Tell me more ×
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.
up vote 6 down vote favorite

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|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. 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 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
show 1 more comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.