The machine was invented by Alan Turing in 1936.
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
- A table of instructions mapping the current state and current
tape symbol to a specific triple action (each of the steps is
- Read/write a symbol in current position
- Move the head left or right
- Change the state