The Busy Beaver Problem
A NEW MILLENNIUM ATTACK
Subset Loops
A Turing machine M is classified as a subset loop if the following properties are true:
  • There is a set of states S such that a transition from S is defined on every symbol in the alphabet (in this case just {0,1}).
  • Every transition defined from a state in S terminates in another state in S
  • At some point during execution, the machine enters one of the states in S
Consider the machine below:
Subset Loop
It is easy to see that the above machine satisifes the first two conditions specified in the definition above. Each state in the circled region has every transition defined to some other state within the region. At first glance, however, it appears that the third condition requires some additional checking in order to confirm whether or not a machine is in fact a subset loop. This is not the case however as we revert the reader back to the discussion of our machine enumeration strategy. It is explained here that redundant "unused state" machines are never generated in the search tree. This is because when creating children machines in the search tree, a transition is never defined unless the machine reaches those conditions at some point during execution. As a result, if a subset of states such as the one above exists, every transition in the subset is guaranteed to have been used at some point during execution. If this is the case than the third condition stated above trivially follows.
Non Halt Detection
Project Components
Current Champions
n B(n) b(n) O(n) o(n)
1 1T 1T 1T 1T
2 2T 3T 2T 3T
3 3? 13R 3O 13R
4 5? 31R 8O 37R
5 11? 57R 15O 111O
6 25M 255M 239R 41606R
7 196M 13682M

8 672M 198339M


n P(n) p(n) R(n) r(n)
1 1T 2T 1T 2T
2 2T 4T 2T 4T
3 4R 14R 4R 14R
4 7R 32R 8R 38R
5 16R 112R 16R 112R
6 163R 27174R 240R 41607R

RSet by present RPI effort
MSet by Machado and Pereira
OSet by Oberschelp, et al.
TTrivial records
?Unknown origin

Also note: A solid yellow background indicates records have been explicitly confirmed by the present effort. A faded yellow indicates relative confidence but not yet an explicit proof.
Busy Beaver Research Team
Bram van Heuveln
Selmer Bringsjord
Boleslaw Szymanski
Carlos Varela
Kyle Ross
Owen Kellett
Shailesh Kelkar