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:
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
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 |