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 an email if you are interested or have any questions.

Required skills:

You should

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.