Turing Machine Equivalents - Other Equivalent Machines and Methods

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)

    As machines become more and more efficient and perfect, so it will become clear that imperfection is the greatness of man.
    Ernst Fischer (1899–1972)

    With a generous endowment of motherhood provided by legislation, with all laws against voluntary motherhood and education in its methods repealed, with the feminist ideal of education accepted in home and school, and with all special barriers removed in every field of human activity, there is no reason why woman should not become almost a human thing. It will be time enough then to consider whether she has a soul.
    Crystal Eastman (1881–1928)