A Small Machine Maximised

The Prompt

Construct and enumerate all halting Turing machines for a small number of states (n = 2 or n = 3) on a two-symbol alphabet. For each halting machine, count the number of 1s written on the tape. Verify the known Busy Beaver values — BB(2) = 4, BB(3) = 6 — by exhaustive search or reasoned elimination. Reflect on how the enumeration grows and why exhaustive methods fail for n ≥ 5.

Completion Criteria

A written enumeration or classification of the halting machines for n = 2 or n = 3, verification of the known BB value, and a one-paragraph reflection on the growth of the search space.

Students who have attested

No Students have attested this quest yet. Be the first.