turing_machine.py

from enum import Enum, auto


class HeadMove(Enum):
    LEFT = -1
    RIGHT = 1
    NOTHING = 0


class TuringMachine:
    """ Turing machine simulator in python """

    def __init__(
        self, transitions, tape, start_state="q0", halt_states={"qa", "qr"}, blank="_"
    ):
        self.transitions = transitions
        self.cur_state = start_state
        self.blank = blank
        self.halt_states = halt_states
        self.tape = tape
        self.cur_pos = 0

    @property
    def configuration(self):
        return (
            "".join(self.tape[: self.cur_pos]).lstrip(self.blank),
            self.cur_state,
            "".join(self.tape[self.cur_pos :]).rstrip(self.blank),
        )

    def is_halted(self):
        return self.cur_state in self.halt_states

    def next_state(self):
        cur_symbol = self.tape[self.cur_pos]
        next_state = self.transitions.get(self.cur_state, {}).get(cur_symbol, None)
        if next_state is None:
            self.cur_state = "qr"
            return

        state, write_symbol, head_move = next_state
        self.tape[self.cur_pos] = write_symbol
        if head_move == HeadMove.LEFT and self.cur_pos == 0:
            self.tape.insert(0, self.blank)
        elif head_move == HeadMove.RIGHT and self.cur_pos == len(self.tape) - 1:
            self.tape.append(self.blank)
            self.cur_pos += 1
        else:
            self.cur_pos += head_move.value

        self.cur_state = state

#machine = TuringMachine(copy2, list("11"))
#print(machine.configuration)
#while not machine.is_halted():
#    machine.next_state()
#    print(machine.configuration)