A Turing Machine Simulator

March 27, 2009

A turing machine is a hypothetical computer, invented in 1936 by the British mathematician Alan Turing, that can evaluate any computable function. Though hypothetical, turing machines play a large role in computer science. Many variants of turing machines have been devised; the purpose of this exercise is to build a simulator for a particular type of turing machine.

The hardware of our turing machine consists of a read/write head and an infinite tape divided into cells that passes across the read/write head. Each cell on the tape contains a symbol, which we take as an ascii character; there is a special blank symbol that is present in all cells which are not yet written. The read/write head can see one cell at a time, read its contents, and write a new symbol (possibly the blank symbol) to the cell.

The software of our turing machine consists of a table encoding a transition function and a state register that maintains the current state. In our machine, states are numbered with non-negative integers; the machine always starts in state zero, and halts if it enters a negative-numbered state. The program being executed by the turing machine is encoded in the transition function, which takes two inputs, the current state and the symbol in the current cell, and then writes a new symbol (or the same symbol, or the special symbol blank) in the current cell, then either moves the read/write head one cell to the left or one cell to the right or remains in the same place, then resets the state to a new state. The transition function is thus encoded in a table of 5-tuples q1 s1 s2 d q2 where q1 is the current state, s1 is the symbol currently under the read/write head, s2 is the symbol to be written, d is the direction to move the tape, and q2 is the next state to enter.

As an example, consider the tape _ _ _ [1] 1 1 + 1 1 1 1 1 _ _ _. This is our notation for a tape that contains, in the middle of an infinite number of blanks, the nine symbols consisting of three one’s, a plus sign, and five one’s, with the read/write head positioned over the first one; the tape can be considered to model the problem of adding the two numbers three and five. The program

    0 1 1 R 0
    0 + 1 R 1
    1 1 1 R 1
    1 _ _ L 2
    2 1 _ L -1

adds the two numbers and writes _ _ _ 1 1 1 1 1 1 1 [1] _ _ _ as its output.

Write a function that takes a turing-machine program and a tape and simulates the action of a turing machine, writing the final tape as output.

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

%d bloggers like this: