Turing machine implementation in Python, with a couple examples

turing.py

#!/usr/bin/env python


class Tape(object):
    def __init__(self, data="", blank=None):
        self.tape = dict(enumerate(data))
        self.pos = 0
        self.blank = blank

    def move_right(self):
        self.pos += 1

    def move_left(self):
        self.pos -= 1

    def read(self):
        return self.read_at(self.pos)

    def read_at(self, pos):
        return self.tape.get(pos, self.blank)

    def write(self, value):
        self.tape[self.pos] = value

    def render(self):
        range_min = min(min(self.tape.keys()), self.pos)
        range_max = max(max(self.tape.keys()), self.pos)

        for i in xrange(range_min, range_max+1):
            val = self.read_at(i)
            txt = str(val) if val is not None else ''
            if i == 0:
                txt += " (start)"
            if i == self.pos:
                txt += " <--"
            print txt


class NumericTape(Tape):
    def __init__(self, data="", blank=None):
        return super(NumericTape, self).__init__(
            map(lambda x: int(x) if x != " " else blank, data),
            blank
        )


class TextTape(Tape):
    def __init__(self, data=""):
        return super(TextTape, self).__init__(data, " ")


class Instruction(object):
    LEFT = Tape.move_left
    RIGHT = Tape.move_right
    NOOP = staticmethod(lambda x: None)

    def __init__(self, write, move, next):
        self.write = write
        self.move = move
        self.next = next


class Halt(Instruction):
    def __init__(self):
        pass


class Machine(object):
    def __init__(self, states, initial_state):
        self.states = states
        self.initial_state = initial_state


class MachineRunner(object):
    def __init__(self, machine, tape, debug=False):
        self.machine = machine
        self.tape = tape
        self.instruction = self.get_instruction(self.machine.initial_state)
        self.debug = debug

    def get_instruction(self, state_name):
        if state_name is Halt:
            return Halt()
        return self.machine.states[(state_name, self.tape.read())]

    def execute_one(self):
        if self.halted():
            return

        if self.debug:
            print "---"
            self.tape.render()
            print "---"
            print self.instruction.next

        self.tape.write(self.instruction.write)
        self.instruction.move(self.tape)
        self.instruction = self.get_instruction(self.instruction.next)

    def execute(self):
        while not self.halted():
            self.execute_one()
        return self.tape

    def halted(self):
        return isinstance(self.instruction, Halt)


# Tri-state busy beaver
"""
MachineRunner(
    Machine(
        {
            ("a", 0): Instruction(1, Instruction.RIGHT, 'b'),
            ("a", 1): Instruction(1, Instruction.RIGHT, Halt),
            ("b", 0): Instruction(0, Instruction.RIGHT, 'c'),
            ("b", 1): Instruction(1, Instruction.RIGHT, 'b'),
            ("c", 0): Instruction(1, Instruction.LEFT,  'c'),
            ("c", 1): Instruction(1, Instruction.LEFT,  'a'),
        },
        "a"
    ),
    Tape(blank=0)
).execute().render()
"""

# Add 1 in binary
"""
MachineRunner(
    Machine(
        {
            ("a", None): Instruction(None, Instruction.LEFT, 'b'),
            ("a", 0): Instruction(0, Instruction.RIGHT, 'a'),
            ("a", 1): Instruction(1, Instruction.RIGHT, 'a'),

            ("b", None): Instruction(1, Instruction.RIGHT, Halt),
            ("b", 0): Instruction(1, Instruction.RIGHT, Halt),
            ("b", 1): Instruction(0, Instruction.LEFT, 'b'),
        },
        "a"
    ),
    Tape(map(int, "100011"))
).execute().render()
"""


# Add 1 in decimal
"""
MachineRunner(
    Machine(
        {
            ("a", None): Instruction(None, Instruction.LEFT, 'b'),
            ("a", 0): Instruction(0, Instruction.RIGHT, 'a'),
            ("a", 1): Instruction(1, Instruction.RIGHT, 'a'),
            ("a", 2): Instruction(2, Instruction.RIGHT, 'a'),
            ("a", 3): Instruction(3, Instruction.RIGHT, 'a'),
            ("a", 4): Instruction(4, Instruction.RIGHT, 'a'),
            ("a", 5): Instruction(5, Instruction.RIGHT, 'a'),
            ("a", 6): Instruction(6, Instruction.RIGHT, 'a'),
            ("a", 7): Instruction(7, Instruction.RIGHT, 'a'),
            ("a", 8): Instruction(8, Instruction.RIGHT, 'a'),
            ("a", 9): Instruction(9, Instruction.RIGHT, 'a'),

            ("b", None): Instruction(1, Instruction.LEFT, Halt),
            ("b", 0): Instruction(1, Instruction.LEFT, Halt),
            ("b", 1): Instruction(2, Instruction.LEFT, Halt),
            ("b", 2): Instruction(3, Instruction.LEFT, Halt),
            ("b", 3): Instruction(4, Instruction.LEFT, Halt),
            ("b", 4): Instruction(5, Instruction.LEFT, Halt),
            ("b", 5): Instruction(6, Instruction.LEFT, Halt),
            ("b", 6): Instruction(7, Instruction.LEFT, Halt),
            ("b", 7): Instruction(8, Instruction.LEFT, Halt),
            ("b", 8): Instruction(9, Instruction.LEFT, Halt),
            ("b", 9): Instruction(0, Instruction.LEFT, 'b'),
        },
        "a"
    ),
    Tape(map(int, "10012399"))
).execute().render()
"""


# Reverse Binary
"""
MachineRunner(
    Machine(
        {
            # Shift by 1 place to the righ (and delete last digit)
            ("Shift-s", None): Instruction(None, Instruction.LEFT, Halt),
            ("Shift-s", 0): Instruction(None, Instruction.RIGHT, 'Shift-0'),
            ("Shift-s", 1): Instruction(None, Instruction.RIGHT, 'Shift-1'),

            ("Shift-0", None): Instruction(None, Instruction.LEFT, 'Place-0'),
            ("Shift-0", 0): Instruction(0, Instruction.RIGHT, 'Shift-0'),
            ("Shift-0", 1): Instruction(0, Instruction.RIGHT, 'Shift-1'),

            ("Shift-1", None): Instruction(None, Instruction.LEFT, 'Place-1'),
            ("Shift-1", 0): Instruction(1, Instruction.RIGHT, 'Shift-0'),
            ("Shift-1", 1): Instruction(1, Instruction.RIGHT, 'Shift-1'),

            # Place a digit before the first blank
            ("Place-0", None): Instruction(None, Instruction.LEFT, 'Place-0-done'),
            ("Place-0", 0): Instruction(0, Instruction.LEFT, 'Place-0'),
            ("Place-0", 1): Instruction(1, Instruction.LEFT, 'Place-0'),

            ("Place-0-done", None): Instruction(0, Instruction.RIGHT, 'Rewind'),
            ("Place-0-done", 0): Instruction(0, Instruction.LEFT, 'Place-0-done'),
            ("Place-0-done", 1): Instruction(1, Instruction.LEFT, 'Place-0-done'),

            ("Place-1", None): Instruction(None, Instruction.LEFT, 'Place-1-done'),
            ("Place-1", 0): Instruction(0, Instruction.LEFT, 'Place-1'),
            ("Place-1", 1): Instruction(1, Instruction.LEFT, 'Place-1'),

            ("Place-1-done", None): Instruction(1, Instruction.RIGHT, 'Rewind'),
            ("Place-1-done", 0): Instruction(0, Instruction.LEFT, 'Place-1-done'),
            ("Place-1-done", 1): Instruction(1, Instruction.LEFT, 'Place-1-done'),

            # Find start (the position after the first blank)
            ("Rewind", None): Instruction(None, Instruction.RIGHT, "Shift-s"),
            ("Rewind", 0): Instruction(0, Instruction.RIGHT, 'Rewind'),
            ("Rewind", 1): Instruction(1, Instruction.RIGHT, 'Rewind'),
        },
        "Shift-s"
    ),
    Tape(map(int, "10001101"))
).execute().render()
"""


# Strlen, writes the number of consecutive non-blank places in the tapes (in binary)
"""
MachineRunner(
    Machine(
        {
            # Initialize the counter (1 blank to the left of the string)
            ("Start", None): Instruction(0, Instruction.RIGHT, Halt),           # Empty tape, just write 0 and halt
            ("Start", 0): Instruction(None, Instruction.LEFT, "Start-write"),   # If not empty, write a blank
            ("Start", 1): Instruction(None, Instruction.LEFT, "Start-write"),   # and initialize the counter with 1

            ("Start-write", None): Instruction(1, Instruction.RIGHT, "GotoEnd"),# Write the 1 (the tape isn't empty)
            ("Start-write", 0): Instruction(1, Instruction.RIGHT, Halt),        # The tape has garbage data
            ("Start-write", 1): Instruction(1, Instruction.RIGHT, Halt),        # The tape has garbage data

            # Go to the end of the string
            ("GotoEnd", None): Instruction(None, Instruction.RIGHT, "FindEnd"), # Skip the counter digits
            ("GotoEnd", 0): Instruction(0, Instruction.RIGHT, "GotoEnd"),
            ("GotoEnd", 1): Instruction(1, Instruction.RIGHT, "GotoEnd"),

            ("FindEnd", None): Instruction(None, Instruction.LEFT, "Found"),    # Skip until a blank
            ("FindEnd", 0): Instruction(0, Instruction.RIGHT, "FindEnd"),
            ("FindEnd", 1): Instruction(1, Instruction.RIGHT, "FindEnd"),

            # Record the fact we found a character
            ("Found", None): Instruction(None, Instruction.LEFT, Halt),         # Nothing left
            ("Found", 0): Instruction(None, Instruction.LEFT, "FindCounter"),   # Remove the last digit
            ("Found", 1): Instruction(None, Instruction.LEFT, "FindCounter"),

            # Go back to the counter
            ("FindCounter", None): Instruction(None, Instruction.LEFT, "Increment"),
            ("FindCounter", 0): Instruction(0, Instruction.LEFT, "FindCounter"),
            ("FindCounter", 1): Instruction(1, Instruction.LEFT, "FindCounter"),

            # Add 1 to the counter
            ("Increment", None): Instruction(1, Instruction.RIGHT, "GotoEnd"),
            ("Increment", 0): Instruction(1, Instruction.RIGHT, "GotoEnd"),
            ("Increment", 1): Instruction(0, Instruction.LEFT, "Increment"),
        },
        "Start"
    ),
    Tape(map(int, "100011101")),
).execute().render()
"""

# Decrement binary integer
"""
MachineRunner(
    Machine(
        {
            ("find-right", None): Instruction(None, Instruction.LEFT, 'decrement'),
            ("find-right", 0): Instruction(0, Instruction.RIGHT, 'find-right'),
            ("find-right", 1): Instruction(1, Instruction.RIGHT, 'find-right'),

            ("decrement", None): Instruction(1, Instruction.RIGHT, Halt),
            ("decrement", 0): Instruction(1, Instruction.LEFT, 'decrement'),
            ("decrement", 1): Instruction(0, Instruction.RIGHT, Halt),
        },
        "find-right"
    ),
    Tape(map(int, "101100")),
).execute().render()
"""

# Binary Sum
"""
MachineRunner(
    Machine(
        {
            # Go to the end (needs to skip a blank)
            ("find-end", None): Instruction(None, Instruction.RIGHT, "find-end-n2"),
            ("find-end", 0): Instruction(0, Instruction.RIGHT, "find-end"),
            ("find-end", 1): Instruction(1, Instruction.RIGHT, "find-end"),

            ("find-end-n2", None): Instruction(None, Instruction.LEFT, "decrement"),
            ("find-end-n2", 0): Instruction(0, Instruction.RIGHT, "find-end-n2"),
            ("find-end-n2", 1): Instruction(1, Instruction.RIGHT, "find-end-n2"),

            # Decrement n2
            ("decrement", None): Instruction(None, Instruction.RIGHT, "clear"),
            ("decrement", 0): Instruction(1, Instruction.LEFT, "decrement"),
            ("decrement", 1): Instruction(0, Instruction.NOOP, "find-n1"),

            # Find the end of n1
            ("find-n1", None): Instruction(None, Instruction.LEFT, "increment"),
            ("find-n1", 0): Instruction(0, Instruction.LEFT, "find-n1"),
            ("find-n1", 1): Instruction(1, Instruction.LEFT, "find-n1"),

            # Increment n1
            ("increment", None): Instruction(1, Instruction.NOOP, "find-end"),
            ("increment", 0): Instruction(1, Instruction.NOOP, "find-end"),
            ("increment", 1): Instruction(0, Instruction.LEFT, "increment"),

            # Clear n2
            ("clear", None): Instruction(None, Instruction.LEFT, Halt),
            ("clear", 0): Instruction(None, Instruction.RIGHT, "clear"),
            ("clear", 1): Instruction(None, Instruction.RIGHT, "clear"),

        },
        "find-end"
    ),
    NumericTape("10011 110"),
).execute().render()
"""

from io import BytesIO
class TMDescriptionParser(object):
    class ParserError(Exception):
        pass

    movement = {
        "<": Instruction.LEFT,
        ">": Instruction.RIGHT,
        "-": Instruction.NOOP,
    }

    @classmethod
    def machine_from_string(cls, string):
        return cls(BytesIO(string)).parse_one()

    def __init__(self, file_obj):
        self.input = file_obj

    def parse_many(self):
        machines = []
        while True:
            machines.append(self._parse_machine())
            ch = self._getchar(None)
            if not ch:
                break
            elif ch != ";":
                raise self.ParserError("Extra characters after machine definition")
        return machines

    def parse_one(self):
        machine = self._parse_machine()
        if self._getchar(None):
            raise self.ParserError("Extra characters after machine definition")
        return machine

    def _parse_machine(self):
        alphabet = self._parse_alphabet()
        return self._parse_states(alphabet)

    def _getchar(self, expected):
        char = self.input.read(1)
        if not char and expected:
            raise self.ParserError("End of stream, expected %s" % expected)
        return char

    def _read_until(self, boundary, required=True):
        result = ""
        while True:
            char = self._getchar(boundary if required else None)
            if char in boundary or (not required and not char):
                return result, char
            result += char

    def _parse_alphabet(self):
        result = []

        while True:
            alphabet, delim = self._read_until(":\\")
            result += list(alphabet)
            if delim == ":":
                break
            else:
                result += [self._getchar("\\ or :")]

        if len(result) != len(set(result)):
            raise self.ParserError("Duplicate characters in the alphabet definition")

        return result

    def _parse_state_name(self):
        name, delim = self._read_until(":", False)
        if "," in name:
            raise self.ParserError("Invald state name: %s" % name)
        return name

    def _parse_states(self, alphabet):
        states = {}
        first_state = None
        while True:
            state_name = self._parse_state_name()
            if not state_name or state_name == ';':
                break

            if not first_state:
                first_state = state_name

            for input_char in alphabet:
                output_char = self._getchar("a state transition output character")
                movement = self.movement.get(
                    self._getchar("a movement operation"),
                    None
                )
                if not movement:
                    raise self.ParserError("Invalid movement operation")

                dest_state, delim = self._read_until(",")
                if not dest_state:
                    dest_state = Halt
                states[(state_name, input_char)] = Instruction(output_char, movement, dest_state)

        if not states:
            raise self.ParserError("Empty machine")

        return Machine(states, first_state)


# Binary added with the compact turing machine definition mini-language
"""
adder = " 01:a: <b,0>a,1>a,b:1>,1>,0<b,;"
print MachineRunner(
    TMDescriptionParser.machine_from_string(adder),
    TextTape("10011")
).execute().render()
"""