Turing Machine

A Turing machine is a non-existent, hypothetical machine ‘invented’ by Alan Turing. This machine can be used to simulate any computer algorithm.

A simple Turing machine consists of:

• An infinite one-dimensional tape divided into cells, where each cell contains a specific symbol from a finite symbol set.
• A head, which reads the cell at a position on the tape, and moves left or right after writing to that cell.
• A state register, which stores the current state the Turing machine is in, from a finite set of states including the halting state.
• A finite set of instructions, which determine the action of the machine.

The instructions relayed to a Turing Machine can be represented using a state transition diagram, which can be thought of as the algorithm for the machine.

A simple state transition diagram which converts 0s to 1s and 1s to 0s

Formal Definitions §

A TM is described by:

1. A finite set of states, $Q=\{S_0,S_1,...\}$
2. An input alphabet $\Sigma =\{A,B,C\}or\{1,2,3\}or...$
3. A tape alphabet (Γ, typically; contains Σ).
4. A transition function (δ, typically).
5. A start state (q0, in Q, typically).
6. A blank symbol (B typically).
7. A set of halting states (F ⊆ Q, typically).