The Busy Beaver Problem
A NEW MILLENNIUM ATTACK
Empty Tape Machines
Consider a Turing machine M that, after one or more transitions, again has a blank (all-0) tape. Let Ci be the state that M is after the last such shift is made. Create a machine M' that is identical to M but starts in state Ci. Clearly, M' will behave exactly as M does. Since M' has a different first transition than does M, M' is non-isomorphic to M and, based on the completeness of normalization, will be generated (possibly by proxy through a machine representing its behaviour) at some time during the generation of the tree. Hence, empty tape machines need not be considered.
Partial Solution: Force First Write 1
Notice that machines whose first action (i.e the action take from the start state when reading a 0) is anything other than "write a 1 on the tape" are empty tape machines. Therefore, by defining the first action taken by any machine to be "write a 1," we can immediately eliminate an enormous number of empty tape machines. The image below shows the expanded root node after applying this optimization.
Pruned Normalization Tree
Remaining Solution: Empty tape detection
Of course in addition to all machines which do not have a first write 1, we also eliminate any other empty tape machines which fit the above specification by implementing a generalized solution to the problem. To do this, we subsequent to the first transition, simply track how many non-blank symbols are on the tape; if this number ever reaches 0, then we discard the machine and its successors in the tree as blank-tape machines. Since the first move has been defined to be "write a 1", we are assured that all blank-tape machines have been eliminated from consideration.
Optimization Filters
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