Turing Machines
Add an infinite tape and you get the definition of "computable" itself — the model every real computer is equivalent to.
The Machine That Defines Computation
A Turing machine is a finite automaton with an infinite tape it can read, write, and move across in both directions. That’s the whole addition — unbounded, rewritable memory — and it’s enough to compute anything that can be computed. It has a finite state control, a tape head, and rules of the form: “in state q reading symbol s, write s′, move L/R, go to state q′.”
The Church-Turing Thesis
The Church-Turing thesis claims: any function that can be computed by any mechanical procedure can be computed by a Turing machine. It’s not a theorem (you can’t prove what “mechanical procedure” means formally) but nothing in 90 years has violated it. Lambda calculus, your laptop, quantum computers, a human with paper — all compute exactly the same set of functions.
| Model | Memory | Computes |
|---|---|---|
| Finite automaton | State only | Regular languages |
| Pushdown automaton | + a stack | Context-free languages |
| Turing machine | + infinite tape | Everything computable |
This hierarchy (the Chomsky hierarchy) is the spine of the whole subject: each machine adds memory and climbs to a strictly larger class of problems.
Turing Completeness
A system is Turing complete if it can simulate any Turing machine. Your programming language is (that’s why they’re interchangeable in principle). So are some surprising things: SQL with recursive CTEs, C++ templates, Conway’s Game of Life, even Excel formulas and Magic: The Gathering. The bar is low — conditional branching plus unbounded memory and loops is enough.
A Universal Machine — the First "Software"
Turing’s deepest move: a Universal Turing Machine takes the description of any Turing machine as input on its tape and simulates it. That is the idea of the stored program — a machine whose input is itself a program — and it’s the reason your CPU isn’t rewired for each app. The interpreter reading these very words is a universal machine.
Interview Questions
What single capability makes a Turing machine more powerful than a pushdown automaton?
An unbounded tape it can read AND write in any position and direction, versus a stack that only exposes its top. That random-access rewritable memory lets it compute anything computable, not just nested structure.
State the Church-Turing thesis.
Any function computable by any effective/mechanical procedure is computable by a Turing machine. It defines “computable”; all reasonable models (lambda calculus, real computers, quantum machines) compute the same class, differing only in efficiency.
What does Turing complete mean, and name a surprising example.
It means a system can simulate any Turing machine — needs conditional branching, loops/recursion and unbounded memory. Surprising cases: recursive SQL, C++ templates, Conway’s Game of Life, Excel formulas.
What is a Universal Turing Machine and why does it matter?
A TM that reads the description of any other TM plus its input and simulates it. It’s the theoretical basis of the stored-program computer — one fixed machine running arbitrary software rather than being rebuilt per task.