Programming Praxis

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