Busy Beaver

June 24, 2014

Since we wrote a turing machine simulator in a previous exercise, this is simple; all we need to do is write the code for the beaver. Here’s the 3-state, 2-symbol beaver; we are using spaces and stars instead of zeroes and ones:

(define bb3 '(
  (0 #\space #\*     right  1)
  (0 #\*     #\*     right -1)
  (1 #\space #\space right  2)
  (1 #\*     #\*     right  1)
  (2 #\space #\*     left   2)
  (2 #\*     #\*     left   0)))

As a reminder, the machine is a list of five-tuples, with the current state and current symbol in the first two slots, the character to be written in the third slot, the direction to move the tape in the fourth slot, and the new state in the fifth slot; the machine starts in state zero and halts when the state becomes negative. Here’s the small driver program along with the output, six stars after fourteen steps:

> (define (beaver bb)
    (turing (make-prog bb)
            (make-tape "" 0)))
> (beaver bb3)
0 0 (* right 1) () ()
1 1 (  right 2) (*) ()
2 2 (* left 2) (*  ) ()
3 2 (* left 2) (*) (*)
4 2 (* left 0) ()*(* *)
5 0 (* right 1) () (* * *)
6 1 (* right 1) (*)*(* *)
7 1 (* right 1) (* *)*(*)
8 1 (* right 1) (* * *)*()
9 1 (  right 2) (* * * *) ()
10 2 (* left 2) (* * * *  ) ()
11 2 (* left 2) (* * * *) (*)
12 2 (* left 0) (* * *)*(* *)
13 0 (* right -1) (* *)*(* * *)
14 -1 final (* * *)*(* *)

You can see the whole thing at http://programmingpraxis.codepad.org/6XlJrVvZ.

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 635 other followers

%d bloggers like this: