Turing Machine
A theoretical mathematical model of computation that defines an abstract machine manipulating symbols on a tape according to rules, forming the foundation of computer science.
Also known as: Universal Turing Machine, Abstract Machine
Category: Software Development
Tags: computer-science, mathematics, computation, history, foundations
Explanation
A Turing machine is an abstract mathematical model of computation introduced by Alan Turing in his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem." Despite its simplicity, it can simulate the logic of any computer algorithm and remains the foundational model for understanding what computers can and cannot do.
**How it works:**
A Turing machine consists of:
- **An infinite tape**: Divided into cells, each containing a symbol from a finite alphabet
- **A head**: Reads and writes symbols on the tape, and moves one cell left or right
- **A state register**: Stores the current state of the machine from a finite set of states
- **A transition function**: A table of rules that, given the current state and symbol being read, specifies what to write, which direction to move, and what state to enter next
The machine starts in an initial state, reads the symbol under the head, consults its rules, writes a symbol, moves, changes state, and repeats until it reaches a halting state (or runs forever).
**Why it matters:**
- **Defines computability**: A problem is "computable" if a Turing machine can solve it. This gives a precise mathematical definition to the intuitive notion of an algorithm
- **Universal Turing Machine**: Turing showed that a single machine can simulate any other Turing machine if given its description as input. This is the theoretical basis for general-purpose programmable computers
- **The Halting Problem**: Turing proved that no algorithm can determine, for all possible programs, whether a given program will halt or run forever. This was the first major undecidability result and has profound implications for the limits of computation
- **Church-Turing thesis**: The claim that Turing machines capture everything that is effectively computable, establishing the boundary between what machines can and cannot solve
**Turing machines and real computers:**
Every modern computer is essentially a finite approximation of a Turing machine (limited by finite memory rather than an infinite tape). While real computers are far more complex and efficient, they cannot solve any problem that a Turing machine cannot. The Turing machine thus provides the theoretical ceiling for all digital computation.
**Historical significance:**
Turing's 1936 paper, written when he was just 23, is one of the most important papers in the history of mathematics and computer science. It simultaneously defined computation, proved fundamental limits of what can be computed, and laid the conceptual groundwork for programmable digital computers - years before any such machine existed.
Related Concepts
← Back to all concepts