7
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ check the first chapter of the first volume of Odifreddi's Classical Recursion Theory. $\endgroup$
    – Kaveh
    Commented Feb 28, 2012 at 6:55
  • $\begingroup$ 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. $\endgroup$
    – Peter
    Commented Feb 28, 2012 at 10:05
  • 1
    $\begingroup$ 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. 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. $\endgroup$
    – András Salamon
    Commented Feb 28, 2012 at 12:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – Magnus Lie Hetland
    Commented Mar 6, 2012 at 8:19
  • $\begingroup$ 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. $\endgroup$
    – Artem Kaznatcheev ♦
    Commented Jun 9, 2012 at 1:29

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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