The Busy Beaver Problem
A NEW MILLENNIUM ATTACK
|
Tree Normalization
In order to accomplish our goal of
categorizing every machine in the search space, an effective
enumeration strategy must be put in place in order to minimize the
computation required while maintaining the completeness of the
search. The solution that we have implemented is a generative
method known as tree normalization. With this approach, we can
completely avoid generating certain types of redundant machines.
Consider the machines represented below:
Redundancy: Isomorphic Machines
The Turing machines illustrated below
are identical to one another except that states 2 and 3 have been
interchanged. Clearly, the machines are functionally equivalent.
For any n-state Turing machine there are n!
isomorphic machines (since there are n! permutations of
the n state-numbers), but we need to consider only one of
these since their behavior will be identical.
Redundancy: Unused-State Machines
This Turing machine is a 6-state
machine but only four of the states are reachable (i.e. because
there are no transitions terminating in either state 4 or 5). For
every n-state machine that has 1 unreachable state, there
is an equivalent machine with n - 1 states, so no such
machines need to be considered for our search to be exhaustive.
Solution: Tree Normalization
Schema
In order to eliminate the above
redundancies in our enumeration strategy, we have chosen to employ
a tree normalization solution. The general idea is as follows: The
root node of the tree contains a single-state machine with no
transitions defined. This machine is consequently run on an
infinite, blank tape. Clearly, it will do nothing, as no
transitions are defined. However, we consider this a "partial
machine" as the machine halted, but not in the halting state. The
conditions under which it halted therefore, are not halting
conditions, but rather oppurtunities to create additional
transitions. In the case of the root node, it halts in state 0,
reading a 0 on the tape. Therefore, we create child machines, each
of which contains a transition for the case in state 0, reading a
0. We enumerate all possible transitions for this case to all
possible existing states, as well as to one of the remaining
unused states (if the number of currently used transitions is less
than n for which we are calculating BB(n)). The
child machines are then pushed onto a stack, and successfully
popped off, with the above general procedure applied to each until
all possible machines have been defined.
Additional Filters
In addition to the specifics of the
machine enumeration strategy, there are also additional filters
which can be implemented in the procedure to weed out even more
redunancies in the search space. These are as follows:
|
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 |