The Turing Machine

• Print

A Turing machine is a theoretical device that manipulates symbols on a strip of tape. It consists of a strip of tape on which are written only the symbols “0” and “1” with each symbol in a cell on the tape, together with a reader which scans the tape cell by cell, and a list of instructions which tells the machine what to do if it reads a particular symbol in a cell – whether to move left or right, to change the symbol or stop.

Turing's own definition of the Turing machine is:

"an infinite 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 behavior 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".

The Turing machine works by reading the symbols imprinted on the tape cells according to the specified rules or transitions in order to either modify its internal state or to write a symbol on the tape. The machine operates according to four tuples or modes of operation, which are represented as such:

⟨ s0, 1, s0, » ⟩ ⟨ s0, 0, s1, 1 ⟩ ⟨ s1, 1, s1, «⟩ ⟨ s1, 0, s2,» ⟩ or in general

(current state, scanned symbol, new state, action)

This means that “if the machine is in state s0 and the current cell contains symbol then move into new state taking action”. In other words, the machine determines its initial state and reads the symbol ("0" or "1") that is represented in the tape cell, and then proceeds to either write a symbol on the tape cell square under the head, move one cell to the right, move one cell to the left, change its state, or halt its operation (the machine halts when there are no or more than one transition rule specified).

Despite its simplicity, a Turing machine can be adapted to simulate any computer algorithm. Turing machines are not intended as a practical computing technology, but rather as a thought experiment representing a computing machine. They help computer scientists understand the limits of mechanical computation.