BB(1,m)

From BusyBeaverWiki
Revision as of 15:54, 30 August 2025 by Polygon (talk | contribs) (Added note about Σ(1,1))
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

BB(1,m) is the Busy Beaver problem for 1-state, m-symbol TMs. They are relatively trivial. No matter how many symbols you have, TNF only has access to a single transition, the initial A0 transition. In fact, there are only 3 different turing machines in TNF: One halting: A0:1RZ and 2 trivial Translated Cyclers: A0:0RA and A0:1RA. These are effectively 1-instruction TMs in BBi. As a result S(1,m) = 1 and Σ(1,m) = 1. Note that Σ(1,1) = 0 as 1-symbol TMs cannot print non-zero symbols.

Champions

S(1,m) = 1 and Σ(1,m) = 1 are both achieved by only one champion in TNF: