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][Vs]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][Vs]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
Current Champions
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 |