Turing Machine

turing.py

class TapeException(BaseException):
    pass

class Machine:
    def __init__(self, state, tape, machine, negsize=1):
        self.state = state
        self.tape = tape
        self.machine = machine
        self.negsize = negsize

    def run(self):
        pos = 0
        try:
            while (self.state, self.tape[pos]) in self.machine:
                m = self.machine[(self.state, self.tape[pos])]
                self.tape[pos] = m[0]
                if m[1] == "R":
                    pos += 1
                else:
                    pos -= 1
                self.state = m[2]
                if pos >= len(self.tape) - self.negsize or pos < -self.negsize:
                    raise TapeException
        except TapeException:
            print "Ran out of tape."

def main():
    # Prints 4 1s to the tape in positions -2, -1, 0, 1
    fourones = Machine(1, [0, 0, 0, 0, 0],
    {
        (1, 0) : (1, "R", 2),
        (1, 1) : (1, "L", 2),
        (2, 0) : (1, "L", 1),
        (2, 1) : (1, "R", 3)
    }, 2)

    # Prints 4 1s to the tape in positions 0, 1, 2, 3
    fourones2 = Machine(1, [0, 0, 0, 0, 0],
    {
        (1, 0) : (1, "R", 2),
        (2, 0) : (1, "R", 3),
        (3, 0) : (1, "R", 4),
        (4, 0) : (1, "R", 5)
    })

    # Adds the two numbers in unary on the tape
    adder = Machine(1, [1, 1, 0, 1, 1, 1, 0, 0], 
    {
        (1, 1) : (1, "R", 1),
        (1, 0) : (1, "R", 2),
        (2, 1) : (1, "R", 2),
        (2, 0) : (0, "L", 3),
        (3, 1) : (0, "R", 4)
    })

    # Prints 1s to the tape till the tape runs out. Positions 0, 1, 2, 3, ...
    ones = Machine(1, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    {
        (1, 0) : (1, "R", 1)
    }, 2)

    # Prints 1s to the tape in negative direction till tape runs out. Positions -1, -2, -3, ...
    nones = Machine(1, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    {
        (1, 0) : (0, "L", 2),
        (2, 0) : (1, "L", 2)
    }, 2)

    machine = adder

    print "Beg:", machine.tape
    machine.run()
    print "End:", machine.tape

if __name__ == '__main__':
    main()