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

**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 ...

**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 ...

**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.. ...

... 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 ...

... 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)