Ryan Avery

Busy Beaver

This application was created by Jacob Babbel and myself in Fall of 2016 as a group extra credit project for CS-361, Theory of Computation. In this project we created a Turing Machine in Java and then set out to tackle the Busy Beaver problem.

The Busy Beaver Game was first described in 1962 by Tibor Rado and deals with computational theory, the halting problem, and complexity theory. Thelarge project picture aim of the game is to create an alphabet for a Turing machine that writes the most characters possible to the tape by using a small number of states, while at the same time ensuring that the Turing machine will eventually halt. A Turing machine that does not halt would not be a valid solution to the Busy Beaver game.

For this project, Jacob and I first created our Turing machine and then set out to create a solution-finding algorithm that would find for us a Turing Machine that would print to the tape the most number of non-zero characters. This was also being done by a number of other groups in the class as a competition for extra credit, in which Jacob and I came in third place.

The starting parameters for our problem were much larger than those that are properly documented (for instance, we used an alphabet of five characters where the 'normal' Busy Beaver game has only two) and for that reason it was hard to compare our results to those that are currently documented for solutions to the Busy Beaver game. We did however find roughly 30 valid solutions in the time that we had to let our algorithm run which was approximately two days on two separate computers.