Turing Machine

A Turing machine is a device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.

The "Turing" machine was described in 1936 by Alan Turing who called it an "a-machine" (automatic machine). The Turing machine is not intended as practical computing technology, but rather as a hypothetical device representing a computing machine. Turing machines help computer scientists understand the limits of mechanical computation.

Turing gave a succinct definition of the experiment in his 1948 essay, "Intelligent Machinery". Referring to his 1936 publication, Turing wrote that the Turing machine, here called a Logical Computing Machine, consisted of:

...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behaviour of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings. (Turing 1948, p. 61)

A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine (UTM, or simply a universal machine). A more mathematically oriented definition with a similar "universal" nature was introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing's in a formal theory of computation known as the Church–Turing thesis. The thesis states that Turing machines indeed capture the informal notion of effective method in logic and mathematics, and provide a precise definition of an algorithm or 'mechanical procedure'.

Studying their abstract properties yields many insights into computer science and complexity theory.

Read more about Turing Machine:  Informal Description, Formal Definition, Additional Details Required To Visualize or Implement Turing Machines, Models Equivalent To The Turing Machine Model, Choice C-machines, Oracle O-machines, Universal Turing Machines, Comparison With Real Machines

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

Counter Machine - Two-counter Machines Are Turing Equivalent (with A Caveat) - Step 1: A Turing Machine Can Be Simulated By Two Stacks.
... A Turing machine consists of an FSM and an infinite tape, initially filled with zeros, upon which the machine can write ones and zeros ... At any time, the read/write head of the machine points to one cell on the tape ... Accordingly, a Turing machine can be simulated by an FSM plus two stacks ...
Counter Machine - Two-counter Machines Are Turing Equivalent (with A Caveat) - Step 3: Four Counters Can Be Simulated By Two Counters.
... in turn simulating two stacks, which are simulating a Turing machine ... Therefore, an FSM plus two counters is at least as powerful as a Turing machine ... A Turing machine can easily simulate an FSM with two counters, therefore the two machines have equivalent power ...
Leaf Language
... class by formalizing what it means for a machine to "accept" an input ... in terms of a polynomial-time nondeterministic Turing machine, where each branch can either accept or reject, and the entire machine accepts or rejects as some function of the branches' conditions ... For example, a non-deterministic Turing machine accepts if at least one branch accepts, and rejects only if all branches reject ...
Multi-track Turing Machine
... A Multitrack Turing machine is a specific type of Multi-tape Turing machine ... In a standard n-tape Turing machine, n heads move independently along n tracks ... In a n-track Turing machine, one head reads and writes on all tracks simultaneously ...
History - 1970–present: The Turing Machine As A Model of Computation
... Today the counter, register and random-access machines and their sire the Turing machine continue to be the models of choice for theorists investigating ... computational complexity theory makes use of the Turing machine Depending on the objects one likes to manipulate in the computations (numbers like nonnegative integers or alphanumeric strings), two models ... the standard model for string-oriented computation, and the random access machine (RAM) as introduced by Cook and Reckhow.. ...

Famous quotes containing the word machine:

    The momentary charge at Balaklava, in obedience to a blundering command, proving what a perfect machine the soldier is, has, properly enough, been celebrated by a poet laureate; but the steady, and for the most part successful, charge of this man, for some years, against the legions of Slavery, in obedience to an infinitely higher command, is as much more memorable than that as an intelligent and conscientious man is superior to a machine. Do you think that that will go unsung?
    Henry David Thoreau (1817–1862)