Turing Machine

The machine was invented by Alan Turing in 1936.

General definition

A Turing Machine is usually composed of four main components:

A tape divided into cells. This tape is the way the machine reads inputs, writes outputs and manipulates information (storing it, moving it, etc.). Each cell can contain any symbol of a predefined alphabet. It is also often presented as infinitely long on both sides.
A head that can read or write a symbol from the tape at its current position.
A register storing the current state of the machine, usually with special start_state and end_state.
A table of instructions mapping the current state and current tape symbol to a specific triple action (each of the steps is optional):
1. Read/write a symbol in current position
2. Move the head left or right
3. Change the state