টুরিং মেশিন — ফরমাল ডেফিনিশন

# একটি সত্যিকারের টুরিং মেশিন সিমুলেটর -- টেপ = position -> symbol ডিকশনারি
# (না-লেখা পজিশন ডিফল্টভাবে ব্ল্যাংক -- conceptually অসীম টেপ দক্ষভাবে represent করে)

class TuringMachine:
    def __init__(self, transitions, start, accept, reject, blank='_'):
        self.transitions = transitions   # dict: (state, symbol) -> (new_state, write, move)
        self.start = start
        self.accept = accept
        self.reject = reject
        self.blank = blank

    def run(self, input_string, max_steps=2000):
        tape = {i: ch for i, ch in enumerate(input_string)}
        head = 0
        state = self.start
        steps = 0
        while steps < max_steps:
            if state == self.accept:
                return "accept", steps
            if state == self.reject:
                return "reject", steps
            symbol = tape.get(head, self.blank)
            key = (state, symbol)
            if key not in self.transitions:
                return "reject", steps          # অসংজ্ঞায়িত ট্রানজিশন -- reject
            new_state, write, move = self.transitions[key]
            tape[head] = write
            head += 1 if move == 'R' else -1
            state = new_state
            steps += 1
        # max_steps শুধু এই স্যান্ডবক্সের ব্যবহারিক নিরাপত্তা-সীমা -- তাত্ত্বিক TM মডেলে
        # কোনো ধাপ-সীমা নেই, এটি অসীম সময় ধরে চলতে পারে
        return "timeout", steps


# L = { 0^n 1^n : n >= 0 } -- leftmost 0 ও rightmost 1 বারবার crossing off
B = '_'
trans = {
    ('q0', '0'): ('q1', 'X', 'R'),    # leftmost অচিহ্নিত 0 -> X দিয়ে চিহ্নিত, ডানে matching 1 খোঁজো
    ('q0', 'Y'): ('q3', 'Y', 'R'),    # সব 0 শেষ -- বাকি অংশ সব Y কিনা যাচাই করো
    ('q0', B):   ('qaccept', B, 'R'),
    ('q1', '0'): ('q1', '0', 'R'),
    ('q1', 'Y'): ('q1', 'Y', 'R'),
    ('q1', '1'): ('q2', 'Y', 'L'),    # rightmost অচিহ্নিত 1 -> Y দিয়ে চিহ্নিত, বামে ফিরে যাও
    ('q1', B):   ('qreject', B, 'R'),
    ('q2', '0'): ('q2', '0', 'L'),
    ('q2', 'Y'): ('q2', 'Y', 'L'),
    ('q2', 'X'): ('q0', 'X', 'R'),    # X সীমানায় পৌঁছালে q0 থেকে পরের 0 খোঁজো
    ('q3', 'Y'): ('q3', 'Y', 'R'),
    ('q3', B):   ('qaccept', B, 'R'),
}
tm = TuringMachine(trans, start='q0', accept='qaccept', reject='qreject')

test_strings = ["", "01", "0011", "000111", "0110", "011", "10", "0001111"]
print("স্ট্রিং          | ফলাফল    | ধাপ")
print("-" * 40)
for s in test_strings:
    result, steps = tm.run(s)
    print(f"{s!r:16s} | {result:8s} | {steps}")