Project 2: Second Annual Busy Beaver Competition

Selmer Bringsjord

All groups will compete to see which can produce the most productive 8 state machine, i.e., which can come closest to p(8). (Perhaps an 8-state busy beaver will be found!) Any and all mathematical and engineering techniques are fair game in this competition, including: representing Turing machines as tuples for simulation outside of Turing's World, use of supercomputers (and connection machines, analog machines, etc.), dedicated hardware, genetic algorithm-powered search through the space in question, prayer, lottery-winning-level luck, etc.

The winning team will receive an expense-paid "Wing Night" dinner at Eldorado. (The winning team must eat lunch on the day their prize is to be claimed).

You will certainly want to carefully read Chapters 3 and 4 in Boolos and Jeffrey's Computability and Logic. Also, it would be prudent to have at least one group member read Rado's original proof and the Scientific American article which includes specification of Uwe Schult's fascinating machine (seen in class). Both of these papers are on reserve.

Please note that our machines are of the 4-tuple variety (not the 5-tuple scheme) as in Turing's World and Boolos and Jeffrey, and that input/output conventions are as specified in Boolos and Jeffrey. In particular, there can be no intervening blanks in the string of stars generated, and the read/write head must come to rest on the leftmost star.

A number of relevant Turing Machines (in "Turing's World") are available through my web site, including the two from the first competition which served to prove that p(7) is greater than or equal to 32. Obviously, minor changes to either of these machines will establish that p(8) is greater than or equal to 33.

Due February 27.