Busy Beaver

June 24, 2014

Yesterday was Alan Turing’s birthday, so today we will write a program for a turing machine.

The Busy Beaver is a turing machine that performs the maximum work for a given configuration of machine; the concept was invented by Tibor Radó in his 1962 paper On Non-Computable Functions. We won’t look at the underlying theory, although it is fascinating if you have the time. Instead, we’ll be content to implement the first few busy beavers. Here are the two-symbol busy beavers for one, two, three and four states, from Wikipedia; the two symbols are 0 and 1, the states are letters A through D plus the halting state H, and the moves L and R are left and right:

  A
0 1RH
1 unused
  A B
0 1RB 1LA
1 1LB 1RH
  A B C
0 1RB 0RC 1LC
1 1RH 1RB 1LA
  A B C D
0 1RB 1LA 1RH 1RD
1 1LB 0RC 1LD 0RA

Your task is to implement the four busy beavers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

3 Responses to “Busy Beaver”

  1. Paul said

    In Python: Codepad. For my hero: Alan Turing.

  2. matthew said

    (I think machine 4 should have 0LC for the 1-B entry there).

    It’s easy to translate Turing Machine programs into Markov programs, so here’s the 3-state machine:

    A0 => 1B
    A1 =>. 1H
    
    B0 => 0C
    B1 => 1B
    
    0C0 => C01
    1C0 => C11
    0C1 => A01
    1C1 => A11
    
    A$ => A0$
    $A => $0A
    B$ => B0$
    $B => $0B
    C$ => C0$
    $C => $0C
    

    and a run:

    ./markov.pl < bb3.txt '$A$'
    $A$
    $A0$
    $1B$
    $1B0$
    $10C$
    $10C0$
    $1C01$
    $C111$
    $0C111$
    $A0111$
    $1B111$
    $11B11$
    $111B1$
    $1111B$
    $1111B0$
    $11110C$
    $11110C0$
    $1111C01$
    $111C111$
    $11A1111$
    $111H111$
    

    And the 4-state machine:

    A0 => 1B
    0A1 => B01
    1A1 => B11
    
    0B0 => A01
    1B0 => A11
    0B1 => C00
    1B1 => C10
    
    C0 =>. 1H
    0C1 => D01
    1C1 => D11
    
    D0 => 1D
    D1 => 0A
    
    A$ => A0$
    $A => $0A
    B$ => B0$
    $B => $0B
    C$ => C0$
    $C => $0C
    D$ => D0$
    $D => $0D
    

    [http://matthewarcus.wordpress.com/2014/01/08/markov-computation/]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 634 other followers

%d bloggers like this: