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.
BackTracker
Now for each state-symbol pair that needs to be checked (in this case just the one), do the following:
  • Construct a local tape configuration which must exist in order for the machine to perform this transition. As the semantics of our tape representation, we use a string of symbols as the characters on the tape. A character indicating the current state is indicated as a subscripted character next to the tape symbol which is located at the current read head. For this particular case, the machine must be in state 0, reading a 1 and therefore the tape is represented as 10
  • For each transition terminating in the state of the state-symbol pair above, do the following:
    • Construct a local tape configuration such that a) the transition in question will be performed on this tape, and b) after the transition is performed, the local tape matches the local tape configuration specified above (i.e. the tape is in such a state that it will execute the halting transition.
    • If such a tape cannot possibly be created, stop searching this leaf node: it is not possible to reach a halting state through this transition.
    • Else continue "backtracking" in the same manner, iterating through all possible transitions that terminate in the state of this particular state-symbol pair.
  • Continue backtracking in each case until an arbitrarily chosen step limit. If any case ends in reaching the step limit, then it may be possible to reach some halting condition and the proof fails. Otherwise, if every case is shown to be an impossibility, the machine is classified as a backtracking non-halter and the proof succeeds.
References
Machlin and Stout. "The Complex Behavior of Simple Machines" Physica D 42 (1990). pp. 85-98
Non Halt Detection
Project Components
Current Champions
n B(n) b(n) O(n) o(n)
1 1T 1T 1T 1T
2 2T 3T 2T 3T
3 3? 13R 3O 13R
4 5? 31R 8O 37R
5 11? 57R 15O 111O
6 25M 255M 239R 41606R
7 196M 13682M

8 672M 198339M


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

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