Busy Beaver
Author: Vidie Pong
Reading
Read http://en.wikipedia.org/wiki/Busy_beaver, the following sections:
- The busy beaver game
- The busy beaver function Sigma
- Max shifts function
- Proof of uncomputability of S(n) and Sigma(n) (Sigma(n) was done in class already, so this section should mostly be a review.)
Reading questions
1. What is written in the cells of a "blank" starting tape?
2. How do you score a Turing machine in this context?
3. What is the busy beaver game?
4. What is the difference between an n-state busy beaver and a champion n-state machine?
5. Why must one submit the number of steps to reach a Halt state along with the machine when submitting to the busy beaver game?
6. Do we know if there is only one busy beaver for any given number of steps?
7. Why is the max shifts function equivalent to the max step function?
Pay close attention to the proof outline of S(3)
Lecture Notes
A busy beaver machine, defined by Tibor Rado, is a machine with a two-symbol alphabet (typically {0,1}) that does the most given a doubly-infinite tape of a "blank" tape (i.e. all 0's) and halts.
The busy-ness of the function can be measured in the number of 1's written on the tape once it has halted (Sigma(n)) or the number of steps it took to halt (S(n)).The busy beaver function Sigma(n) takes the number of states a machine has, n, and outputs the highest score a machine with n states can reach. Sigma(n) is not known for n>4.
Class exercise
Busy beavers for n = 1,2, and 3 are given below. As a class, we'll reason out what happens to a blank tape and figure out what the Sigma score for each busy beavers is.
Turing Machine for 1-state Busy Beaver:
a0 -> h1r
Turing Machine for 2-state Busy Beaver:
a0 -> b1r a1 -> b1l b0 -> a1l b1 -> h1r
Turing Machine for 3-state Busy Beaver:
a0 -> b1r a1 -> h1r b0 -> c0r b1 -> b1r c0 -> c1l c1 -> a1l
Try to come up with the 4-states busy beaver with your table. Report results after 15 minutes. (Answer in sub-page.)
End of Exercise
Note: The score of each busy beavers is
Sigma(1) = 1
Sigma(2) = 4
Sigma(3) = 6
Sigma(4) = 13
No proven busy beaver for n=5 has been found yet, but the current champion has a score of 4098. As you can see, Sigma(n) grows really quickly. In fact, so quickly it has been proven to grow faster than any computable function.
Applications
As seems to be a theme in this class lately, a whole class of problems could be solved if only we could solve the busy beaver problem.
Example:
Goldbach's conjecture states that every even integer greater than 2 can be expressed as a sum of two primes.
Suppose you have a program that tests every even number greater than 2 sequentially to see if it is a sum of primes. If Goldbach's conjecture is true, our program will never halt.
Now suppose we simulate this program on an n-state Turing machine, M. If he knew S(n), then we would know that if we run M, and it runs for more steps than S(n), it will never halt because S(n) is the maximum number of steps a halting n-state Turing machine can have before halting. Therefore, we could prove or disprove Goldbach's conjecture.
Unfortunately, we don't know S(n), and never will (see Proof of Uncomputability), so that method isn't viable.
Quiz Questions
1. If we could solve S(n), could we solve the Halting Problem? Why, or why not?
2. Why is the proof used to establish that S(3)=21 not used for other values of n?
Homework
Create a visuallization of 4-state busy beaver in the programming language of your choice to get a better understanding of this machine. It should be equivalent to the following:
