The Busy Beaver Problem
A NEW MILLENNIUM ATTACK
Simple Loops
Generally speaking, a simple loop Turing machine is one that moves in a general leftward or general rightward direction in some infinite repeatable fashion. In more specific terms, a Turing machine M is classified as a simple loop if the following holds:
  • At some point during execution, the following tape configuration is reached: 0*[C][Xs][Y]0*
    In this notation, C, X, and Y are words of arbitrary length. 0* represents an infinite sequence of 0's, and the machine is in state s with the read head at the right most symbol of word X.
And one of the following sets of properties is true:
  1. The same tape configuration is reached at some later point.
Or
  1. The following tape configuration is reached at some later point: 0*[C][V][Xs][Y]0*
  2. Between these two points the read head never moves past the left edge of the initial X (which would incidentally be the same position as the left edge of the resulting V.
*Note: the above specification outlines a simple loop machine that moves in a generally rightward direction. Mirroring the components of the specification yields the requirements for a generally leftward moving simple loop Turing machine.

The first case is quite simple to grasp. If the tape, read head, and current state are all identical at two different points during execution, it is an obvious infinite loop and will never halt. The second case, however, is not quite as obvious. Let us consider the following example:
Simple Loop Detection Strategy
Simple Loop
In order to detect for a simple loop Turing machine, the machine must be run for an arbitrarily limited number of steps. After each step, the machine is in a particular state and reading a particular symbol on the tape. We compare the current tape to the tape at all previous occurances of the same state, symbol pair. In the execution sequence shown below, the contents of the tape when the machine is in state 4 reading a 1 is compared to the previous occurance of these conditions. All of the components specified in the above definition are identifiable and match. However, in this particular instance, the machine moves in the general leftward direction. Therefore the specification from above is reversed. The final condition is then reversed and we check whether or not the read head ever moves past the right edge of the initial X. It does not, and the machine can therefore be classified as a simple loop non-halter.
Simple Loop Execution
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
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