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:
“For some men the power to destroy life becomes the equivalent to the female power to create life.”
—Myriam Miedzian, U.S. author. Boys Will Be Boys, ch. 4 (1991)
“The machines that are first invented to perform any particular movement are always the most complex, and succeeding artists generally discover that, with fewer wheels, with fewer principles of motion, than had originally been employed, the same effects may be more easily produced. The first systems, in the same manner, are always the most complex.”
—Adam Smith (1723–1790)
“If you want to know the taste of a pear, you must change the pear by eating it yourself.... If you want to know the theory and methods of revolution, you must take part in revolution. All genuine knowledge originates in direct experience.”
—Mao Zedong (1893–1976)