রাইসের থিওরেম

import itertools

BLANK = '_'

class TuringMachine:
    """L32/L37-এর ধাঁচের একটি জেনেরিক TM।"""
    def __init__(self, transitions, start, accept, reject, blank=BLANK):
        self.transitions = transitions
        self.start, self.accept, self.reject, self.blank = start, accept, reject, 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
            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


# L37-এর M -- L = {0^n 1^n : n >= 0}
zn_transitions = {
    ('q_find0', 'X'): ('q_find0', 'X', 'R'), ('q_find0', 'Y'): ('q_find0', 'Y', 'R'),
    ('q_find0', '0'): ('q_goright', 'X', 'R'), ('q_find0', '1'): ('q_reject', '1', 'R'),
    ('q_find0', BLANK): ('q_accept', BLANK, 'R'),
    ('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'), ('q_findlast', '0'): ('q_reject', '0', 'L'),
    ('q_findlast', BLANK): ('q_reject', BLANK, 'L'),
    ('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'),
}
M = TuringMachine(zn_transitions, 'q_find0', 'q_accept', 'q_reject')


class TMEncoder:
    SEP_FIELD, SEP_RULE, SEP_PARTS, SEP_ARROW = ';;', '|', ',', '>'

    @staticmethod
    def encode(tm):
        parts = ['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))
        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 transitions, fields['START'], fields['ACCEPT'], fields['REJECT'], fields['BLANK']


class UniversalSimulator:
    def __init__(self, encoded_tm):
        (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


def build_Mw(m_encoded, w, buffer=60):
    """L40-এর রিডাকশন কনস্ট্রাকশনের হুবহু পুনর্ব্যবহার -- M_w তার নিজের ইনপুট ignore
    করে, নিরাপদে দূরে সরে গিয়ে w লেখে, তারপর M-কে সেই w-এর উপর চালায়।"""
    transitions, start, accept, reject, blank = TMEncoder.decode(m_encoded)
    new_transitions = dict(transitions)
    seek_len = buffer + max(len(w), 1)
    for i in range(seek_len):
        cur = f'mw_seek_{i}'
        nxt = f'mw_seek_{i+1}' if i + 1 < seek_len else 'mw_write_0'
        for sym in ('0', '1', blank):
            new_transitions[(cur, sym)] = (nxt, sym, 'L')
    if len(w) == 0:
        for sym in ('0', '1', blank):
            new_transitions[('mw_write_0', sym)] = ('mw_return_0', sym, 'R')
    else:
        for i, ch in enumerate(w):
            cur = f'mw_write_{i}'
            nxt = f'mw_write_{i+1}' if i + 1 < len(w) else 'mw_return_0'
            for sym in ('0', '1', blank):
                new_transitions[(cur, sym)] = (nxt, ch, 'R')
    return_len = max(len(w), 1)
    for i in range(return_len):
        cur = f'mw_return_{i}'
        nxt = f'mw_return_{i+1}' if i + 1 < return_len else start
        for sym in ('0', '1', blank):
            new_transitions[(cur, sym)] = (nxt, sym, 'L')
    return TMEncoder.encode(TuringMachine(new_transitions, 'mw_seek_0', accept, reject, blank))


def bounded_nonempty_property_checker(m_encoded, max_len=4, max_steps=500):
    """(বাউন্ডেড approximation, সত্যিকারের general decider নয় -- রাইসের থিওরেম অনুযায়ী
    এমন কিছু থাকতেই পারে না) -- max_len পর্যন্ত সব স্ট্রিং খুঁজে দেখে, প্রথম accept পেলেই True।"""
    sim = UniversalSimulator(m_encoded)
    for length in range(max_len + 1):
        for bits in itertools.product('01', repeat=length):
            candidate = ''.join(bits)
            result, _ = sim.run(candidate, max_steps=max_steps)
            if result == 'accept':
                return True
    return False


def reduces_to_halt_via_rice_pattern(m_encoded, w, property_checker):
    """L40-এর build_Mw প্যাটার্নই পুনরায় ব্যবহার -- এবার E_TM-এর বদলে 'L(M)-এ অন্তত
    একটি স্ট্রিং আছে' প্রপার্টির জন্য -- রাইসের থিওরেমের অনেক instance-ই যে একই
    আন্ডারলাইং রিডাকশন টেকনিক শেয়ার করে, তা কংক্রিটভাবে দেখায়।"""
    mw_encoded = build_Mw(m_encoded, w)
    return property_checker(mw_encoded)


# --- ১) রাইসের থিওরেমের দুই শর্ত অনুযায়ী কয়েকটি উদাহরণ প্রপার্টি ক্লাসিফাই করা ---
properties = {
    "L(M) খালি (E_TM)": {
        "is_language_property": True, "is_nontrivial": True,
        "note": "কিছু TM-এর ভাষা খালি, কিছুর নয় -- L40-এ সরাসরি আনডিসাইডেবল প্রমাণিত",
    },
    "L(M)-এ 'ab' স্ট্রিং আছে": {
        "is_language_property": True, "is_nontrivial": True,
        "note": "কিছু TM-এর ভাষায় 'ab' আছে, কিছুর নেই",
    },
    "L(M) = Sigma* (সব স্ট্রিং accept করে)": {
        "is_language_property": True, "is_nontrivial": True,
        "note": "কিছু TM সব স্ট্রিং accept করে, কিছু করে না",
    },
    "L(M) রেগুলার": {
        "is_language_property": True, "is_nontrivial": True,
        "note": "কিছু TM-এর ভাষা রেগুলার (যেমন Sigma*), কিছুর নয় (যেমন 0^n1^n)",
    },
    "M-এর ঠিক ৫টি state আছে": {
        "is_language_property": False, "is_nontrivial": True,
        "note": "L(M)-এর উপর নির্ভর করে না, M-এর নিজস্ব বর্ণনার উপর -- Rice প্রযোজ্য নয়",
    },
    "L(M) একটি ভাষা (সবসময় সত্য)": {
        "is_language_property": True, "is_nontrivial": False,
        "note": "প্রতিটি TM-এর জন্যই vacuously সত্য -- trivial, তাই Rice প্রযোজ্য নয়",
    },
}

print(f"{'প্রপার্টি':34s} | ভাষা-প্রপার্টি | নন-ট্রিভিয়াল | Rice প্রযোজ্য?")
print("-" * 92)
for name, info in properties.items():
    rice_applies = info["is_language_property"] and info["is_nontrivial"]
    verdict = "হ্যাঁ -- আনডিসাইডেবল" if rice_applies else "না"
    print(f"{name:34s} | {str(info['is_language_property']):13s} | {str(info['is_nontrivial']):13s} | {verdict}")
    print(f"    ({info['note']})")

# --- ২) L40-এর একই M_w প্যাটার্ন 'L(M)-এ অন্তত একটি স্ট্রিং আছে' প্রপার্টির জন্য ---
print()
m_encoded = TMEncoder.encode(M)
for w, expected_accepts in [("0011", True), ("01001", False)]:
    direct, _ = M.run(w)
    guessed_nonempty = reduces_to_halt_via_rice_pattern(m_encoded, w, bounded_nonempty_property_checker)
    print(f"M({w!r}) সরাসরি = {direct}; M_w-এর property-checker অনুমান করলো nonempty={guessed_nonempty} "
          f"(প্রত্যাশিত M accepts w = {expected_accepts})")
    assert guessed_nonempty == expected_accepts

print("\nRice reduction pattern -- একই M_w কনস্ট্রাকশন ভিন্ন প্রপার্টির জন্যও সঠিকভাবে কাজ করলো।")