ডিসাইডেবল বনাম টুরিং-রিকগনাইজেবল ল্যাঙ্গুয়েজ

১ · পুনরালোচনা ও নতুন পরিভাষা

L33-এ আমরা দেখেছিলাম টুরিং মেশিনের দুটো আচরণ — রিকগনাইজ করা আর ডিসাইড করা। এই মডিউলের (M9) পুরো বাকি অংশ এই পার্থক্যের উপরই দাঁড়িয়ে, তাই আরেকবার নির্ভুলভাবে বলা যাক —

• ডিসাইডেবলDecidable (recursive)একটি TM প্রতিটি সম্ভাব্য ইনপুটে হল্ট করে, সঠিকভাবে accept বা reject করে (recursive) ভাষা: এমন একটি TM আছে যা প্রতিটি ইনপুটে হল্ট করে — সদস্য স্ট্রিং accept করে, অ-সদস্য স্ট্রিং সরাসরি reject করে (লুপ করে না)।
• টুরিং-রিকগনাইজেবলTuring-recognizable (recursively enumerable)একটি TM সব YES-ইনস্ট্যান্সে accept করে হল্ট করে, কিন্তু NO-ইনস্ট্যান্সে লুপ করতেও পারে (recursively enumerable) ভাষা: এমন একটি TM আছে যা সদস্য স্ট্রিং-এ accept করে হল্ট করে, কিন্তু অ-সদস্য স্ট্রিং-এ হয় reject করে, নয়তো চিরকাল লুপ করতে পারে।
• Co-recognizableCo-recognizableL-এর complement, $\overline{L}$, যদি Turing-recognizable হয় ভাষা: $L$-এর complement, $\overline{L}$, যদি Turing-recognizable হয় — অর্থাৎ, "L-এ নেই" প্রশ্নটা recognize করা যায়।

L33-এর গুরুত্বপূর্ণ, প্রায়ই-ভুল-বোঝা অসামঞ্জস্যটা আবার জোর দিয়ে বলা দরকার — প্রতিটি ডিসাইডেবল ভাষা recognizable (একটি decider নিজেই একটি recognizer, শুধু "সবসময় হল্ট করে" এই বাড়তি গ্যারান্টিসহ) — কিন্তু উল্টোটা সত্য নয় — কিছু ভাষা recognizable হয়েও ডিসাইডেবল নয় (এমন একটি recognizer আছে, কিন্তু সেটি অন্তত কিছু non-member স্ট্রিং-এ চিরকাল লুপ করে — কোনোভাবেই সেই recognizer-কে decider-এ রূপান্তর করা যায় না)। M9/L39-এর হল্টিং প্রবলেম হবে এই ফাঁকের সবচেয়ে বিখ্যাত উদাহরণ।

২ · মূল থিওরেম: L ডিসাইডেবল $\iff$ L ও $\overline{L}$ উভয়ই recognizable

এই থিওরেমটি সত্যিই সুন্দর, কারণ এর প্রমাণ কনস্ট্রাক্টিভ — শুধু দাবি করে না, বরং সরাসরি দেখায় কীভাবে decider বানাতে হয়।

($\Rightarrow$) সহজ দিক: যদি $L$ ডিসাইডেবল হয়, তাহলে তার decider-এর accept/reject সিদ্ধান্তটা উল্টে দিলেই (accept বদলে reject, reject বদলে accept) সরাসরি $\overline{L}$-এর একটি decider (তাই recognizer-ও) পাওয়া যায় — তুচ্ছ।

($\Leftarrow$) গুরুত্বপূর্ণ দিক: ধরা যাক $L$-এর একটি recognizer $M_1$ আছে, এবং $\overline{L}$-এর একটি recognizer $M_2$ আছে। এখন একই ইনপুট $w$-এর উপর $M_1$ ও $M_2$-কে একই সাথে চালাই — একটি স্টেপ $M_1$-এর, একটি স্টেপ $M_2$-এর, এভাবে পালা করে (ইন্টারলিভড)। যেহেতু $w$ অবশ্যই $L$-এ আছে অথবা $\overline{L}$-এ আছে (একইসাথে দুটোতেই নয়, কখনোই কোনোটাতেই না-ও নয়) — $M_1, M_2$-এর মধ্যে ঠিক একজন নিশ্চিতভাবে কোনো-না-কোনো সসীম সংখ্যক স্টেপের পর accept করবে। যে আগে accept করে, তার সিদ্ধান্তই চূড়ান্ত উত্তর — এই ইন্টারলিভড সিমুলেশনটাই $L$-এর একটি decider, কারণ এটি সবসময় হল্ট করে (দুটোর মধ্যে একটা তো নিশ্চিতভাবে accept করবেই)।

৩ · Python-এ ইন্টারলিভড সিমুলেশন

নিচের কোড সেলে দুটো ভিন্ন জেনারেটর-স্টাইল রিকগনাইজার বানানো হচ্ছে — একটি $L$ = "স্ট্রিং-এ অন্তত একটি 1 আছে"-এর জন্য, আরেকটি $\overline{L}$ = "স্ট্রিং সম্পূর্ণ শূন্য দিয়ে গঠিত"-এর জন্য। প্রতিটি রিকগনাইজার একটি স্টেপ-বাই-স্টেপ জেনারেটর (ব্ল্যাক-বক্স ফাংশন কল নয়) — যদি নিজের ভাষায় সদস্যপদ প্রমাণ করতে ব্যর্থ হয়, সেটি সত্যিকারের একটি recognizer-এর মতোই চিরকাল 'continue' yield করতে থাকে (কখনো হল্ট করে না) — শুধু "সদস্য" পেলেই 'accept' yield করে থামে। interleaved_simulation এই দুটোকে পালা করে এক-এক স্টেপ চালিয়ে, যেটাই আগে accept করে সেটার উত্তর রিটার্ন করে।

def contains_one_recognizer(s):
    """L = 'স্ট্রিং-এ অন্তত একটি 1 আছে' -- একটি recognizer, জেনারেটর হিসেবে।
    '1' না পাওয়া গেলে চিরকাল 'continue' yield করে -- কখনো হল্ট করে না।"""
    def gen():
        i = 0
        while True:
            if i < len(s):
                if s[i] == '1':
                    yield 'accept'
                    return
                i += 1
                yield 'continue'
            else:
                yield 'continue'   # '1' পাওয়া যায়নি -- চিরকাল লুপ (কখনো হল্ট করে না)
    return gen()


def all_zeros_recognizer(s):
    """L̄ = 'স্ট্রিং সম্পূর্ণ শূন্য দিয়ে গঠিত' -- এটাও একটি recognizer।
    কোনো non-zero পেলে চিরকাল লুপ করে -- কখনো হল্ট করে না।"""
    def gen():
        i, stuck = 0, False
        while True:
            if stuck:
                yield 'continue'
                continue
            if i >= len(s):
                yield 'accept'
                return
            if s[i] != '0':
                stuck = True        # non-zero পাওয়া গেছে -- এই recognizer আর কখনো accept করবে না
                yield 'continue'
                continue
            i += 1
            yield 'continue'
    return gen()


def interleaved_simulation(gen1, gen2, max_total_steps=2000):
    """L38-থিওরেমের কনস্ট্রাক্টিভ প্রমাণ -- L আর L̄-এর দুটো recognizer-কে একটি করে
    স্টেপ পালা করে চালানো হয় -- যেটা আগে accept করে, সেটাই চূড়ান্ত সিদ্ধান্ত।"""
    steps = 0
    while steps < max_total_steps:
        r1 = next(gen1)
        steps += 1
        if r1 == 'accept':
            return 'L', steps
        if steps >= max_total_steps:
            break
        r2 = next(gen2)
        steps += 1
        if r2 == 'accept':
            return 'complement of L', steps
    return 'timeout', steps


# --- যাচাই: প্রতিটি স্ট্রিং-এ ডিসাইডার নিশ্চিতভাবে হল্ট করে ও সঠিক উত্তর দেয় ---
tests = ["", "0", "1", "000", "111", "0001", "1000", "00000001", "0000000"]
print(f"{'w':12s} | {'সিদ্ধান্ত':17s} | স্টেপ | প্রত্যাশিত মিলছে?")
print("-" * 58)
all_correct = True
for s in tests:
    expected = 'L' if '1' in s else 'complement of L'
    which, steps = interleaved_simulation(contains_one_recognizer(s), all_zeros_recognizer(s))
    correct = (which == expected)
    all_correct = all_correct and correct
    print(f"{s!r:12s} | {which:17s} | {steps:4d}  | {'হ্যাঁ' if correct else 'না'}")

print(f"\nপ্রতিটি টেস্টে ডিসাইডার হল্ট করেছে ও সঠিক উত্তর দিয়েছে: {all_correct}")