TuringMachine.py

#!/usr/bin/env python
# coding:utf-8

import time
import graphviz


class Tape(object):
    def __init__(self, tape_string="", blank_symbol="B"):
        self.blank_symbol = blank_symbol
        self.__tape = dict((enumerate(blank_symbol * 0x01 + tape_string + blank_symbol * 0x01)))


    def __str__(self):
        s = ""
        min_used_index = min(self.__tape.keys()) 
        max_used_index = max(self.__tape.keys())
        for i in range(min_used_index, max_used_index):
            s += self.__tape[i]
        return s    


    def __getitem__(self,index):
        if index in self.__tape:
            return self.__tape[index]
        else:
            return self.blank_symbol


    def __setitem__(self, pos, char):
        self.__tape[pos] = char 

        
class TuringMachine(object):
    def __init__(self, 
                 tape="", 
                 blank_symbol="B",
                 initial_state="q0",
                 final_states={"qf"},
                 head_position=1,
                 transition_function=None,
                 name="Turing Machine",
                 sleep_time=0,
                 mute=False):
        self.__tape = Tape(tape)
        self.__head_position = head_position
        self.__blank_symbol = blank_symbol
        self.__current_state = initial_state
        self.__halt = False
        self.__state_history = []
        self.__Q = set()
        self.__name = name
        self.__sleep_time = sleep_time
        self.__mute = mute
        if transition_function == None:
            self.__transition_function = {}
        else:
            self.__transition_function = transition_function
        # Analysis Q
        for k, v in self.__transition_function.items():
            self.__Q.add(k[0])
            self.__Q.add(v[0])
        if final_states == None:
            self.__final_states = set()
        else:
            self.__final_states = set(final_states)


    def instaneous_description(self):
        prefix = str(self.__tape)[:self.__head_position]
        suffix = str(self.__tape)[self.__head_position:]
        return "%s[%s]%s" % (prefix, self.__current_state, suffix)


    def get_tape(self): 
        return str(self.__tape)


    def step(self):
        char_under_head = self.__tape[self.__head_position]
        x = (self.__current_state, char_under_head)
        if x in self.__transition_function:
            y = self.__transition_function[x]
            self.__tape[self.__head_position] = y[1]
            if y[2] == "R":
                self.__head_position += 1
            elif y[2] == "L":
                self.__head_position -= 1
            self.__current_state = y[0]
        else:
            if not self.__mute: print("No transition for %s, halting..." % (str(x)))
            self.__halt = True


    def infinite_loop(self):
        ID = self.instaneous_description()
        if ID in self.__state_history:
            return True
        else:
            self.__state_history.append(ID)
            return False


    def visualize(self):
        g = graphviz.Digraph(name='Turing Machine')
        g.graph_attr['rankdir'] = 'LR'
        g.edge_attr.update(arrowhead='vee', arrowsize='1')
        # Nodes
        for q in sorted(self.__Q):
            if q in self.__final_states:
                g.node(q, q, shape='doublecircle')
            else:
                g.node(q, q)
        # Edges
        for k, v in self.__transition_function.items():
            g.edge(k[0], v[0], "%s/%s,%s" % (k[1], v[1], v[2]))
        g.render("%s.gv" % (self.__name), None, format="png")


    def start(self):
        while not self.__halt:
            if self.infinite_loop():
                if not self.__mute: print("Infinite loop for state: %s, halting..." % (self.__current_state))
                break
            self.step()
            if not self.__mute: print(self.instaneous_description())
            time.sleep(self.__sleep_time)
        return self.__current_state in self.__final_states


def exercise_8_2_1_TM(tape):
    transition_function = {
        ("q0","0"):("q1", "X", "R"),
        ("q0","Y"):("q3", "Y", "R"),
        ("q1","0"):("q1", "0", "R"),
        ("q1","1"):("q2", "Y", "L"),
        ("q1","Y"):("q1", "Y", "R"),
        ("q2","0"):("q2", "0", "L"),
        ("q2","X"):("q0", "X", "R"),
        ("q2","Y"):("q2", "Y", "L"),
        ("q3","Y"):("q3", "Y", "R"),
        ("q3","B"):("q4", "B", "R"),
        ("q4","B"):("qf", "B", "R"),
    }
    # Declare Turing Machine then start it
    TM = TuringMachine(
        tape=tape, 
        transition_function=transition_function,
        name="exercise_8_2_1_TM"
    )
    TM.visualize()
    TM.start()
    # Final Instaneous Description
    print("Final Instaneous Description: %s" % (TM.instaneous_description()))


def exercise_8_2_1_a():
    exercise_8_2_1_TM(tape="00")


def exercise_8_2_1_b():
    exercise_8_2_1_TM(tape="000111")


def exercise_8_2_1_c():
    exercise_8_2_1_TM(tape="00111")


def exercise_8_2_2_a():
    transition_function = {
        ("q0","0"):("q1", "X", "R"),
        ("q0","1"):("q2", "X", "R"),
        ("q1","X"):("q1", "X", "L"),
        ("q1","0"):("q1", "0", "L"),
        ("q1","1"):("q1", "1", "L"),
        ("q1","B"):("q3", "B", "R"),
        ("q2","X"):("q2", "X", "L"),
        ("q2","1"):("q2", "1", "L"),
        ("q2","0"):("q2", "0", "L"),
        ("q2","B"):("q4", "B", "R"),
        ("q3","X"):("q3", "X", "R"),
        ("q3","0"):("q3", "0", "R"),
        ("q3","1"):("q5", "X", "L"),
        ("q4","X"):("q4", "X", "R"),
        ("q4","1"):("q4", "1", "R"),
        ("q4","0"):("q5", "X", "L"),
        ("q5","0"):("q5", "0", "L"),
        ("q5","1"):("q5", "1", "L"),
        ("q5","X"):("q5", "X", "L"),
        ("q5","B"):("q0", "B", "R"),
        ("q0","X"):("q0", "X", "R"),
        ("q0","B"):("qf", "B", "R"),
    }
    # Declare Turing Machine then start it
    TM = TuringMachine(
        tape="00110110", 
        transition_function=transition_function,
        name="exercise_8_2_2_a_TM"
    )
    TM.visualize()
    TM.start()
    # Final Instaneous Description
    print("Final Instaneous Description: %s" % (TM.instaneous_description()))


def exercise_8_2_2_b():
    transition_function = {
        ("q0","a"):("q1", "X", "R"),
        ("q1","a"):("q1", "a", "R"),
        ("q1","Y"):("q1", "Y", "R"),
        ("q1","b"):("q2", "Y", "R"),
        ("q2","b"):("q2", "b", "R"),
        ("q2","Z"):("q2", "Z", "R"),
        ("q2","c"):("q3", "Z", "L"),
        ("q3","Z"):("q3", "Z", "L"),
        ("q3","b"):("q3", "b", "L"),
        ("q3","Y"):("q3", "Y", "L"),
        ("q3","a"):("q3", "a", "L"),
        ("q3","X"):("q0", "X", "R"),
        ("q0","Y"):("q4", "Y", "R"),
        ("q4","Y"):("q4", "Y", "R"),
        ("q4","Z"):("q5", "Z", "R"),
        ("q5","Z"):("q5", "Z", "R"),
        ("q5","B"):("qf", "B", "R"),
    }
    # Declare Turing Machine then start it
    TM = TuringMachine(
        tape="aaabbbccc", 
        transition_function=transition_function,
        name="exercise_8_2_2_b_TM"
    )
    TM.visualize()
    TM.start()
    # Final Instaneous Description
    print("Final Instaneous Description: %s" % (TM.instaneous_description()))


def exercise_8_2_2_c():
    transition_function = {
        ("q0","0"):("q1", "X", "R"),
        ("q0","1"):("q2", "X", "R"),
        ("q1","0"):("q1", "0", "R"),
        ("q1","1"):("q1", "1", "R"),
        ("q1","X"):("q1", "X", "R"),
        ("q1","B"):("q3", "B", "L"),
        ("q2","0"):("q2", "0", "R"),
        ("q2","1"):("q2", "1", "R"),
        ("q2","X"):("q2", "X", "R"),
        ("q2","B"):("q4", "B", "L"),
        ("q3","X"):("q3", "X", "L"),
        ("q3","0"):("q5", "X", "L"),
        ("q4","X"):("q4", "X", "L"),
        ("q4","1"):("q5", "X", "L"),
        ("q5","0"):("q5", "0", "L"),
        ("q5","1"):("q5", "1", "L"),
        ("q5","X"):("q0", "X", "R"),
        ("q0","X"):("qf", "X", "R"),
    }
    # Declare Turing Machine then start it
    TM = TuringMachine(
        tape="00010100101000B", 
        transition_function=transition_function,
        name="exercise_8_2_2_c_TM"
    )
    TM.visualize()
    TM.start()
    # Final Instaneous Description
    print("Final Instaneous Description: %s" % (TM.instaneous_description()))


def exercise_8_2_5_a():
    for i in range(0x08):
        for j in range(1 << i):
            # Enumerate the input tape space with length i
            t = bin(j)[2:]
            tape = "0" * (i - len(t)) + t
            transition_function = {
                ("q0","0"):("q1", "1", "R"),
                ("q1","1"):("q0", "0", "R"),
                ("q1","B"):("qf", "B", "R"),
            }
            # Declare Turing Machine then start it
            TM = TuringMachine(
                tape=tape, 
                transition_function=transition_function,
                name="exercise_8_2_2_c_TM",
                mute=True
            )
            # TM.visualize()
            if TM.start():
                print("tape: %s is accepted" % (tape))


def exercise_8_2_5_b():
    for i in range(0x08):
        for j in range(1 << i):
            # Enumerate the input tape space with length i
            t = bin(j)[2:]
            tape = "0" * (i - len(t)) + t
            transition_function = {
                ("q0","0"):("q0", "B", "R"),
                ("q0","1"):("q1", "B", "R"),
                ("q1","1"):("q1", "B", "R"),
                ("q1","B"):("qf", "B", "R"),
            }
            # Declare Turing Machine then start it
            TM = TuringMachine(
                tape=tape, 
                transition_function=transition_function,
                name="exercise_8_2_2_c_TM",
                mute=True
            )
            # TM.visualize()
            if TM.start():
                print("tape: %s is accepted" % (tape))


def exercise_8_2_5_c():
    for i in range(0x08):
        for j in range(1 << i):
            # Enumerate the input tape space with length i
            t = bin(j)[2:]
            tape = "0" * (i - len(t)) + t
            transition_function = {
                ("q0","0"):("q1", "1", "R"),
                ("q1","1"):("q2", "0", "L"),
                ("q2","1"):("q0", "1", "R"),
                ("q1","B"):("qf", "B", "R"),
            }
            # Declare Turing Machine then start it
            TM = TuringMachine(
                tape=tape, 
                transition_function=transition_function,
                name="exercise_8_2_2_c_TM",
                mute=True
            )
            # TM.visualize()
            if TM.start():
                print("tape: %s is accepted" % (tape))


def main():
    exercise_8_2_1_a()
    exercise_8_2_1_b()
    exercise_8_2_1_c()
    exercise_8_2_2_a()
    exercise_8_2_2_b()
    exercise_8_2_2_c()
    exercise_8_2_5_a()
    exercise_8_2_5_b()
    exercise_8_2_5_c()


if __name__ == "__main__":
    main()