BB(n,1): Difference between revisions
Jump to navigation
Jump to search
→Champions: Added champions |
Linked champions, added See also with a link to BB(1,m) |
||
| 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== | == 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: | 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[1,a] = 0RZ | ||
* 0R[n,a] = 0Ra_0R[n-1,a+1] for n>1 | * 0R[n,a] = 0Ra_0R[n-1,a+1] for n>1 | ||
For the n-state champion, start with 0R[n,2]. | For the n-state champion, start with 0R[n,2]. | ||
[[Category:BB Domains]] | [[Category:BB Domains]] | ||
== See also == | |||
* [[BB(1,m)]] | |||
Latest revision as of 12:34, 20 February 2026
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].