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:

    In truth, politeness is artificial good humor, it covers the natural want of it, and ends by rendering habitual a substitute nearly equivalent to the real virtue.
    Thomas Jefferson (1743–1826)

    Gee, I wish we had one of them doomsday machines things.
    Stanley Kubrick (b. 1928)

    All men are equally proud. The only difference is that not all take the same methods of showing it.
    François, Duc De La Rochefoucauld (1613–1680)