Week 07 · Sipser 3.1 · Part III
The tape is unbounded, the head moves one cell at a time, and a computation is just a sequence of snapshots. Nothing here is clever — which is the point. This is the machine that defines what "algorithm" means, and the last one below never stops.
Each run is capped at 20 000 steps. A machine that hits the cap is reported as still running — not as a rejection. Telling those two apart in general is precisely the problem that Chapter 4 proves unsolvable.
One transition per line: q0, 0 -> q1, x, R means
in q0 reading 0, write x, move right, go to q1. Directives:
start:, accept:, reject:, blank:.
Watch 0^(2ⁿ) decide 00000000. It crosses off every other 0 and sweeps back, again and again. Nothing about the machine knows what a power of two is; the halving falls out of the sweeps. That is what a "high-level description" in Sipser is compressing.
Run the busy beaver on empty input. Three states, two symbols, no input at all — and it still runs for a while before halting. Now imagine deciding, for an arbitrary such machine, whether it ever will.
Run "never halts" and press stop. You knew to stop because you read the machine. The undecidability of ATM says no program can do that reading for every machine and every input — and the proof is four lines of diagonalisation in week 9.