Turing Machine Illustration

Turing Machine

Computability theory, Computer science

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

← Back to Notes