Other Equivalent Machines and Methods
- Multidimensional Turing machine: For example, a model by Schönhage (1980) uses the four head-movement commands { North, South, East, West }.
- Single-tape, multi-head Turing machine: In an undecidability proof of the "problem of tag", Minsky 1961 and Shepherdson and Sturgis (1963) described machines with a single tape that could write along the tape with one head and read further along the tape with another.
- Markov Algorithm (1960) is another remarkably simple computational model, based on string rewriting, equivalent to the Turing machines.
- Lambda calculus
- Queue automaton
Read more about this topic: Turing Machine Equivalents
Famous quotes containing the words equivalent, machines and/or methods:
“Inter-railers are the ambulatory equivalent of McDonalds, walking testimony to the erosion of French culture.”
—Alice Thompson (b. 1963)
“If men do not keep on speaking terms with children, they cease to be men, and become merely machines for eating and for earning money.”
—John Updike (b. 1932)
“We can best help you to prevent war not by repeating your words and following your methods but by finding new words and creating new methods.”
—Virginia Woolf (1882–1941)