Turing Machine in Python

binaryadd.txt

; Binary addition - adds two binary numbers
; Input: two binary numbers, separated by a single space, eg '100 1110'

0 _ _ r 1
0 * * r 0
1 _ _ l 2
1 * * r 1
2 0 _ l 3x
2 1 _ l 3y
2 _ _ l 7
3x _ _ l 4x
3x * * l 3x
3y _ _ l 4y
3y * * l 3y
4x 0 x r 0
4x 1 y r 0
4x _ x r 0
4x * * l 4x    ; skip the x/y's
4y 0 1 * 5
4y 1 0 l 4y
4y _ 1 * 5
4y * * l 4y    ; skip the x/y's
5 x x l 6
5 y y l 6
5 _ _ l 6
5 * * r 5
6 0 x r 0
6 1 y r 0

7 x 0 l 7
7 y 1 l 7
7 _ _ r halt
7 * * l 7

Example.md

python ./turing.py ./binaryadd.txt "110110 101011"

turing.py

from collections import defaultdict

class MaxStepsExceededException(Exception):
    pass


class ParseException(Exception):
    pass


class HaltException(Exception):
    pass


class Instruction:
    def __init__(self, current_state, current_symbol, new_symbol, action, new_state):
        self.current_state = current_state
        self.current_symbol = current_symbol
        self.new_symbol = new_symbol
        self.action = action
        self.new_state = new_state

    @staticmethod
    def parse(line):
        # Strip the comment
        line = line.split(';', 1)[0]

        tokens = line.split()

        # Empty line (or comment)
        if len(tokens) == 0:
            return None

        if len(tokens) > 6 or len(tokens) == 6 and tokens[5] != "!":
            raise ParseException("Line contains too many entries")

        if len(tokens) < 5:
            raise ParseException("Line contains not enough entries")

        # remove the break point marker, not supported by this machine
        if len(tokens) == 6:
            tokens.pop()

        current_state, current_symbol, new_symbol, action, new_state = tokens

        if len(current_symbol) != 1:
            raise ParseException("<current symbol> should be a single character")

        if len(new_symbol) != 1:
            raise ParseException("<new symbol> should be a single character")

        if action.lower() not in ["l", "r", "*"]:
            raise ParseException("<direction> should be 'l', 'r', or '*'")

        return Instruction(current_state, current_symbol, new_symbol, action, new_state)


VARIANT_INFINITE = 0 # infinite tape
VARIANT_FINITE = 1 # only infinite in one direction

class TuringMachine:
    def __init__(self, program, variant=VARIANT_INFINITE):
        self.state = "0"
        self.steps = 0
        self.tape = ""
        self.tape_offset = 0
        self.head_position = 0
        self.variant = variant
        self.compile(program)

    def run(self, initial_tape, initial_state, max_steps=None):
        # Find the initial head location, if given
        try:
            self.head_position = initial_tape.index("*")
        except ValueError:
            self.head_position = 0

        self.tape = initial_tape.replace("*", "").replace(" ", "_") if initial_tape is not None else ""
        if self.tape == "":
            self.tape = " "
        self.tape_offset = 0

        self.state = initial_state.strip().split(" ")[0] if initial_state is not None else ""
        if self.state == "":
            self.state = "0"

        self.steps = 0

        while self.step():
            if max_steps is not None and self.steps > max_steps:
                raise MaxStepsExceededException()

        return {
            'output': self.tape,
            'head': self.head_position,
            'steps': self.steps
        }


    def step(self):
        if self.state[0:4].lower() == "halt":
            return False

        # current symbol
        head_symbol = self.getTapeSymbol(self.head_position)

        # Find the appropriate TM instruction
        instruction = self.getNextInstruction(self.state, head_symbol)

        if instruction is None:
            raise HaltException("No rule for state '{}' and symbol '{}'.".format(self.state, head_symbol))
        
        if instruction.new_state == "*":
            new_state = state
        else:
            new_state = instruction.new_state

        if instruction.new_symbol == "*":
            new_symbol = head_symbol
        else:
            new_symbol = instruction.new_symbol

        if instruction.action.lower() == "l":
            action = -1
        elif instruction.action.lower() == "r":
            action = 1
        else:
            action = 0

        # We can't move left when we're already at the left-most tape cell
        if self.variant == 1 and self.head_position == 0 and action == -1:
            action = 0

        # Update the machine tape and state
        self.setTapeSymbol(self.head_position, new_symbol)
        self.state = new_state
        self.head_position += action
        self.steps += 1
    
        return True

    def compile(self, source):
        program = defaultdict(dict)
        for i, line in enumerate(source.splitlines()):
            try:
                instruction = Instruction.parse(line)

                # If the line was empty or a comment, skip it 
                if instruction is None:
                    continue

                # Remember the line number for better error messages
                instruction.sourceLineNumber = i + 1

                # Insert the instruction in the state transition table
                if instruction.current_symbol in program[instruction.current_state]:
                    raise ParseException("Multiple definitions for state '{instruction.current_state}' symbol '{instruction.current_symbol}' on lines {existingInstruction.sourceLineNumber} and {instruction.sourceLineNumber}".format(
                        instruction=instruction,existingInstruction=program[instruction.current_state][instruction.current_symbol]))
                else:
                    program[instruction.current_state][instruction.current_symbol] = instruction
            except ParseException as err:
                raise ParseException("Parse exception on line {}: {}".format(i+1, err))
        
        self.program = dict(program) # ditch the defaultdict for a normal predictable dict

    def getNextInstruction(self, state, head_symbol):
        for a_state in [state, "*"]:
            for a_symbol in [head_symbol, "*"]:
                if a_state in self.program and a_symbol in self.program[a_state]:
                    return self.program[a_state][a_symbol]
        return None

    def getTapeSymbol(self, position):
        if position < self.tape_offset or position >= len(self.tape) + self.tape_offset:
            return "_"
        else:
            return self.tape[position - self.tape_offset]

    def setTapeSymbol(self, position, symbol):
        if position < self.tape_offset:
            self.tape = symbol + (self.tape_offset - position - 1) * "_" + self.tape
            self.tape_offset = position
        elif position > self.tape_offset + len(self.tape):
            self.tape = self.tape + (self.tape_offset + len(self.tape) - position - 1) * "_" + symbol
        else:
            self.tape = self.tape[0:(position - self.tape_offset)] + symbol + self.tape[(position - self.tape_offset + 1):]

if __name__ == '__main__':
    import sys
    
    if len(sys.argv) < 2 or len(sys.argv) > 4:
        print("Usage: {} <program> [inital_tape [initial_state]]".format(sys.argv[0]))
        sys.exit(1)

    with open(sys.argv[1], 'r') as program:
        machine = TuringMachine(program.read())
        state = sys.argv[2] if len(sys.argv) >= 3 else None
        tape = sys.argv[3] if len(sys.argv) >= 4 else None
        machine.run(state, tape)
        print("Output: {}".format(machine.tape))