The Busy Beaver Problem
A NEW MILLENNIUM ATTACK
|
Empty Tape Machines
Consider a Turing machine M
that, after one or more transitions, again has a blank (all-0)
tape. Let Ci be the state that M is
after the last such shift is made. Create a machine M'
that is identical to M but starts in state Ci.
Clearly, M' will behave exactly as M does. Since M'
has a different first transition than does M, M'
is non-isomorphic to M and, based on the completeness of
normalization, will be generated (possibly by proxy through a
machine representing its behaviour) at some time during the
generation of the tree. Hence, empty tape machines need not be
considered.
Partial Solution: Force First
Write 1
Notice that machines whose first
action (i.e the action take from the start state when reading a 0)
is anything other than "write a 1 on the tape" are empty
tape machines. Therefore, by defining the first action taken by
any machine to be "write a 1," we can immediately eliminate an
enormous number of empty tape machines. The image below shows the
expanded root node after applying this optimization.
Remaining Solution: Empty tape
detection
Of course in addition to all machines
which do not have a first write 1, we also eliminate any other
empty tape machines which fit the above specification by
implementing a generalized solution to the problem. To do this, we
subsequent to the first transition, simply track how many
non-blank symbols are on the tape; if this number ever reaches 0,
then we discard the machine and its successors in the tree as
blank-tape machines. Since the first move has been defined to be
"write a 1", we are assured that all blank-tape machines have been
eliminated from consideration.
|
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 |