Turing Machine Simulator

Watch a Turing machine read, write, and move along an infinite tape following transition rules.

Worked example — Turing Machine Simulator

Read	'0'
Head position	0

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

One tape makes palindromes quadratic 🖖

The palindrome preset accepts 1,0,1,0,1 in 21 steps and rejects 1,0,1,1 in 13. The machine cannot compare the two ends at once, so it erases the leftmost symbol, carries it in its state, walks the whole tape to check the rightmost, erases that, and walks back — once per pair. For an n-cell all-ones tape this program takes exactly (n+1)(n+2)/2 steps: 21 at n = 5, 55 at n = 9, 253 at n = 21. Hand the same machine a second tape and the job becomes linear; Hennie proved in 1965 that on a single tape it cannot be. The cost is not the alphabet or the state count — it is the walking.

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.

Problem solved in full

Configurations the palindrome program passes through on 1 0 1 0 1 5 steps
The palindrome program starts on the tape 1 0 1 0 1, head on cell 0, state q0. Count every configuration it passes through before it halts — from the rule table, without stepping it — and then say what that count does as the input gets longer.

Open this problem in the tool
1. Read the table as rounds, not as a list of moves. Only one rule can open a round: q0 erases the leftmost symbol and branches on what it just erased, to q1 for a 1 and to q2 for a 0. That branch is the entire comparison mechanism. The machine never stores the symbol on the tape; it stores it in which state it is in, so testing the far end against it later costs no extra moves.
  
  $q_{0} : 1 \mapsto (_, R, q_{1}), 0 \mapsto (_, R, q_{2})$
2. Count one round on a block of m symbols. Erasing the left end is 1 move. The head then crosses the m − 1 symbols still standing and spends 1 more move on the blank beyond them to turn around. Erasing the right end is 1 move, walking back over the m − 2 survivors is m − 2 moves, and 1 last move on the blank at the left end faces the machine right again in q0.
  
  $1 + (m - 1) + 1 + 1 + (m - 2) + 1 = 2 m + 1$
3. Our tape gives a block of 5, then 3, then a single symbol — and a single symbol is not a round. q0 erases it, q1 walks off the right end and turns, and q1c finds a blank where a partner should be. An odd-length palindrome has an unmatched centre, and finding that blank is what accepts.
  
  $m = 5 : 11, m = 3 : 7, m = 1 : 3$
4. Add the three, then mind the fencepost. 21 is the number of moves; the transport counts configurations, and 21 moves visit 22 of them once you include the one you started in.
  
  $11 + 7 + 3 = 21 ⟹ 21 + 1 = 22$
5. Generalise to any odd length n. The blocks run n, n − 2, and so on down to 3, each costing 2m + 1, with the centre costing 3. Summing that list gives a quadratic in n, not a linear one.
  
  $(2 n + 1) + (2 n - 3) + \dots + 7 + 3 = \frac{( n + 1 ) ( n + 2 )}{2}$
Answer

22 configurations — 21 moves. The quadratic is the part worth keeping. A 21-symbol palindrome costs 253 moves: 12 times the work for an input 4.2 times as long. The reason is geometric rather than clever — the two symbols being compared always sit at opposite ends of what is left, and there is one head, so every pair costs one full traverse of the remaining tape. Give the machine a second tape and the same job goes linear: copy the input across as you read it, then run the two heads in opposite directions and compare in one pass, roughly 3n moves. On one tape there is nowhere to put that copy, and the shuttling is forced.

$n = 5 : 21; n = 21 : \frac{22 \cdot 23}{2} = 253$

References (3)

The single-tape quadratic lower bound for palindromes: F. C. Hennie, "One-tape, off-line Turing machine computations." Information and Control 8(6), 553–578, 1965.
Where multi-tape time complexity classes were set out: J. Hartmanis and R. E. Stearns, "On the computational complexity of algorithms." Transactions of the American Mathematical Society 117, 285–306, 1965.
The machine itself: A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society s2-42(1), 230–265, 1937.

YouTube (1)

The Rest Is Science·Alan Turing's Final Theory Was About Leopards

By the 42Math team · Reviewed against published sources. Corrections welcome.