Turing machine
Introduction
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, the machine can simulate the logic of any computer algorithm, and is used in theoretical computer science to understand the nature of computation. It is named after the British mathematician Alan Turing who introduced this model in 1936.
Definition
A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Given the initial state and the initial tape contents, the instructions for a Turing machine can be fully determined by a finite set of tuples.
Components
A Turing machine consists of:
- A tape divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol (here written as '0') and one or more other symbols. The tape is assumed to be arbitrarily extendable to the left and to the right, i.e., the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written before are assumed to be filled with the blank symbol.
- A head that can read and write symbols on the tape and move the tape left and right one (and only one) cell at a time. In some models the head moves and the tape is stationary.
- A state register that stores the state of the Turing machine, one of a finite set of states. The state register can be in one of a finite number of states, except for the initial state and the final state (or states), which are distinguished from each other.
Operation
A Turing machine mathematically models a machine that mechanically operates on a tape. On this tape are symbols, which the machine can manipulate, one at a time, using rules dictated by a set of tuples. These tuples dictate if the machine will move left or right or write a symbol and change state. If the machine is currently in the "m" state and reads a "0" symbol, it writes the symbol "1", moves one cell to the right, and continues in state "n". This is an example of a tuple in the machine's table of rules.
Turing Machine Variants
There are many variants of Turing machines in terms of their abilities and complexity. Some of these include:
- Multi-tape Turing machines
- Multi-dimensional Turing machines
- Non-deterministic Turing machines
- Universal Turing machines
Each of these variants modifies the basic Turing machine concept in some way, yet each remains equivalent in computational power to the basic, "vanilla" Turing machine.
Universal Turing Machine
A Universal Turing Machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The UTM essentially achieves this by reading both the description of the machine to be simulated as well as the input thereof from its own tape.
Turing Machine and Computability
The concept of a Turing machine is important in the theory of computation because it gives a precise definition of what it means for a function to be computable. A function is Turing computable if there exists some Turing machine which, given an input tape coded with the function's argument, halts with the function's value on the output tape.
Turing Machine and Complexity Theory
In complexity theory, Turing machines are used to model algorithms in order to determine the computational difficulty of a problem, referred to as its space and time complexity.