The Busy Beaver Problem
A NEW MILLENNIUM ATTACK
|
Mirror Machines
The two machines pictured below are
not identical, and they are not isomorphic. Rather, for each move
transition in one machine, the other specifies the same
transition, just with the oppositve movement. All write
transitions are identical. As a result, when one machine moves
right, the other moves left and vice versa. It is easy to see that
these two machines will be equally as productive but will behave
in a mirrored fashion to one another. There is no need, therefore,
to consider both machines.
Solution: Mirror Machines
The solution to eliminating mirror
machines is actually quite simple. By simply forcing the first
move to always be to the right, it is impossible to generate any
mirror machines. In addition, the completeness of the search
remains in tact because for any machine that would have been
produced if its first move was a left, its mirror machine is
guaranteed to be enumerated at some point by the tree. Combined
with the Empty tape and nonproductive transition filters, this
leaves us with the following initial search tree:
|
Optimization Filters
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 |