Turing Machine Equivalents

Turing Machine Equivalents

A Turing machine is a hypothetical device with an infinite memory capacity, first conceived by Alan Turing in 1936. The machine manipulates symbols on a potentially infinite strip of tape according to a table of rules, and can be adapted to simulate the logic of any computer algorithm.

While none of the following models have been shown to have more power than the single-tape, one-way infinite, multi-symbol Turing-machine model, their authors defined and used them to investigate questions and solve problems more easily than they could have if they had stayed with Turing's a-machine model.

Read more about Turing Machine Equivalents:  Machines Equivalent To The Turing Machine Model, Tape-based Turing Machines, Register Machine Models, Machines With Input and Output, Other Equivalent Machines and Methods

Other articles related to "turing machine equivalents, turing machine, machines, equivalent, turing machines":

Turing Machine Equivalents - 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 ... computational model, based on string rewriting, equivalent to the Turing machines ...

Famous quotes containing the word machine:

    Much that is natural, to the will must yield.
    Men manufacture both machine and soul,
    And use what they imperfectly control
    To dare a future from the taken routes.
    Thom Gunn (b. 1929)