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.
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.

By the 42Math team · Updated 2026-06-19

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Example problems

Bit Flip - Bit flip: swap 0s and 1s
Binary +1 - Binary increment: 1011→1100
1111 → 10000 - The worst input increment can be given: every bit is a 1, so the carry has to flip all of them. Watch it scan right to the blank, walk back left turning each 1 into a 0, and then write a new leading 1 on a cell that was never part of the input. Eleven configurations in all, and the tape comes back one cell longer than it went in.
Unary m+n - Unary addition: 3+2=5
1+1 = 2 - The simplest unary sum there is, and it still takes nine configurations. The machine cannot add. It erases one 1 from the left group, walks the whole tape, and appends one 1 on the right, once per unit. Cost grows with the size of the numbers, not the length of their notation. Load the longer unary preset and count the difference.
Palindrome ✓ - Palindrome checker: 10101
1011 — rejected - The outer pair matches: the string starts and ends with a 1, so the machine erases both and comes back for the inner layer. Only there does it find a 0 facing a 1 and move to the reject state, and the readout names the rule that did it. A one-tape palindrome check cannot fail early, which is exactly why it costs a full sweep for every pair.

YouTube

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