The Busy Beaver Problem
A NEW MILLENNIUM ATTACK
|
Background - Turing Machines and
what they are
Comprehension of the Busy Beaver
problem requires a conceptual understanding of what a turing
machine is and does. In short, a turing machine is an abstract
model of computation that encapsulates the definition of
computability. More formally, a turing machine is structured with
the following components:
Turing Machines can be easily conceptualized when depicted in a graphical diagram as shown below. Each node in the diagram represents a state and each directed arrow represents an instruction. Each instruction contains a label of the following format: (Read Symbol:Write Symbol,Move Direction). When a machine is in a particular state, the action that it performs corresponds to the "Write Symbol" and "Move Direction" of the instruction in which the "Read Symbol" matches the symbol at the current read head on the tape. The machine then transitions to the state in which the instruction's arrow terminates and repeats the process. The machine halts when it enters an explicitly defined halt state or no instruction can be found given the current state and read head symbol. The execution of the very simple Turing Machine below is shown. The machine operates on an initially infinite tape of all 0's with an alphabet of {0,1}:
*Note: infinite sequences of 0's are truncated from the left and right sides of each tape sequence The Busy Beaver Problem
Considering the definition of a Turing
Machine above, we can now define the Busy Beaver function,
invented by Tibor Rado around 1960. As you may have noticed, it is
quite easy to construct a turing machine that never halts given a
particular piece of input. In fact, it is provably impossible to
define an algorithm which, given a turing machine and an input
tape, can definitively return whether or not that machine halts on
that particular input. This is classicly known as the halting
problem and is what the Busy Beaver is centered around. The Busy
Beaver function is defined as follows:
Clearly, if we had an algorithm that could solve the halting problem than we could very easily devise an algorithm to solve the Busy Beaver problem. This is not the case, however, and the proof of the uncomputability of the Busy Beaver problem can be found here. Variants of the Busy Beaver
Problem
Quadruple vs. Quintuple
Formulation
The Turing machine described above is classified as a quintuple formulation Turing machine. This is so because each instruction contains five pieces of information (current state, current symbol, new state, new symbol, move). During every transition, a write action and a move action is performed before proceeding to the next state. Consider, now, a Turing machine whose instructions are only allowed to perform one action for every transition. An instruction can specify either a new write symbol or a move direction but not both. Such a machine is of the quadruple variety of Turing machines. Quadruple machines and quintuple machines are provably equivalent in expressive power. Halting Type There are two methods of specifying how a Turing machine halts. One is by simply not creating an instruction for a particular state, symbol pair. When the machine encounters these conditions, it has no action to take and will therefore halt. We describe these machines as implicit halt machines. The second method is to create an additional halting state. If the machine makes a transition to this new halt state, it immediately halts. These machines are thus explicit halt machines. It is important to note, for the purposes of studying the Busy Beaver problem, that an n-state Turing machine has n states plus exactly one halt state. The Turing machines considered in our research have the restriction that there can be no outgoing transitions from the halt state---when the machine is in the halt state, it cannot be run any further. Standard Position The definition of the Busy Beaver problem defined above makes no reference to the nature of the tape after the machine has halted beyond strictly the number of 1's that are present. A variant of the problem enforces the additional restriction that a machine can not be considered a Busy Beaver candidate unless the resulting pattern of 1's on the tape is in a contiguous sequence with the read head located at the left-most 1. We call this configuration "standard position" Our Attack
Our Attack focuses on the variants of
the quadruple formulation of the problem as defined above. Most
previous work on the Busy Beaver problem has dealt with some
variant of the binary alphabet quintuple formulation. There has,
however, been some previous study of several of the quadruple
variants:
|
Busy Beaver in a Nut Shell
Consider a binary alphabet Turing Machine
which is given an infinite, blank tape as input. If this machine
halts, we define its productivity as the number of 1's left on the
tape after the machine is run to completion. If it does not halt,
the machine is given a productivity value of zero. Now consider
all of the binary alphabet Turing Machines that have n
states. The machine in this set which has the highest productivity
is called a Busy Beaver, and its productivity is the result of the
Busy Beaver function BB(n).
Busy Beaver Research Team
Bram van Heuveln
Selmer Bringsjord Boleslaw Szymanski Carlos Varela Kyle Ross Owen Kellett Shailesh Kelkar |