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:
“Nobody can deny but religion is a comfort to the distressed, a cordial to the sick, and sometimes a restraint on the wicked; therefore whoever would argue or laugh it out of the world without giving some equivalent for it ought to be treated as a common enemy.”
—Mary Wortley, Lady Montagu (1689–1762)
“In Hell all the messages you ever left on answering machines will be played back to you.”
—Judy Horacek (b. 1961)
“A writer who writes, “I am alone” ... can be considered rather comical. It is comical for a man to recognize his solitude by addressing a reader and by using methods that prevent the individual from being alone. The word alone is just as general as the word bread. To pronounce it is to summon to oneself the presence of everything the word excludes.”
—Maurice Blanchot (b. 1907)