A Turing machine is composed of an infinite tape bounded on the left, a read-write tape head, and a finite control.

A Turing Machine (TM) is described by the tuple^{}

(1) |

*Q*- is the finite set of states,
- is the the finite set of allowable tape symbols,
*B*- is the blank symbol ().
- is the set of input symbols, .
- is the next move function, .
*q*_{0}- is the start state ().
*F*- is the set of final states, .

- 1.
- changes state,
- 2.
- prints a symbol on tape cell, replacing what was written there before, and
- 3.
- moves the tape head left or right one cell.