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

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/]