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:

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. 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 1₀
• 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.

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