The Busy Beaver Problem : A NEW MILLENNIUM ATTACK

The Busy Beaver Problem

A NEW MILLENNIUM ATTACK

Christmas Tree Non-Halters

In a general sense, a christmas tree non-halter sweeps back and forth across the tape in a repeatable manner. More specifically, at some point during machine execution, the tape has the following structure: 0*[U][V_s]0* (see the discussion on simple loops for an explanation of this particular tape represenation). Then at some later point, the tape has the structure: 0*[U][X][V_s]0*. This does not complete the proof however as it must be shown that the machine progresses through a series of specific transformations such that additional [X]'s are repeatedly added to the middle of the structure ad infinitum. See Owen's non-halter presentation for details on the 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