The Most Powerful Computer You'll Never Own

Inspired by the movie the Imitation Game, I just had build my own Turing Machine (I know, I should have built one of these! Some day). While folks have built actual physical machines, I took the programmer's way out and made mine strictly virtual.

A Turing Machine is the theortical device Alan Turing devised in his 1936 paper on computability. To this day, Computer Science students are made to do battle with this machine and the theories that stem from it.

While it's been years since I've done any CS homework that involved Turing Machines, I can't recall actually ever implementing one. What a shame.

The web is filled with such simulators including: here, here and here. These were invaluable for refreshing my memory as to how a Turing Machine operates.

Implementing a Turing Machine was oddly satisfying. One has to contend with the fact that a program handed to a Turing Machine may never complete. I dealt with this by allowing the user to execute the machine in terms of blocks of cycles. So you create the machine, run it for 100 cycles, and if you want, run it 100 more.

Here's the code to create a machine. The program is actually Alan Turing's first example:

(define r1 '(((b _) (c 0 >))
             ((c _) (e _ >))
             ((e _) (f 1 >))
             ((f _) (b _ >))))
(define tm1 (make-tm 'b '() '() r1))

The rules specified by r1 are in the format:

 (((current-state current-symbol) (new-state new-symbol new-direction))
  ...)

Invoking make-tm creates the new Turing Machine. You provide as arguments the initial state, initial tape-contents, list of halting states and the transition rules.

Once you've got the machine (tm1, above), you can invoke it with an integer to say how many cycles of the machine should execute (e.g., (tm1 10)).

Scheme truly shined as a host language: I was trivially able to make the machine operate on arbitrary states and tape contents. Also sexpr's were ideal for defining the state transition rules.

All of this may seem fairly unimpressive until you ponder this thought:

However odd it may sound for so simple a machine, the Turing Machine is the most powerful computing model known to computer scientists. In this context, "powerful" refers only to what it is capable of doing, not to how fast or efficiently it does it. It has been proven that a TM is capable of performing any computation that a modern computer can, given enough time. Infact, it is technically MORE powerful than modern computers, since it has no storage limitations.

Here's the complete source code for my simulator.

Update: Programming Praxis tackled the Turing Machine almost 5 years ago. I've updated my code below with their example.

; A Turing Machine Impl

(define (range lower upper)
 (if (>= lower upper) '()
     (cons lower (range (+ 1 lower) upper)))) 

(define (show . words)
 (for-each display words))

(define tape-cell '#(_))
(define tape-padding '#(_ _ _ _ _))

(define (make-tape contents)
 (cons 0 (vector-append (list->vector contents) tape-padding)))

(define (tape-head t)
 (car t)) 
(define (tape-items t)
 (cdr t))
 
(define (tape-read t)
 (vector-ref (tape-items t) (tape-head t)))
 
(define (tape-write t x)
 (vector-set! (tape-items t) (tape-head t) x)
 t)
 
(define (tape-move t direction)
 (let ((index (+ (tape-head t)
                 (case direction
                  ((< L) -1)
                  ((> R) 1)
                  ((- N) 0)
                  (else (error "Unknown tape movement: " direction))))))
  (cond ((= index -1)
         (set-cdr! t (vector-append tape-cell (tape-items t)))
         (set! index 0))
        ((= index (vector-length (tape-items t)))
         (set-cdr! t (vector-append (tape-items t) tape-padding))))
  (set-car! t index)
  t))

(define (display-tape t)
 (for-each (lambda (i)
            (let ((v (vector-ref (tape-items t) i)))
              (cond ((= i (tape-head t))
                     (show "[" v "]"))
                    (else (show v)))
              (show " ")))
           (range 0 (vector-length (tape-items t)))))

(define (tm-find state tape rules)
 (let ((needle (list state (tape-read tape))))
  (let loop ((rules rules))
   (cond ((null? rules) #f)
         ((equal? needle (caar rules)) (cadar rules))
         (else
          (loop (cdr rules))))))) 
            
(define (make-tm initial-state initial-tape halting-states rules)
 (let ((state initial-state)
       (tape (make-tape initial-tape)))
 (lambda (cycles)
  (let loop ((cycle 0))
   (show state ": ")
   (display-tape tape)
   (newline)
   (cond ((= cycle cycles) #t)
         ((member state halting-states) state)
         ((tm-find state tape rules) =>
          (lambda (dest)
           (let* ((new-state (car dest))
                  (new-symbol (cadr dest))
                  (new-direction (caddr dest)))
             (set! state new-state)
             (tape-write tape new-symbol)
             (tape-move tape new-direction)
             (loop (+ 1 cycle)))))
          (else 'no-matching-rules))))))

; Binary Counting - http://aturingmachine.com/examples.php
(define r0 '(((walk  0) (walk  0 >))
             ((walk  1) (walk  1 >))
             ((walk  _) (count _ <))
             ((count 0) (walk  1 >))
             ((count 1) (count 0 <))
             ((count _) (walk  1 >))))
             
(define tm0 (make-tm 'walk '(0) '() r0))

; Turing's First Example 
;  http://en.m.wikipedia.org/wiki/Turing_machine_examples
(define r1 '(((b _) (c 0 >))
             ((c _) (e _ >))
             ((e _) (f 1 >))
             ((f _) (b _ >))))
(define tm1 (make-tm 'b '() '() r1))

; http://programmingpraxis.com/2009/3/27/a-turing-machine-simulator/
(define r2 '(((0 1) (0 1 R))
             ((0 +) (1 1 R))
             ((1 1) (1 1 R))
             ((1 _) (2 _ L))
             ((2 1) (H 1 N))))
(define tm2
 (make-tm 0
         '(1 1 1 + 1 1 1 1)
         '(H)
         r2))