<p>There's a comprehensive treatment of different Turing-complete computation models and proofs of their equivalence in Martin Davis, <a href="http://www.futuretg.com/FTHumanEvolutionCourse/FTFreeLearningKits/08-CO-Computer,%20Internet%20and%20Programming/087-CO03-Algorithms%20and%20Programming%20Languages/Martin%20Davis%20-%20Computability%20and%20Unsolvability.pdf" rel="nofollow">Computability and Unsolvability</a>. Some of the most popular systems are described, including Turing-Machines, Post problems and general recursive functions.</p>

CC BY-SA 3.0
2013-09-23T14:12:52.553Z
2013-09-23T14:12:52.553Z
cody
<p>I learned theoretical computer sciences from Linz's textbook Introduction to Theoreticel Computer Science. It is a method and algorithm book therefore there are many examples ranging from context free languages to Universal Turing Machines. It clearly shows the notion of expressive power of a model of computation. You'll however need the patience to work through the algorithms and the explanations which are for an undergrad audience.</p>

<p>General books on the subject, that do not delve in technicalities? You might have more chances in the cognitive sciences rack?</p>

<p>I remember a book called From Turing to Chaitin, that discusses the philosophical aspects of uncomputability...</p>

<p>There is a republication of Turing's paper on Turing machines (Hilbert's decision problem) which comes with a long introductory paper discusiing Turing's work. It is published in French though.</p>

<p>It is very hard to be honest to find a single book on such a large topic which will satisfy all one's curiosity...</p>

CC BY-SA 3.0
2013-07-25T04:37:02.437Z
2013-07-25T04:37:02.437Z
Phil
<p>I am starting out in theoretical computer science.</p>

<p>I have a model of computation based on observations of auto-associative memory in the brain.  I believe (with little evidence) that I can do anything in this simple model.  I understand the primary way of proving universality is to show that your model can simulate another universal model, especially a turing machine.</p>

<p>I would like to request the following information:</p>

<ol>
<li><p>References to clear and easy to follow proofs of universality of a computational model, graspable by an able beginner such as myself.</p></li>
<li><p>Guidance as to what model would be easiest model to attempt to simulate.  I imagine the answer to this may be 'it depends'.  Currently it appears my model bears some semblance to lambda calculus.</p></li>
</ol>

CC BY-SA 3.0
2012-03-06T08:19:40.863Z
As a starting point, to satisfy yourself that your model *is* Turing-complete, you could try to simulate loops and conditionals, as well as basic operations such as memory read/write. It really doesn't take much more than that.
Magnus Lie Hetland
CC BY-SA 3.0
2012-06-09T01:29:08.547Z
As you noted in your question, and as the comments suggest. There are many nice universal models (lambda calc, TMs, cellular automata, tag systems, neural networks, random walks, etc etc) and it is hard to help you without more detail about your model. Another community that might be helpful to you is the [Cognitive Sciences](http://cogsci.stackexchange.com/) stackexchange.
Artem Kaznatcheev
CC BY-SA 3.0
2012-08-28T16:07:05.693Z
one of the simplest criteria that can reject many models is that a system with finite memory cannot be Turing complete (because Turing completeness requires the analog of an infinite size tape, or perhaps better characterized as _unbounded_). therefore it seems fairly reasonable to argue that no finite volume/matter system can be Turing complete. but some make a completely different argument eg Penrose, in Emperors New Mind, that our brains are beyond Turing complete because we can comprehend the undecidability of the halting problem....
vzn
CC BY-SA 3.0
2012-02-28T06:55:44.140Z
check the first chapter of the first volume of Odifreddi's Classical Recursion Theory.
Kaveh
CC BY-SA 3.0
2012-02-28T10:05:13.267Z
You could also check out chapter three of Cutland's Computability. The book is built on URM's, but in that chapter, he proves equality to other models.
Peter
CC BY-SA 3.0
2012-02-28T12:26:00.043Z
As you say, it depends.  You could check some of the simpler Turing-equivalent models such as two-stack pushdown automata or two-counter machines.  But your application may be closer to artificial neural networks, so you may want to look at Siegelmann and Sontag's analogue computation model instead.   http://dx.doi.org/10.1006/jcss.1995.1013  However, note that using arbitrary precision rationals is regarded as just as unrealistic as unbounded-size registers or infinite tape.
András Salamon
<reference-request><computability><universal-computation><machine-models>
Which model of computation to simulate to prove universality?
zenna
# Which model of computation to simulate to prove universality?

(Asked by: username_0 on 2012-02-28)

I am starting out in theoretical computer science.

I have a model of computation based on observations of auto-associative memory in the brain. I believe (with little evidence) that I can do anything in this simple model. I understand the primary way of proving universality is to show that your model can simulate another universal model, especially a turing machine.

I would like to request the following information:

1. References to clear and easy to follow proofs of universality of a computational model, graspable by an able beginner such as myself.
2. Guidance as to what model would be easiest model to attempt to simulate. I imagine the answer to this may be 'it depends'. Currently it appears my model bears some semblance to lambda calculus.

**Tags:** reference-request, computability, universal-computation, machine-models

> **Comments:**
> **username_4**: check the first chapter of the first volume of Odifreddi's Classical Recursion Theory.  
> **username_5**: You could also check out chapter three of Cutland's Computability. The book is built on URM's, but in that chapter, he proves equality to other models.  
> **username_6**: As you say, it depends.  You could check some of the simpler Turing-equivalent models such as two-stack pushdown automata or two-counter machines.  But your application may be closer to artificial neural networks, so you may want to look at Siegelmann and Sontag's analogue computation model instead.   http://dx.doi.org/10.1006/jcss.1995.1013  However, note that using arbitrary precision rationals is regarded as just as unrealistic as unbounded-size registers or infinite tape.  
> **username_1**: As a starting point, to satisfy yourself that your model *is* Turing-complete, you could try to simulate loops and conditionals, as well as basic operations such as memory read/write. It really doesn't take much more than that.  
> **username_2**: As you noted in your question, and as the comments suggest. There are many nice universal models (lambda calc, TMs, cellular automata, tag systems, neural networks, random walks, etc etc) and it is hard to help you without more detail about your model. Another community that might be helpful to you is the [Cognitive Sciences](http://cogsci.stackexchange.com/) stackexchange.  
> **username_3**: one of the simplest criteria that can reject many models is that a system with finite memory cannot be Turing complete (because Turing completeness requires the analog of an infinite size tape, or perhaps better characterized as _unbounded_). therefore it seems fairly reasonable to argue that no finite volume/matter system can be Turing complete. but some make a completely different argument eg Penrose, in Emperors New Mind, that our brains are beyond Turing complete because we can comprehend the undecidability of the halting problem....  

---

## 2 answers

### Answer by username_7 on 2013-09-23. Score: 3

There's a comprehensive treatment of different Turing-complete computation models and proofs of their equivalence in Martin Davis, [Computability and Unsolvability](http://www.futuretg.com/FTHumanEvolutionCourse/FTFreeLearningKits/08-CO-Computer,%20Internet%20and%20Programming/087-CO03-Algorithms%20and%20Programming%20Languages/Martin%20Davis%20-%20Computability%20and%20Unsolvability.pdf). Some of the most popular systems are described, including Turing-Machines, Post problems and general recursive functions.


---

### Answer by username_8 on 2013-07-25. Score: 0

I learned theoretical computer sciences from Linz's textbook Introduction to Theoreticel Computer Science. It is a method and algorithm book therefore there are many examples ranging from context free languages to Universal Turing Machines. It clearly shows the notion of expressive power of a model of computation. You'll however need the patience to work through the algorithms and the explanations which are for an undergrad audience.

General books on the subject, that do not delve in technicalities? You might have more chances in the cognitive sciences rack?

I remember a book called From Turing to Chaitin, that discusses the philosophical aspects of uncomputability...

There is a republication of Turing's paper on Turing machines (Hilbert's decision problem) which comes with a long introductory paper discusiing Turing's work. It is published in French though.

It is very hard to be honest to find a single book on such a large topic which will satisfy all one's curiosity...


---

