A Turing Machine Simulator

March 27, 2009

We begin by considering the tape, which we store as a pair containing the left half of the tape (before the current cell) in reversed order in the car and the right half of the tape (the current cell, and everything to its right) in the cdr. The infinite blank ends of the tape are represented as a pair with a #\space in the car and pointer to itself in the cdr, created by set-cdr!. Thus, a blank tape is created by:

(define blanks
  (let ((x (list #\space)))
    (set-cdr! x x)
    (cons x x)))

Utility functions read or write the current cell and move the tape left or right:

(define (read-cell tape) (cadr tape))

(define (write-cell chr tape)
  (cons (car tape) (cons chr (cddr tape))))

(define (move-left tape)
  (cons (cdar tape) (cons (caar tape) (cdr tape))))

(define (move-right tape)
  (cons (cons (cadr tape) (car tape)) (cddr tape)))

The make-tape function creates a new tape with a list of characters given as a string and the zero-based index into that string that is the current cell. For instance, the tape that is the subject of the addition problem is created by (make-tape "111+11111" 0). By convention, the tape is initialized with the read/write head at the left-most non-blank cell, so the index is normally 0.

(define (make-tape chrs curr)
  (define (insert-cell chr tape)
    (cons (car tape) (cons chr (cdr tape))))
  (let loop ((curr curr) (chrs (reverse (string->list chrs))) (tape blanks))
    (cond ((= curr -1) (move-left tape))
          ((null? chrs) (loop (- curr 1) chrs (move-right tape)))
          (else (loop curr (cdr chrs) (insert-cell (car chrs) tape))))))

The show-tape function returns the non-blank portion of the tape surrounding the current cell and the index of the current cell:

(define (show-tape tape)
  (let loop ((tape tape) (k -1))
    (if (char=? (read-cell tape) #\space)
        (let loop ((tape (move-right tape)) (chrs '()))
          (if (char=? (read-cell tape) #\space)
              (values (list->string (reverse chrs)) k)
              (loop (move-right tape) (cons (read-cell tape) chrs))))
        (loop (move-left tape) (+ k 1)))))

Now that we have some functions to handle the tape, we can look at the program, which is given as a list of 5-tuples; the program given above to add two numbers looks like this:

(define adder '(
  (0 #\1     #\1     right 0)
  (0 #\+     #\1     right 1)
  (1 #\1     #\1     right 1)
  (1 #\space #\space left  2)
  (2 #\1     #\space left  -1)))

A program is stored in a hash table indexed by state/symbol pair. Since we assume ascii, there are 256 possible symbols on the tape, so the hash function multiplies the state by 256 and adds the ordinal value of the symbol:

(define (hash-state-symbol key)
  (+ (* (car key) 256) (char->integer (cadr key))))

The make-prog function takes a program expressed as 5-tuples and returns the program stored in a hash table; it uses make-hash, take, and drop from the Standard Prelude:

(define (make-prog tuples)
  (let ((prog (make-hash hash-state-symbol equal? #f 97)))
    (do ((tuples tuples (cdr tuples)))
        ((null? tuples) prog)
      (prog 'insert (take 2 (car tuples)) (drop 2 (car tuples))))))

Now we are ready to simulate the turing machine. The turing function takes a program and a tape, sets the initial state to 0, then performs each command as it arrives, halting and printing the current contents of the tape when the state becomes negative. The action at each step is to read the symbol at the current cell, lookup the action that corresponds to the current state/symbol key, write the new symbol at the current cell, move the tape as directed, and reset the current state.

(define (turing prog tape)
  (let loop ((state 0) (tape tape))
    (if (negative? state) (show-tape tape)
      (let ((cmd (prog 'lookup (list state (read-cell tape)))))
        (loop (caddr cmd) (case (cadr cmd)
          ((left) (move-left (write-cell (car cmd) tape)))
          ((right) (move-right (write-cell (car cmd) tape)))
          (else (write-cell (car cmd) tape))))))))

Running the adder in the example looks like this:

> (turing (make-prog adder) (make-tape "111+11111" 0))
"11111111"
7

You can see the program at http://programmingpraxis.codepad.org/bZje3rH9.

About these ads

Pages: 1 2

4 Responses to “A Turing Machine Simulator”

  1. veer said

    Here is my try

  2. veer said

    There should be a preview option.
    Here’s the second try,http://codepad.org/pb3pJtxl

  3. I decided to interpret the Turing Machine as an object, so I made a class for it which has methods that simulate actually operating with a physical machine.

    I’ve included the entire class, and some test code that runs the function you posted.

    Cheers!

    class Turing_Machine():
    def __init__(self, input_tape=[], function_matrix=[]):
    “””Constructs a functional Turing Machine with the optional inputs.”””
    self.set_input_tape(input_tape)
    self.set_transition_matrix(function_matrix)
    print
    print “Turing Machine created as: ”
    print
    print self

    direction = ”

    # hardware
    head_position = 0
    input_tape = []

    # software
    state_register = 0
    “””a list of lists with indices as states demarking a list with form
    [symbol(being read 1 or 0 or _), symbol(to write; 1 or 0 or _), d(direction to move tape; R or L),
    state(to enter; 0 or integer, -1 to end)]“””
    transition_function = []

    # output
    output_tape = []

    def run(self):
    “””Runs the Turing Machine. (Doesn’t print)”””
    self._place_head()
    self._actual_compute()
    self.output_tape.insert(0,’_’) # for looks
    self.reset()

    def set_transition_matrix(self, matrix):
    “””Takes in a list of 5-length lists, puts them into the format that we need,
    into self.transition_function. Could make this move intuitive to input?”””
    for function in matrix:
    self._add_transition_line(function)

    def set_input_tape(self, list):
    “””Takes in a list (starting with an arbitrary number of _) to be the input to the program.
    Could make this take an easier input (a string? space seperatd, null terminated?)”””
    self.input_tape = list

    def clear_matrix(self):
    “””Resets the transition function.”””
    self.transition_function = []

    def clear_input(self):
    “””Resets the input_tape”””
    self.input_tape = []

    def reset(self):
    “””Sets the machine to a naive state (but keeps function matrix and input tape)”””
    self.state_register = 0
    self.head_position = 0

    def _place_head(self):
    “””Places the head on the first non-blank index of the input_tape”””
    for i in range(len(self.input_tape)):
    if self.input_tape[i] != ‘_':
    self.head_position = i
    self.input_offset = i #how many blanks we had to skip (for output formatting)
    break

    def _add_transition_line(self, line):
    “””Adds a transition statement to the function matrix self.transition_function. One line at a time. Takes in an array of length 5.”””
    if line[0] >= len(self.transition_function): #checks to see if state number is already in the function marrix
    self.transition_function.append([]) #if not, add a state array
    self.transition_function[line[0]].append(line[1:]) #append the rest of the function to the matrix (minus the state)

    def _actual_compute(self):
    “””Recursively computes the output of the transition table applied to the input, writes that to the output array.”””
    for function in self.transition_function[self.state_register]:
    if self.input_tape[self.head_position] == function[0]:
    if self.direction == ‘L': #if we’re moving backwards, the output tape already has that position, so don’t append anything to the output tape array
    self.output_tape[self.head_position-self.input_offset] = function[1]
    else:
    self.output_tape.append(function[1]) #if we’re moving right, we need to append to the output tape array
    self.state_register = function[3] #sets the next state
    self.direction = function[2] # sets the next direction
    if self.direction == ‘R':
    self.head_position += 1 #moves the head to the right if dir = ‘R’
    else: #otherwise, it’s left, so move left
    self.head_position -+ 1
    if self.state_register >= 0: #if the state isn’t negative, compute again
    self._actual_compute()

    def __str__(self):
    “””Basic printing of the Turing Machine. Could be improved.”””
    return “program: ” + str(self.transition_function) + “\ninput: ” + str(self.input_tape) + “\noutput: ” + str(self.output_tape) + “\n”

    def _test_machine():
    _ = ‘_’
    plus = ‘+’
    R = ‘R’
    L = ‘L’
    matrix = [ [0, 1, 1, R, 0], [0, plus, 1, R, 1], [1, 1, 1, R, 1], [1, _, _, L, 2], [2,1, _, L, -1] ]
    input_tape = [_,_,_,1,1,1,'+',1,1,1,1,1,_,_,_]
    tm = Turing_Machine(input_tape, matrix)
    tm.run()
    print tm

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

%d bloggers like this: