## Programming the Turing Machine

### April 3, 2009

`(define multiplier '( ; product = multiplicand * multiplier`

(0 #\1 #\1 left 0) ; move left to blank at left of multiplicand

(0 #\space #\= right 1) ; write equal-sign to mark right end of product

(1 #\1 #\1 right 1) ; traverse to right end of multiplier

(1 #\* #\* right 1) ; traverse to right end of multiplier

(1 #\space #\space left 2) ; found right end of multiplier

(2 #\* #\space left 8) ; outer loop -- terminates at times-sign

(2 #\1 #\space left 3) ; outer loop -- for each digit in multiplier

(3 #\1 #\1 left 3) ; traverse to left end of multiplier

(3 #\* #\* left 4) ; found beginning of multiplicand

(4 #\= #\= right 7) ; inner loop -- terminates at equal-sign

(4 #\1 #\@ left 5) ; inner loop -- for each digit of multiplicand

(5 #\1 #\1 left 5) ; traverse to left end of product

(5 #\= #\= left 5) ; traverse to left end of product

(5 #\space #\1 right 6) ; write new digit at left end of product

(6 #\1 #\1 right 6) ; traverse to next digit of multiplicand

(6 #\= #\= right 6) ; traverse to next digit of multiplicand

(6 #\@ #\@ left 4) ; go to top of inner loop

(7 #\@ #\1 right 7) ; reset digits of multiplicand

(7 #\* #\* right 7) ; traverse to right end of multiplier

(7 #\1 #\1 right 7) ; traverse to right end of multiplier

(7 #\space #\space left 2) ; go to top of outer loop

(8 #\1 #\space left 8) ; erase multiplicand

(8 #\= #\space left -1))) ; erase equal-sign and halt

`> (turing (make-prog multiplier) (make-tape "111*1111" 0))`

"111111111111"

11

You can run this program at http://programmingpraxis.codepad.org/2RPNPlHk.

Pages: 1 2

Thanks so much, it helped greatly with my university test!

https://github.com/ftt/programming-praxis/blob/master/20090327-a-turing-machine-simulator/turing.py#L39