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:
“When the apple is ripe it will fall.”
—Irish proverb.
An English equivalent to this might be, “To everything there is a season.”
“Shoes are the first adult machines we are given to master.”
—Nicholson Baker (b. 1957)
“The greatest part of our faults are more excusable than the methods that are commonly taken to conceal them.”
—François, Duc De La Rochefoucauld (1613–1680)