The Busy Beaver Problem
A NEW MILLENNIUM ATTACK
|
Backtrackers
The idea behind the backtrack non-halt
detection algorithm is to prove that a machine can never reach a
set of conditions in which it does, or could potentially halt
from. With the particular definition used for the Busy Beaver
problem (an n-state machine defined on a binary alphabet),
there are exactly 2n possible state-symbol pairs for which
a transition can be defined. The only possibly way that a machine
can halt is if it reaches a set of conditions (represented as a
state-symbol pair) for which the transition is either a transition
to the halt state, or in the case of partially defined machines,
there is no transition defined at all (in which case a transition
to the halt state can easily be defined). Therefore, the
backtracking algorithm iterates through every state-symbol pair
which has one of these two properties, and "backtracks" to see if
it is possible to reach these conditions. The procedure is as
follows:
Backtracking Algorithm
Consider the machine below. The
backtracking algorithm states that the conditions that must be
checked are those state-symbol pairs for which there is either a
transition to the halt state, or no transition at all. Since this
machine is fully defined, and there is only one transition to the
halt state (in state 0, reading a 1), this is the only condition
that must be checked.
References
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 |