Turing machine

Mathematical model of computation

Turing machine

A Turing machine is a mathematical model of computation that defines an abstract machine. The Turing machine manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.

A model of a Turing machine

History

The concept of the Turing machine was introduced by Alan Turing in 1936, in his paper "On Computable Numbers, with an Application to the Entscheidungsproblem." Turing's machine was designed to be a simple yet powerful model of computation that could be used to explore the limits of what can be computed.

Description

A Turing machine consists of:

• A tape divided into cells, one next to the other. Each cell contains a symbol from a finite alphabet.
• A head that can read and write symbols on the tape and move the tape left and right one cell at a time.
• A state register that stores the state of the Turing machine, one of a finite number of states.
• A finite table of instructions that, given the current state and the symbol the head is reading, tells the machine what symbol to write, how to move the tape (left or right), and what the next state of the machine is.

Diagram of a Turing machine

Functionality

The Turing machine operates by reading the symbol on the tape at the current head position, consulting the table of instructions, and then performing the specified action. This action may involve writing a new symbol on the tape, moving the head left or right, and changing the state of the machine. The process continues until the machine reaches a halting state, if such a state exists.

Variants

There are many variants of the Turing machine, including the universal Turing machine, which can simulate any other Turing machine. Other variants include the multi-tape Turing machine, which has multiple tapes and heads, and the non-deterministic Turing machine, which can make multiple moves at once.

Applications

Turing machines are used in theoretical computer science to understand the limits of what can be computed. They are also used in the study of computational complexity to classify problems based on the resources required to solve them.

Busy Beaver

The Busy Beaver is a Turing machine that is designed to produce the maximum number of 1s on its tape before halting, given a specific number of states. The Busy Beaver function is non-computable, meaning there is no algorithm that can determine the maximum number of 1s for any given number of states.

Example of a 3-state Busy Beaver

Related pages

• Alan Turing
• Computability theory
• Church-Turing thesis
• Halting problem
• Universal Turing machine

References

• Turing, A. M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society, 2(42), 230-265.
• Davis, M. (2000). "The Universal Computer: The Road from Leibniz to Turing." W. W. Norton & Company.

• 
  Turing Machine Model by Davey, 2012
• 
  Turing machine diagram 2a
• 
  Turing machine diagram 2b
• 
  Busy Beaver 3 State
• 
  State diagram of 3-state Busy Beaver
• 
  Moves of a 3-state Busy Beaver
• 
  Model of a Turing machine
• 
  Lego Turing Machine
• 
  Turing machine