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":

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 ...
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 ...
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 questions in the theory of ... In particular, 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 ... the standard model for string-oriented computation, and the random access machine (RAM) as introduced by Cook and Reckhow.. ...
Leaf Language
... method of characterizing a complexity class by formalizing what it means for a machine to "accept" an input ... 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 ... For example, a non-deterministic Turing machine accepts if at least one branch accepts, and rejects only if all branches reject ...
Counter Machine - Two-counter Machines Are Turing Equivalent (with A Caveat) - Step 3: Four Counters Can Be Simulated By Two Counters.
... can simulate four counters, which are 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 ...

Famous quotes containing the word machine:

    The chrysanthemums’ astringent fragrance comes
    Each year to disguise the clanking mechanism
    Of machine within machine within machine.
    Wallace Stevens (1879–1955)