CST Part II / Diploma
Student Project Suggestion 2002
This project was successfully done by Richard Griffiths, Trinity College,
2002/2003, who received a Data Connection Prize for an Outstanding Dissertation!
Richard Griffiths, 2003, Computing the Uncomputable,
CompSci Tripos Part II dissertation
Computing the Uncomputable
The Busy Beaver function Sigma(N) (due to T. Rado 1962) is a famous example
of an uncomputable function. It is defined as the function which maps N
to the maximum number of 1's produced by any Turing machine with N states
which halts when run on an initially empty tape. It can easily be shown
that this function grows too quickly to be computable. Nevertheless, it
is possible to compute values of the function for very small N, and it is
certainly possible to compute lower bounds of the function in general. In
fact, Sigma(N) is known for N<=5:
Sigma(1) = 1
Sigma(2) = 4
Sigma(3) = 6
Sigma(4) = 13
Marxen et al. have computed some impressive lower bounds on Sigma(5)
(>=4098) and Sigma(6) (>1.29*10^865).
The Busy Beaver problem has a natural analogue in register machines:
what is the largest number remaining in any register after a halting run
of any register machine with N instructions and initially empty registers?
In March 2002, I organised a Register Machine Busy Beaver Contest amongst
four CST IB students, and the challenge was to find a good Busy Beaver
register machine with N=12 instructions. The winning entry was a register
machine which produced the number 2^65536 - 4. In the meantime, a competition
that I held in a puzzle newsgroup resulted in a register machine which produced
a much larger number -- approximately 4^(4^(...4)..) (exponential tower
of height 18, found by Ortwin Gasper, March 2002).
As far as I know, no research has ever been conducted on the Busy Beaver
problem for register machines. The aim of this project would be to write
a program which tries to compute values of the Busy Beaver function for
register machines (for very small N). The best idea would probably be to
adopt the brute force idea of Marxen et al. used for computing lower bounds
for the Turing machine problem. The first step would be to invent a canonical
representation for register machines to cut down the vast number of register
machines with N states, many of which are trivially equivalent. We also
need a register machine simulator to run the enumerated register machines,
but the simulator should act like an optimising register machine compiler,
e.g. r0++ --> r0++ should be optimised to r0:=r0+2. And
finally, you will have to investigate and implement clever methods to determine
non-termination of register machines automatically, e.g. if a configuration
is encountered twice.
The project is quite open-ended and extensible (e.g. a graphical RM-simulator),
and I also welcome any suggestion on variants of this project. Send me
if you are interested or have any questions.
- have enjoyed the IB Computation Theory course (especially the part
about register machines)
- be mathematically inclined and enjoy solving puzzles
- have strong programming skills (any language including Java is
See Marxen's page
for more resources on the Turing Machine Busy Beaver problem. You should
definitely read Marxen's paper "Attacking the Busy Beaver 5" on that page.