turing_machine.py

import csv
import sys


class MachineStuck(Exception):
    pass


class UnKnownOperation(Exception):
    pass


# NOTE - the tape is in theory infinite, but for our purposes a finite one will do
TAPE_SIZE = 100
CSV_SEPARATOR = ","
OP_SEPARATOR = "-"
INITIAL_M_CONFIG = "b"


class TuringMachine:
    """
    Construct a Turing machine from a csv file with the following format:
    m-configuration,symbol,operations,final m-configuration

    Example - file describing the machine computing 1/3:

    b,None,P0-R,c
    c,None,R,e
    e,None,P1-R,f
    f,None,R,b
    """

    def __init__(self, file_path):
        self._description = {}
        with open(file_path) as file:
            reader = csv.reader(file, delimiter=CSV_SEPARATOR)
            for row in reader:
                m_config, symbol, operations_str, next_m_config = row
                if symbol == "None":
                    symbol = None
                operations = operations_str.split(OP_SEPARATOR)
                self._description[(m_config, symbol)] = operations, next_m_config

        self._tape = TAPE_SIZE * [None]
        self._current_index = 0
        self._current_m_config = INITIAL_M_CONFIG

    def next(self):
        next_op_config = self._description.get(
            (self._current_m_config, self._get_current_symbol())
        )
        if next_op_config is None:
            raise MachineStuck

        operations, next_m_config = next_op_config
        for op in operations:
            self._perform_operation(op)
        self._current_m_config = next_m_config

    def print(self):
        print(f"current m-config: {self._current_m_config}")
        head_cursor = f"{' ' * 2 * self._current_index}*"
        print(head_cursor)
        line = (
            "|".join(
                (str(symbol) if symbol is not None else " " for symbol in self._tape)
            )
            + "..."
        )
        print(line)

    def _get_current_symbol(self):
        return self._tape[self._current_index]

    def _write_symbol(self, symbol):
        self._tape[self._current_index] = symbol

    def _move_head_left(self):
        self._current_index -= 1

    def _move_head_right(self):
        self._current_index += 1

    def _perform_operation(self, op):
        if op == "L":
            self._move_head_left()
        elif op == "R":
            self._move_head_right()
        elif op == "P0":
            self._write_symbol(0)
        elif op == "P1":
            self._write_symbol(1)
        elif op.startswith("P"):
            self._write_symbol(op[1:])
        else:
            raise UnKnownOperation


if __name__ == "__main__":
    file_path = sys.argv[1]
    machine = TuringMachine(file_path)
    while True:
        machine.print()
        input("type something to print the next state")
        machine.next()