Equivalence of models of computation

Register (URM), counter and RAM machines, and theorems that Turing machines and other models compute exactly the partial recursive functions or decide and recognize exactly the recursive and r.e. predicates (Church–Turing equivalences).

• Counter machines
• Equivalence of Turing machines and recursive functions
• Multi-tape machines decide only recursive predicates
• Random-access machines
• Single-tape machines decide the recursive predicates
• Nondeterministic Turing machines
• Unlimited register machines

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.