Turing Machine Simulator
Watch a Turing machine read, write, and move along an infinite tape following transition rules.
Decidability limits and formal automata theory 🖖
A Turing machine is a formal mathematical model of computation consisting of an infinite tape, a tape head, and a state transition table. It defines the limits of what can be calculated: any algorithm can be simulated by a Turing machine (Church-Turing thesis). Statically, it proves the undecidability of the Halting Problem, demonstrating that no general algorithm can predict whether a program will run forever or terminate.
How a few rules run everything 🖖
A Turing machine has almost nothing to it: a strip of tape, a head that reads one cell, and a short lookup table. Each step it checks only its current state and the symbol under the head, then writes a symbol, moves one cell left or right, and switches state. Run the binary-increment preset and watch it glide right to the end, then carry the +1 back leftward — exactly how you add by hand.
The Busy Beaver outruns the universe 🖖
Ask the smallest question — how long can a tiny machine run before it halts? — and computation explodes. A 5-state, 2-symbol machine can march for exactly 47,176,870 steps before stopping, a value only proven in 2024. For 6 states the known record already exceeds 2↑↑↑5, a tower of powers that dwarfs every atom in the cosmos. That is why simulators like this one cap each run: a handful of states can outlast eternity.
Example problems
- Bit Flip - Bit flip: swap 0s and 1s
- Binary +1 - Binary increment: 1011→1100
- 1111 → 10000 - 1111 → 10000
- Unary m+n - Unary addition: 3+2=5
- 1+1 = 2 - 1+1 = 2
- Palindrome ✓ - Palindrome checker: 10101
- 1011 — rejected - 1011 — rejected