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.

About these ads

Pages: 1 2

2 Responses to “Programming the Turing Machine”

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

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

%d bloggers like this: