"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.