Is a Turing machine a real computer?

No, it is a mathematical abstraction with unlimited tape and no concern for speed or memory cost. Its value is conceptual: it pins down exactly what can be computed in principle, and any task a real computer can perform a Turing machine can also perform given enough tape and time.

Why is the universal Turing machine important?

It shows that one fixed machine can carry out the behavior of any other when given that machine's description as input. This is the theoretical foundation of the general-purpose programmable computer, where software is data fed to a single interpreting device rather than rewiring for each task.

Turing Machines

The Turing machine is an abstract device with a finite control and an unbounded tape that captures the intuitive notion of an algorithm, and it serves as the standard reference model for what is computable.

Definition

A Turing machine consists of a finite set of states and a two-way infinite tape of cells; at each step it reads the symbol under its head, writes a symbol, moves left or right, and changes state according to a transition function, halting when it enters an accepting or rejecting state.

Scope

This topic covers the definition and operation of Turing machines, configurations and computations, robustness of the model under variants such as multiple tapes and nondeterminism, the universal Turing machine that can simulate any other, and the encoding of machines as data that makes self-reference and undecidability arguments possible.

Core questions

How does a simple read–write–move device capture the full notion of algorithm?
Why do many variants of the model compute exactly the same functions?
What is a universal machine, and why is its existence significant?
How does encoding machines as strings enable proofs about their own behavior?

Key theories

Universality: There is a single universal Turing machine that, given an encoding of any machine and its input, simulates that machine's computation, foreshadowing the stored-program computer in which programs are themselves data.
Robustness of the model: Adding tapes, multiple heads, two-dimensional tapes, or nondeterminism does not change the class of computable functions, so the Turing machine captures a notion of computation that is insensitive to such details.

Clinical relevance

The Turing machine is the yardstick against which the power of programming languages and computer architectures is measured, and the universal machine is the conceptual ancestor of the general-purpose stored-program computer on which all modern computing rests.

History

Turing introduced his machines in 1936 to make precise what it means for a number to be computable and to resolve Hilbert's decision problem. The idea of a universal machine, in which a stored description controls a general device, influenced von Neumann's design of the stored-program computer a decade later.

Key figures

Alan Turing
Emil Post
John von Neumann

Seminal works

turing1937
sipser2013

Frequently asked questions

Is a Turing machine a real computer?: No, it is a mathematical abstraction with unlimited tape and no concern for speed or memory cost. Its value is conceptual: it pins down exactly what can be computed in principle, and any task a real computer can perform a Turing machine can also perform given enough tape and time.
Why is the universal Turing machine important?: It shows that one fixed machine can carry out the behavior of any other when given that machine's description as input. This is the theoretical foundation of the general-purpose programmable computer, where software is data fed to a single interpreting device rather than rewiring for each task.