The Busy Beaver Problem : A NEW MILLENNIUM ATTACK

The Busy Beaver Problem

A NEW MILLENNIUM ATTACK

Alternating Christmas Tree Non-Halters

Alternating Christmas trees are extremely similar to regular christmas trees. The only difference being that the construction of an additional [X] on the tape takes two sweeps across the tape rather than one. See Owen's non-halter presentation for details on the alternating christmas tree detection strategy.

References

Brady. "The Determination of the Value of Rado's Noncomputable Function Sigma(k) for Four-State Turing Machines" Mathematics of Computation Volume 40, Number 162. April 1983, pp 647-665

Machlin and Stout. "The Complex Behavior of Simple Machines" Physica D 42 (1990). pp. 85-98

Non Halt Detection

Non Halters
Backtrackers
Subset Loops
Simple Loops
Christmas Trees
Alternating Christmas Trees
Counters

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