| State | Read | Write | Move | Next state |
|---|
Alan Turing introduced his abstract computing machine in his landmark 1936 paper "On Computable Numbers", as a tool to prove that certain problems — most famously the Halting Problem — are undecidable by any algorithm. A Turing machine consists of an infinite tape divided into cells (each holding a symbol from a finite alphabet), a read/write head that moves one cell at a time, and a finite set of states governed by a transition table: given the current state and the symbol under the head, the table specifies the new symbol to write, the direction to move (left or right), and the next state to enter. Despite this minimal description, the Church-Turing thesis holds that any function computable by any physically realisable device can also be computed by a Turing machine.
This simulator provides an animated, step-by-step tape view with a highlighted head, full state-transition table display, and five built-in programs covering binary increment, unary addition, palindrome checking, string copying, and the Busy Beaver for selected state counts. You can pause at any step, inspect the tape, and edit the transition table to write your own programs — making it ideal for exploring computability theory and the gap between "terminates" and "runs forever".
What is the Halting Problem and why can no Turing machine solve it?
The Halting Problem asks: given a description of a Turing machine M and input w, will M eventually halt on w? Turing proved in 1936 that no general algorithm can answer this for all (M, w) pairs. The proof is a diagonal argument: assume a halting-detector H exists, then construct a machine D that uses H to do the opposite of what H predicts about D itself — leading to a contradiction. This was the first rigorous proof that certain well-defined problems are computationally unsolvable.
What is the Busy Beaver problem?
The Busy Beaver function BB(n) is the maximum number of "1" symbols that an n-state, 2-symbol Turing machine can write on a blank tape before halting. Known values: BB(1)=1, BB(2)=4, BB(3)=6, BB(4)=13, BB(5)≥4098 (proven lower bound), and BB(6)≥10^10^10^10^10^7 — astronomically large. BB(n) grows faster than any computable function, proving it is uncomputable. Finding BB values requires exhaustive search among all n-state machines, most of which never halt.
Are all modern computers really just Turing machines?
In terms of computability — which problems can be solved — yes, by the Church-Turing thesis. Any function your laptop or phone can compute can also be computed by a sufficiently large Turing machine, and vice versa. However, real computers differ enormously in efficiency: operations that take polynomial time on a RAM model may require exponential tape-head movements on a single-tape TM. Multi-tape and nondeterministic Turing machines are used in complexity theory to define complexity classes like P, NP, PSPACE, and EXPTIME.
A transition function δ maps (current_state, read_symbol) to (new_symbol, direction, next_state). For a 3-state, 2-symbol machine the table has 6 entries (3 states × 2 symbols). Each entry is typically written as a quintet: (q, s) → (s', D, q') where q is the current state, s the symbol read, s' the symbol to write, D ∈ {L, R} the movement direction, and q' the next state. Special halt states (accept/reject) have no outgoing transitions — the machine stops when it enters one.
A Universal Turing Machine (UTM) takes as input the encoded description of any other Turing machine M plus M's input, and simulates M's computation step by step. UTMs are the theoretical basis for general-purpose computers: just as a CPU runs arbitrary programs by decoding instruction bytes, a UTM runs arbitrary machines by decoding their transition tables from the tape. Minsky (1962) showed a UTM can be constructed with as few as 7 states and 4 symbols; smaller variants with 2 states and 18 symbols have been proved universal.
The binary increment program reads the tape from right (least significant bit) to left, flipping each 1 to 0 until it finds a 0 (or blank), flips that to 1, then halts. For input "1011" (decimal 11), the machine flips the rightmost 1→0 (carry), propagates carry through the next 1→0, finds 0→1, writes "1100" (decimal 12). The maximum number of steps is O(n) where n is the number of bits. This is one of the simplest non-trivial Turing machine programs and a classic teaching example.
A language (set of strings) is decidable if a Turing machine always halts and correctly accepts or rejects every string. It is recognisable (recursively enumerable) if a TM accepts every string in the language but may loop forever on strings not in the language. The Halting Problem is recognisable but not decidable: a TM that simply runs M on w accepts if M halts, but may loop forever if M doesn't. The complement of the Halting Problem is not even recognisable. These distinctions define the basis of the arithmetical hierarchy in mathematical logic.
A two-state, three-symbol Turing machine was proved Turing-complete by Alex Smith in 2007, winning a $25,000 prize offered by Stephen Wolfram. Whether a two-state, two-symbol machine is Turing-complete remains open. Single-state machines are trivially not universal (they cannot change state to implement branching). The 2-state, 3-symbol UTM of Smith is the smallest known universal machine in terms of states × symbols.
A k-tape Turing machine has k independent tapes and heads that move simultaneously at each step. Multi-tape machines are computationally equivalent to single-tape machines (every k-tape machine can be simulated by a single-tape machine), but there is a quadratic time blowup: an O(T(n)) k-tape computation can be simulated in O(T(n)²) steps on one tape. In complexity theory, multi-tape machines more naturally model algorithms with separate input, working, and output spaces, and are the standard model for defining time-bounded complexity classes.
A nondeterministic TM (NTM) may have multiple valid transitions for the same (state, symbol) pair and is considered to "accept" if any branch of its computation tree reaches an accept state. NTMs do not correspond to any physically realisable device but are theoretically powerful: NP is precisely the class of problems decidable by a polynomial-time NTM. Whether P = NP — i.e., whether NTMs offer an exponential advantage — is the most famous unsolved problem in mathematics and computer science.
Tape compression is a simulation technique that shows any TM using an alphabet of size k and one tape can be simulated by a TM using only a binary alphabet (k = 2) with at most a constant factor overhead in time and a logarithmic factor in tape usage. More generally, any TM using space S(n) can be simulated using S(n)/c space for any constant c, at some time cost — this is the Space Compression Theorem (Hennie, 1966). Such results let theorists work with simple binary alphabets without loss of generality.