BB(1,m): Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
Created page with "{| class="wikitable" |+ Small busy beaver values<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref> ! !!1-state |- ! 2-symbol | BB(1) = 1 (Halt) |}"
 
Polygon (talk | contribs)
Added note about Σ(1,1)
 
(10 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{| class="wikitable"
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 <code>A0</code> transition. In fact, there are only 3 different turing machines in [[TNF]]: One halting: <code>A0:1RZ</code> and 2 trivial [[Translated Cyclers]]: <code>A0:0RA</code> and <code>A0:1RA</code>. 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.
|+ Small busy beaver values<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref>
 
! !!1-state
==Champions==
|- 
S(1,m) = 1 and Σ(1,m) = 1 are both achieved by only one [[champion]] in TNF:
! 2-symbol
* {{TM|1RZ---|halt}}
| [[BB(1)]] = 1 (Halt)
[[Category:BB Domains]]
|}

Latest revision as of 15:54, 30 August 2025

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: