The Busy Beaver Problem
A NEW MILLENNIUM ATTACK
|
Nonproductive Transitions
Machines exhibiting one of the
following two behaviors are classified as nonproductive machines.
These machines are provably equivalent to some other machine in
the tree and can therefore be removed from consideration:
Simple Nonproductive Transition
(s:s transition)
Consider a machine that contains a
transition as defined on the left below from i to j. Such a
transition reads a symbol s and then writes the same symbol back
onto the tape. It can be shown that a machine which contains such
a transition, and therefore a sequence such as i,j,k below, is
functionally equivalent to another machine in the tree, which in
place of the structure to the left, instead contains the
state/transition definition to the right.
Complex NonproductiveTransitions
(s:s' -> s':s transition)
Another type of nonproductive
transition takes the two part form as specified to the left below.
Successive transitions read an original symbol, write an auxiliary
symbol, and then proceed to rewrite the original symbol in the
same location. Such a machine is provable equivalent to one with
the transitions re-defined to those on the right and therefore
need not be considered.
|
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 |