Results 1 to 2 of 2

Math Help - Urgent Help Needed! Hard problem!

  1. #1
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1

    Urgent Help Needed! Hard problem!

    "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.
    Last edited by CaptainBlack; May 11th 2006 at 10:19 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by fifthrapiers
    " Explain why BB(n) >= (n-1).
    Consider the program of n steps:

    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Incredibly Hard MALTHUS Problem Help Needed
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: October 25th 2009, 10:34 PM
  2. Replies: 3
    Last Post: February 5th 2009, 11:56 AM
  3. Homework for calculus thats hard URGENT
    Posted in the Calculus Forum
    Replies: 4
    Last Post: March 3rd 2008, 12:40 AM
  4. Help Needed Urgent
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: December 8th 2006, 06:05 AM
  5. Urgent help needed with linear algebra problem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: June 13th 2005, 10:32 AM

Search Tags


/mathhelpforum @mathhelpforum