BB(n,1): Difference between revisions
Jump to navigation
Jump to search
(Created page for 1-symbol TMs) |
(→Champions: Added champions) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
'''BB(n,1)''' is the Busy Beaver problem for n-state, 1-symbol TMs. It is trivial that Σ(n,1) = 0, as 1-symbol TMs cannot print any non-zero symbols. As any transition back to an already visited state will put the machine in an infinite loop, the most effective halting strategy is to pass through the states one by one, halting only in the final state, thus making BB(n,1) = n. | '''BB(n,1)''' is the Busy Beaver problem for n-state, 1-symbol TMs. It is trivial that Σ(n,1) = 0, as 1-symbol TMs cannot print any non-zero symbols. As any transition back to an already visited state will put the machine in an infinite loop, the most effective halting strategy is to pass through the states one by one, halting only in the final state, thus making BB(n,1) = n. | ||
==Champions== | |||
By translating state names into numbers (such that A=1, B=2, etc.), the 1-symbol champions can be defined in the following way: | |||
* 0R[1,a] = 0RZ | |||
* 0R[n,a] = 0Ra_0R[n-1,a+1] for n>1 | |||
For the n-state champion, start with 0R[n,2]. | |||
[[Category:BB Domains]] | |||
Latest revision as of 15:49, 30 August 2025
BB(n,1) is the Busy Beaver problem for n-state, 1-symbol TMs. It is trivial that Σ(n,1) = 0, as 1-symbol TMs cannot print any non-zero symbols. As any transition back to an already visited state will put the machine in an infinite loop, the most effective halting strategy is to pass through the states one by one, halting only in the final state, thus making BB(n,1) = n.
Champions
By translating state names into numbers (such that A=1, B=2, etc.), the 1-symbol champions can be defined in the following way:
- 0R[1,a] = 0RZ
- 0R[n,a] = 0Ra_0R[n-1,a+1] for n>1
For the n-state champion, start with 0R[n,2].