Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
check the first chapter of the first volume of Odifreddi's Classical Recursion Theory. – Kaveh Feb 28 '12 at 6:55
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 Feb 28 '12 at 10:05
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. However, note that using arbitrary precision rationals is regarded as just as unrealistic as unbounded-size registers or infinite tape. – András Salamon Feb 28 '12 at 12:26
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 Mar 6 '12 at 8:19
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 stackexchange. – Artem Kaznatcheev Jun 9 '12 at 1:29

There's a comprehensive treatment of different Turing-complete computation models and proofs of their equivalence in Martin Davis, Computability and Unsolvability. Some of the most popular systems are described, including Turing-Machines, Post problems and general recursive functions.

share|cite|improve this answer

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...

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.