The Busy Beaver Problem
A NEW MILLENNIUM ATTACK
Nonproductive Transitions
Machines exhibiting one of the following two behaviors are classified as nonproductive machines. These machines are provably equivalent to some other machine in the tree and can therefore be removed from consideration:
Simple Nonproductive Transition (s:s transition)
Consider a machine that contains a transition as defined on the left below from i to j. Such a transition reads a symbol s and then writes the same symbol back onto the tape. It can be shown that a machine which contains such a transition, and therefore a sequence such as i,j,k below, is functionally equivalent to another machine in the tree, which in place of the structure to the left, instead contains the state/transition definition to the right.
Simple Nonproductive Transition
Complex NonproductiveTransitions (s:s' -> s':s transition)
Another type of nonproductive transition takes the two part form as specified to the left below. Successive transitions read an original symbol, write an auxiliary symbol, and then proceed to rewrite the original symbol in the same location. Such a machine is provable equivalent to one with the transitions re-defined to those on the right and therefore need not be considered.
Complex Nonproductive Transition
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