Consider the program of n steps:Originally Posted by fifthrapiers
step1:Set X=X=1
:
:
step n-1:Set X=X+1
step n:stop
where steps 1 to n-1 are all "Set X=X+1", then the score
of this program is n-1, hence BB(n)>=(n-1).
RonL
"Open Mathematical Problem: The Busy Beaver N-game. In this version we eliminate the Input X statement and assume instead that every variable begins with the value 0. Then we can do the equivalent of reading in a positive integer i for X by writing i consecutive "X := X + 1" statements. The score of a TRIVIAL program is defined to be the sum of the values of all variables when the program stops or 0 if the program never stops. Then the Busy Beaver n-game is the problem of determining a TRIVIAL program with n instructions with the highest possible score among all TRIVIAL programs with n instructions. We call that maximum score BB(n). Thus BB(1) = 0, since the only TRIVIAL program with one line is
Step 1. Stop.
A two-step program could be
Step 1. Set X := X + 1
Step 2. Stop.
Thus BB(2) = 1, since X begins at 0 and is increased only to 1. Explain why BB(n) >= (n-1). Then show that BB(3) = 2 and BB(4) = 3. Find a value of n such that BB(n) >= (n-1); you will need to use at least two variables. Very little is known about the Busy Beaver n-game for even small values of n. It is known that there is no simple function that expresses BB(n) as function of n. It has been shown that BB(20) >= 4^(4^(4^4))"
Thank you!!
Reminder:
There is a simple programming language known as TRIVIAL. In this language only the following 6 types of instructions are allowed:
a.) Input X, a natural number
b.) Go to step # -
c.) Set X := X + 1
d.) If X = 0, then go to step # -
e.) If > 0, then set X := X - 1
f.) Stop.