Busy Beaver
Let us define the productivity of a binary alphabet Turing-machine to
be the number of 1's that a halting Turing machine prints out when started
on an empty tape. The Busy Beaver function BB(n) is now defined as the
maximum productivity of a Turing-machine with n states. Any machine with
n states whose productivity equals BB(n) is called a Busy Beaver. The
Busy Beaver problem is to find these Busy Beavers for various values of
n.
The Busy Beaver function was formulated and shown to be Turing-uncomputable
by Tibor Rado in 1962. However, for low values of n, BB(n) can be found.
Finding these values creates interesting engineering challenges (how
to find Busy Beavers in the vast space of all possible computer programs),
and also raises fundamental philosophical questions (what are the theoretical
boundaries of computation and demonstration?). To address these challenges
and questions, the Busy Beaver Project: A New Milennium
Attack was created as a multidisciplinary project between the departments
of Cognitive Science and Computer Science.
As of to date, the project has born a number of fruits. Undergraduate
students Kyle Ross and Owen Kellett were instrumental in confirming
and breaking a number of Busy Beaver records in the 4-tuple Turing-machine
realm. At the same time, we seem to have quickly reached an epistemological
'wall' where it has become an enormous challenge to prove that some
Turing-machine is in fact a Busy Beaver, which is very interesting from
a philosophical and cognitive point of view.
|
