The Busy Beaver Problem : A NEW MILLENNIUM ATTACK

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.

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.

Optimization Filters

Tree Normalization
Nonproductive Transitions
Empty tape machines
Mirror machines

Project Components

Tree Normalization
Non Halt Detection
Distributed Computing

Current Champions

n	*B(n)*	*b(n)*	*O(n)*	*o(n)*
1	1^T	1^T	1^T	1^T
2	2^T	3^T	2^T	3^T
3	3^?	13^R	3^O	13^R
4	5^?	31^R	8^O	37^R
5	11^?	57^R	15^O	111^O
6	25^M	255^M	239^R	41606^R
7	196^M	13682^M
8	672^M	198339^M

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

^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