# Which model of computation to simulate to prove universality?

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.

• check the first chapter of the first volume of Odifreddi's Classical Recursion Theory. Feb 28, 2012 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. Feb 28, 2012 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. Feb 28, 2012 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. Mar 6, 2012 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. Jun 9, 2012 at 1:29