চার্চ-টুরিং থিসিস ও ইউনিভার্সাল টুরিং মেশিন

BLANK = '_'  # টেপের ব্ল্যাংক সিম্বল

class TuringMachine:
    """L32-এর ধাঁচের একটি জেনেরিক টুরিং মেশিন -- (state, symbol) থেকে
    (new_state, write, direction)-এর ট্রানজিশন টেবিল দিয়ে চালিত।"""
    def __init__(self, states, input_alphabet, tape_alphabet, transitions,
                 start, accept, reject, blank=BLANK):
        self.states = states
        self.transitions = transitions
        self.start = start
        self.accept = accept
        self.reject = reject
        self.blank = blank

    def run(self, input_string, max_steps=3000):
        tape = {i: c for i, c in enumerate(input_string)}
        head, state, steps = 0, self.start, 0
        while state != self.accept and state != self.reject and steps < max_steps:
            symbol = tape.get(head, self.blank)
            key = (state, symbol)
            if key not in self.transitions:
                return 'reject', steps          # ট্রানজিশন নেই -- ইমপ্লিসিট reject
            new_state, write_symbol, direction = self.transitions[key]
            tape[head] = write_symbol
            head += 1 if direction == 'R' else -1
            state = new_state
            steps += 1
        if state == self.accept:
            return 'accept', steps
        elif state == self.reject:
            return 'reject', steps
        else:
            return 'timeout', steps


# L = {0^n 1^n : n >= 0} -- leftmost অচিহ্নিত 0 ও rightmost অচিহ্নিত 1 জোড়ায় জোড়ায় ক্রস-অফ
zn_states = {'q_find0', 'q_goright', 'q_findlast', 'q_gohome', 'q_accept', 'q_reject'}
zn_transitions = {
    ('q_find0', 'X'): ('q_find0', 'X', 'R'),          # আগে চিহ্নিত 0 টপকে যাও
    ('q_find0', 'Y'): ('q_find0', 'Y', 'R'),          # আগে চিহ্নিত 1 টপকে যাও
    ('q_find0', '0'): ('q_goright', 'X', 'R'),        # leftmost 0 -- X দিয়ে চিহ্নিত করো
    ('q_find0', '1'): ('q_reject', '1', 'R'),         # 0 আশা করেছিলাম, 1 পেলাম -- reject
    ('q_find0', BLANK): ('q_accept', BLANK, 'R'),     # কিছুই বাকি নেই -- accept

    ('q_goright', '0'): ('q_goright', '0', 'R'),
    ('q_goright', '1'): ('q_goright', '1', 'R'),
    ('q_goright', 'X'): ('q_goright', 'X', 'R'),
    ('q_goright', 'Y'): ('q_goright', 'Y', 'R'),
    ('q_goright', BLANK): ('q_findlast', BLANK, 'L'), # ডানপ্রান্তে পৌঁছে এক ঘর পিছিয়ে আসি

    ('q_findlast', 'X'): ('q_findlast', 'X', 'L'),
    ('q_findlast', 'Y'): ('q_findlast', 'Y', 'L'),
    ('q_findlast', '1'): ('q_gohome', 'Y', 'L'),      # rightmost 1 -- Y দিয়ে চিহ্নিত করো
    ('q_findlast', '0'): ('q_reject', '0', 'L'),      # 1 আশা করেছিলাম, 0 পেলাম -- reject
    ('q_findlast', BLANK): ('q_reject', BLANK, 'L'),  # অচিহ্নিত 1 নেই -- reject

    ('q_gohome', '0'): ('q_gohome', '0', 'L'),
    ('q_gohome', '1'): ('q_gohome', '1', 'L'),
    ('q_gohome', 'X'): ('q_gohome', 'X', 'L'),
    ('q_gohome', 'Y'): ('q_gohome', 'Y', 'L'),
    ('q_gohome', BLANK): ('q_find0', BLANK, 'R'),     # টেপের শুরুতে ফিরে আবার শুরু করো
}
zn_tm = TuringMachine(zn_states, {'0', '1'}, {'0', '1', 'X', 'Y', BLANK},
                       zn_transitions, 'q_find0', 'q_accept', 'q_reject')


class TMEncoder:
    """একটি TM-কে (states, transitions, start, accept, reject) একটিমাত্র স্ট্রিং-এ এনকোড করে।"""
    SEP_FIELD, SEP_RULE, SEP_PARTS, SEP_ARROW = ';;', '|', ',', '>'

    @staticmethod
    def encode(tm):
        parts = [
            'STATES=' + TMEncoder.SEP_PARTS.join(sorted(tm.states)),
            'START=' + tm.start, 'ACCEPT=' + tm.accept, 'REJECT=' + tm.reject,
            'BLANK=' + tm.blank,
        ]
        rules = []
        for (state, symbol), (ns, ws, d) in tm.transitions.items():
            lhs = TMEncoder.SEP_PARTS.join([state, symbol])
            rhs = TMEncoder.SEP_PARTS.join([ns, ws, d])
            rules.append(lhs + TMEncoder.SEP_ARROW + rhs)
        parts.append('TRANS=' + TMEncoder.SEP_RULE.join(rules))
        return TMEncoder.SEP_FIELD.join(parts)

    @staticmethod
    def decode(encoded):
        fields = dict(f.split('=', 1) for f in encoded.split(TMEncoder.SEP_FIELD))
        states = set(fields['STATES'].split(TMEncoder.SEP_PARTS))
        transitions = {}
        if fields['TRANS']:
            for rule in fields['TRANS'].split(TMEncoder.SEP_RULE):
                lhs, rhs = rule.split(TMEncoder.SEP_ARROW)
                state, symbol = lhs.split(TMEncoder.SEP_PARTS)
                ns, ws, d = rhs.split(TMEncoder.SEP_PARTS)
                transitions[(state, symbol)] = (ns, ws, d)
        return (states, transitions, fields['START'], fields['ACCEPT'],
                fields['REJECT'], fields['BLANK'])


class UniversalSimulator:
    """<M> (এনকোডেড TM) + w (ইনপুট) নিয়ে M-কে ডিকোড করে জেনেরিকভাবে সিমুলেট করে --
    এটাই একটি ইউনিভার্সাল টুরিং মেশিনের মূল ধারণা।"""
    def __init__(self, encoded_tm):
        (self.states, self.transitions, self.start,
         self.accept, self.reject, self.blank) = TMEncoder.decode(encoded_tm)

    def run(self, input_string, max_steps=3000):
        tape = {i: c for i, c in enumerate(input_string)}
        head, state, steps = 0, self.start, 0
        while state != self.accept and state != self.reject and steps < max_steps:
            symbol = tape.get(head, self.blank)
            key = (state, symbol)
            if key not in self.transitions:
                return 'reject', steps
            ns, ws, d = self.transitions[key]
            tape[head] = ws
            head += 1 if d == 'R' else -1
            state = ns
            steps += 1
        if state == self.accept:
            return 'accept', steps
        elif state == self.reject:
            return 'reject', steps
        else:
            return 'timeout', steps


# --- verification: encode-decode-সিমুলেট চক্র, বনাম সরাসরি চালানো -- ফলাফল অভিন্ন হতে হবে ---
encoded_M = TMEncoder.encode(zn_tm)
print(f"এনকোডেড ⟨M⟩-এর দৈর্ঘ্য: {len(encoded_M)} ক্যারেক্টার\n")

universal = UniversalSimulator(encoded_M)
tests = ["", "0", "1", "01", "10", "0011", "000111", "0101", "011", "0001"]
print(f"{'w':12s} | {'সরাসরি M(w)':13s} | {'U(<M>,w)':13s} | মিলছে?")
print("-" * 52)
all_match = True
for w in tests:
    direct, _ = zn_tm.run(w)
    via_utm, _ = universal.run(w)
    match = (direct == via_utm)
    all_match = all_match and match
    print(f"{w!r:12s} | {direct:13s} | {via_utm:13s} | {'হ্যাঁ' if match else 'না'}")

print(f"\nসব টেস্ট স্ট্রিং-এ ফলাফল অভিন্ন: {all_match}")