সরাসরি পর্বে যান
পর্ব ৫৩ · ৮৫-এর মধ্যে · মডিউল ৯

Rice-এর theorem — program-এর আচরণ নিয়ে প্রশ্ন

Rice's Theorem — Semantic vs Syntactic Properties, the Proof by Reduction from ATM, Examples, Limits, and What It Means for Program Analysis

Taught in Bangla, this lesson states Rice's theorem: every non-trivial semantic property of the language a Turing machine accepts is undecidable. It explains the two conditions, semantic and non-trivial, proves the theorem by reducing A_TM and builds the machine M_w in in-page Python (Pyodide). It classifies example questions, marks the boundary (including Rice–Shapiro), and explains why perfect virus and dead-code detectors cannot exist and real static analysis must give up soundness or completeness.

এই পর্বে যা শিখবেন

  • Turing machine-এর ধর্মকে language হিসেবে লেখা, আর semantic, syntactic, trivial ও non-trivial ধর্ম আলাদা করা
  • Rice-এর theorem-এর সুনির্দিষ্ট বিবৃতি আর ATM থেকে mapping reduction দিয়ে পূর্ণ প্রমাণ, সঙ্গে “∅-এর ধর্ম থাকলে recognizable-ও নয়” corollary
  • কোন প্রশ্নে Rice খাটে, কোনটিতে খাটে না, আর না খাটলেও কিছু প্রশ্ন কেন undecidable
  • Python আর JavaScript-এ reduction-টি ছোট যন্ত্রে চালিয়ে দেখা, আর একটি ধর্ম semantic কি না, তা উদাহরণ দিয়ে খণ্ডন করা
  • Static analysis, virus detection আর compiler-এর জন্য sound বনাম complete আপসের মানে

১ · বাজারঘরের প্রশ্ন — “এই script কি কখনো অর্ডার ফ্রি করে দেবে?”

বাজারঘরে প্রতিদিন নতুন discount-script জমা পড়ে। প্রতিটি script একটি অর্ডার-নম্বর পেয়ে দাম হিসাব করে। দলের প্রধান একটি স্বয়ংক্রিয় যাচাইকারী চান: script জমা দিলেই যন্ত্রটি বলবে, “এই script কি কোনো অর্ডারকে কখনো বিনা দামে ছেড়ে দেবে?” প্রশ্নটি কোডের চেহারা নিয়ে নয়, কোডের আচরণ নিয়ে: কোন input-এ কী ফল আসে।

আগের পর্বগুলোতে এমন একটি প্রশ্নের উত্তর পেয়েছেন। Universal machine (পর্ব ৪৮) যেকোনো যন্ত্র চালাতে পারে, কিন্তু চালানো আর “আগেই জানা” এক নয়। পর্ব ৫১-এ diagonalization দিয়ে দেখানো হয়, ATM = {⟨M, w⟩ : M w গ্রহণ করে} undecidable, আর পর্ব ৫২-এ mapping reduction দিয়ে ETM (L(M) কি ফাঁকা?) আর REGULARTM (L(M) কি regular?) একই দলে ঢোকে। প্রতিটির জন্য আলাদা প্রমাণ লিখতে হয়েছে। এই পর্বের theorem সব প্রমাণকে এক ধাক্কায় সাধারণ করে: যন্ত্রের language নিয়ে যেকোনো অর্থবহ প্রশ্নই undecidable.

পরীক্ষার খাতা দেখার কথা ভাবুন। “খাতায় কয়টি পাতা আছে” বা “নাম-রোল লেখা আছে কি না” পরীক্ষক খাতা খুলেই বলতে পারেন: এগুলো খাতার চেহারা। কিন্তু “এই ছাত্রের লেখা algorithm কি প্রতিটি input-এ সঠিক উত্তর দেবে?” প্রশ্নের উত্তর খাতার চেহারায় নেই, আছে algorithm-টি আসলে কী করে তার মধ্যে। Rice-এর theorem বলে, এই দ্বিতীয় ধরনের প্রশ্নের জন্য কোনো “সব খাতায় নির্ভুল” স্বয়ংক্রিয় পরীক্ষক বানানো যায় না।

কথাটি প্রথম শুনলে অতিরঞ্জিত মনে হয়। তাই এই পর্বে আমরা সতর্কভাবে এগোব: প্রথমে “ধর্ম” শব্দটিকে গাণিতিক রূপ দেব, তারপর theorem আর প্রমাণ, তারপর Python-এ reduction-টি ছোট যন্ত্রে চালিয়ে দেখব, আর শেষে দেখব theorem কোথায় খাটে না। ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৫-এ Rice-এর এক অনুচ্ছেদের পরিচয় আছে; এখানে পূর্ণ প্রমাণ আর সীমানা নিয়ে অনেক গভীরে যাব।

২ · “ধর্ম” কী — semantic বনাম syntactic, trivial বনাম non-trivial

পর্ব ০৫-এর রীতিতে প্রতিটি প্রশ্নই একটি language: যেসব input-এ উত্তর “হ্যাঁ”, তাদের set. Turing machine-এর একটি ধর্ম তাই একটি set P, যার সদস্য কিছু যন্ত্রের বর্ণনা ⟨M⟩. যেমন emptiness-এর প্রশ্ন:

ETM = {⟨M⟩ : M একটি Turing machine আর L(M) = ∅}
সংজ্ঞা ২.১ (Turing machine-এর ধর্ম)

ধরুন P হলো Turing machine-এর বর্ণনার একটি set.
১. P semantic (language-এর ধর্ম), যদি যেকোনো দুটি যন্ত্র M1, M2-এর জন্য L(M1) = L(M2) হলে ⟨M1⟩ ∈ P ⇔ ⟨M2⟩ ∈ P. অর্থাৎ উত্তর শুধু L(M)-এর ওপর নির্ভর করে, M-এর কোড কেমন তার ওপর নয়।
২. P non-trivial, যদি অন্তত একটি যন্ত্রের বর্ণনা P-তে থাকে আর অন্তত একটির বর্ণনা P-তে না থাকে।
৩. যে ধর্ম semantic নয়, অর্থাৎ যার উত্তর কোডের খুঁটিনাটির ওপর নির্ভর করে, তাকে এই পর্বে syntactic বা গঠনগত ধর্ম বলব।

সমতুল্যভাবে, একটি semantic ধর্ম আসলে recognizable language-গুলোর একটি শ্রেণি 𝒞: P = {⟨M⟩ : L(M) ∈ 𝒞}. গণিতের বইয়ে এমন P-কে 𝒞-এর index set বলা হয়। Non-trivial মানে 𝒞 ফাঁকা নয়, আর সব recognizable language-ও 𝒞-তে নেই।

ধর্মSemantic?Non-trivial?
L(M) = ∅হ্যাঁহ্যাঁ
BG-0042 ∈ L(M)হ্যাঁহ্যাঁ
L(M) একটি regular languageহ্যাঁহ্যাঁ
L(M) Turing-recognizableহ্যাঁনা: সব যন্ত্রের আছে
M-এর ঠিক ৫টি stateনাহ্যাঁ
M সব input-এ থামেনাহ্যাঁ

শেষ সারিটি সূক্ষ্ম, তাই একটু থামুন। ধরুন M1 “a দিয়ে শুরু হলে গ্রহণ, নইলে বর্জন” করে, আর M2 “a দিয়ে শুরু হলে গ্রহণ, নইলে চিরকাল ডানে হাঁটে”। দুটির language হুবহু এক, a(a ∪ b)∗, কিন্তু M1 সব input-এ থামে, M2 থামে না। একই language, ভিন্ন উত্তর: তাই “সব input-এ থামা” semantic নয়। মনে রাখুন, এখানে “semantic” মানে ঠিক “শুধু গৃহীত string-এর set-এর ওপর নির্ভর করে”, আচরণের সব খুঁটিনাটি (কত ধাপ, কোথায় loop) নয়।

৩ · Rice-এর theorem আর তার প্রমাণ

উপপাদ্য ৩.১ (Rice-এর theorem — H. G. Rice, ১৯৫৩)

Turing machine-এর প্রতিটি non-trivial semantic ধর্ম P undecidable. অর্থাৎ এমন কোনো decider নেই, যা প্রতিটি ⟨M⟩ পেয়ে থামে আর ঠিক বলে ⟨M⟩ ∈ P কি না।

প্রমাণের কৌশল পর্ব ৫২-এর মতোই: একটি জানা undecidable language, ATM, থেকে P-তে reduction. দিকের নিয়মটি আবার মনে করুন, কারণ ভুল দিকে reduction এই বিষয়ের সবচেয়ে সাধারণ ভুল:

A ≤m B আর B decidable ⇒ A decidable; তাই A undecidable ⇒ B undecidable

আমাদের A = ATM, B = P. তাই দেখাতে হবে ATM ≤m P, উল্টোটা নয়। দরকারি দুটি যন্ত্র: T∅, যা প্রতিটি input তৎক্ষণাৎ বর্জন করে (L(T∅) = ∅), আর P-এর একটি সদস্য T. নিচের ছবি পুরো নির্মাণটি দেখায়।

Rice-এর reduction: ⟨M, w⟩ থেকে ⟨Mw⟩

f শুধু কোড লেখে, M চালায় না। Mw-এর language দুটির একটি: L(T) অথবা ∅.

The reduction in the proof of Rice's theorem ⟨M, w⟩ f: computable শুধু ⟨Mw⟩-এর কোড লেখে Mw, input x: ধাপ ১: M-কে w-এর ওপর চালানো গ্রহণ বর্জন বা loop ধাপ ২: T-এর মতো x-এ চলা কোনো x গৃহীত নয় L(Mw) = L(T) L(Mw) = ∅ R: P-এর decider (ধরে নেওয়া) হ্যাঁ ⇔ M w গ্রহণ করে
ছবি ৫৩.১ — ⟨T∅⟩ ∉ P আর ⟨T⟩ ∈ P বলে, Mw P-তে আছে ঠিক তখন, যখন M w গ্রহণ করে। ডটেড বাক্সটি কল্পিত: প্রমাণ দেখায় এমন R থাকতে পারে না।

প্রমাণ (উপপাদ্য ৩.১):

  1. বিরোধের জন্য ধরুন R একটি decider, যা P decide করে। — অনুমান
  2. প্রথমে ধরুন ⟨T∅⟩ ∉ P. (যদি ⟨T∅⟩ ∈ P হয়, তবে complement P̄ নিন: P̄-ও semantic আর non-trivial, ⟨T∅⟩ ∉ P̄, আর R-এর উত্তর উল্টে দিলে P̄-এর decider পাওয়া যায়। তাই P̄-এর জন্য বাকি প্রমাণ চালালেই হবে।) — সাধারণতা না হারিয়ে
  3. P non-trivial, তাই এমন একটি যন্ত্র T আছে যাতে ⟨T⟩ ∈ P. — non-trivial-এর সংজ্ঞা
  4. f সংজ্ঞায়িত করুন: input ⟨M, w⟩ হলে output ⟨Mw⟩, যেখানে Mw = “input x-এর ওপর: M-কে w-এর ওপর চালান। M বর্জন করলে বর্জন করুন। M গ্রহণ করলে T-কে x-এর ওপর চালান আর T-এর রায় দিন।” Input বৈধ ⟨M, w⟩ না হলে output ⟨T∅⟩. — নির্মাণ
  5. f একটি computable function: এটি শুধু M, w আর T-এর কোড জোড়া লাগিয়ে নতুন কোড লেখে, M-কে কখনো চালায় না, তাই প্রতিটি input-এ থামে। — reduction-এর প্রথম শর্ত
  6. M যদি w গ্রহণ করে, তবে প্রতিটি x-এ Mw ধাপ ২-এ পৌঁছায় আর T-এর মতো আচরণ করে, তাই L(Mw) = L(T). P semantic, তাই ⟨Mw⟩ ∈ P. — semantic শর্ত এখানে লাগে
  7. M যদি w গ্রহণ না করে (বর্জন করে বা loop করে), তবে কোনো x-এ Mw গ্রহণ করে না, তাই L(Mw) = ∅ = L(T∅). আবার semantic শর্তে ⟨Mw⟩ ∉ P, কারণ ⟨T∅⟩ ∉ P. — দ্বিতীয় দিক
  8. ধাপ ৬ আর ৭ মিলে: ⟨M, w⟩ ∈ ATM ⇔ f(⟨M, w⟩) ∈ P. অর্থাৎ ATM ≤m P. — mapping reduction
  9. তাহলে S = “input ⟨M, w⟩-এ f চালিয়ে R-কে জিজ্ঞেস করুন, R-এর উত্তর দিন” ATM decide করে। কিন্তু পর্ব ৫১ অনুযায়ী ATM undecidable. বিরোধ, তাই R নেই। ∎ — দিকের নিয়ম

লক্ষ করুন, ধাপ ৭-এ loop-এর ক্ষেত্রটি কোনো সমস্যা করে না: M w-এ loop করলে Mw প্রতিটি x-এ loop করে, আর loop মানে গ্রহণ নয়, তাই L(Mw) = ∅. যন্ত্র নিজে থামুক বা না থামুক, language নিয়ে প্রশ্নে শুধু “গৃহীত কি না” গোনা হয়। নিচের stepper P = {⟨M⟩ : BG-0042 ∈ L(M)} আর T = “শুধু BG-0042 গ্রহণ করে” নিয়ে তিনটি ক্ষেত্র ধাপে ধাপে দেখায়।

1f: input ⟨M, w⟩2f: ⟨M_w⟩ লেখা (M চালানো নয়)3M_w(x): M-কে w-এ চালানো4  বর্জন হলে: বর্জন5  গ্রহণ হলে: T-কে x-এ চালানো6R(⟨M_w⟩) = ?
এই ধাপে
(M, w)
M w-তে
L(M_w)
R-এর উত্তর
  1. অনুমান। P = {⟨M⟩ : BG-0042 ∈ L(M)}. T∅ সব বর্জন করে, তাই ⟨T∅⟩ ∉ P; T শুধু BG-0042 গ্রহণ করে, তাই ⟨T⟩ ∈ P. ধরে নিই R নামের একটি decider P decide করে।
  2. f কোড লেখে। f ⟨M, w⟩ পড়ে ⟨Mw⟩-এর কোড লেখে: M-এর কোড, w-এর কপি আর T-এর কোড জোড়া লাগিয়ে। M একবারও চালানো হয় না, তাই M loop করলেও f থামে।
  3. Mw-এর গঠন। Mw নিজের input x প্রথমে উপেক্ষা করে, M-কে স্থির w-এর ওপর চালায়। শুধু M গ্রহণ করলে ধাপ ২-এ গিয়ে T-এর মতো x বিচার করে।
  4. ক্ষেত্র ১: M w গ্রহণ করে। ACC শুধু ab গ্রহণ করে, w = ab. প্রতিটি x-এ Mw ধাপ ২-এ পৌঁছায়, তাই L(Mw) = L(T) = {BG-0042}, আর R বলে “হ্যাঁ”।
  5. ক্ষেত্র ২: M w বর্জন করে। w = ba হলে ACC বর্জন করে, Mw প্রতিটি x বর্জন করে। L(Mw) = ∅, তাই R বলে “না”।
  6. ক্ষেত্র ৩: M w-এ loop করে। LOOP কখনো থামে না, তাই Mw প্রতিটি x-এ loop করে। Loop মানে গ্রহণ নয়: L(Mw) = ∅, R আবার বলে “না”। R নিজে কিন্তু থামে, কারণ সে decider.
  7. উপসংহার। তিন ক্ষেত্রে R-এর উত্তর “হ্যাঁ” ঠিক তখন, যখন M w গ্রহণ করে। তাই R ∘ f একটি ATM-এর decider হতো, যা পর্ব ৫১ অনুযায়ী অসম্ভব। অতএব R নেই।
অনুসিদ্ধান্ত ৩.২ (∅-এর ধর্ম থাকলে recognizable-ও নয়)

P non-trivial semantic আর ⟨T∅⟩ ∈ P হলে P Turing-recognizable-ও নয়।

প্রমাণ:

  1. P̄ non-trivial, semantic আর ⟨T∅⟩ ∉ P̄. উপপাদ্য ৩.১-এর ধাপ ৩–৮ P̄-এর জন্য চালালে একটি computable f পাই, যাতে ⟨M, w⟩ ∈ ATM ⇔ f(⟨M, w⟩) ∈ P̄. — একই নির্মাণ
  2. দুই দিকেই “না” বসালে: ⟨M, w⟩ ∈ A̅TM ⇔ f(⟨M, w⟩) ∈ P, অর্থাৎ A̅TM ≤m P. (বৈধ encoding নয় এমন string-এর খুঁটিনাটি পর্ব ৫২-এর রীতিতে সামলানো যায়।) — ⇔ দুই দিকেই উল্টানো যায়
  3. P recognizable হলে A̅TM-ও recognizable হতো। কিন্তু ATM recognizable আর undecidable, তাই পর্ব ৫০-এর “L আর L̄ দুটিই recognizable ⇔ L decidable” অনুযায়ী A̅TM recognizable নয়। বিরোধ। ∎

উদাহরণ: ETM-এ T∅ আছে, তাই ETM শুধু undecidable নয়, recognizable-ও নয়; এর complement অবশ্য recognizable (বিভিন্ন string-এ পালা করে চালিয়ে একটি গৃহীত string খুঁজলেই হয়), তাই ETM co-recognizable. অন্যদিকে “BG-0042 ∈ L(M)” recognizable: M-কে BG-0042-এর ওপর চালান, গ্রহণ করলে গ্রহণ। Rice-এর theorem নিজে recognizability সম্পর্কে কিছু বলে না; সেই প্রশ্ন অংশ ৬-এর Rice–Shapiro-র এলাকা।

৪ · Python-এ reduction — Mw বানানো আর চালানো

প্রমাণটি কাগজে বিমূর্ত লাগে। তাই এবার f-কে সত্যিকারের কোডে লিখি। এখানে একটি “যন্ত্র” হলো একটি Python generator function: প্রতিটি yield একটি ধাপ, return True মানে গ্রহণ, return False মানে বর্জন, আর কখনো return না করা মানে loop. run ধাপ গুনে চালায়, step cap 3000 ছুঁলে বলে cap, যার মানে শুধু “এখনো থামেনি”। আসল কাজটি f: এটি Mw নামের একটি নতুন function বানায়, কিন্তু M-কে চালায় না, ঠিক প্রমাণের ধাপ ৫-এর মতো।

# A toy "machine" is a Python generator function: one yield = one step,
# return True = accept, return False = reject, never returning = loop.
def run(M, x, cap=3000):                 # step-capped runner
    g, steps = M(x), 0
    while steps < cap:
        try: next(g)
        except StopIteration as e: return ("acc" if e.value else "rej"), steps
        steps += 1
    return "cap", steps
def T(x):                                # L(T) = {"BG-0042"}: has property P
    for _ in x: yield
    return x == "BG-0042"
def f(M, w):                             # the reduction: BUILDS M_w, never runs it
    def Mw(x):
        ok = yield from M(w)             # stage 1: run M on the fixed w
        if not ok: return False
        return (yield from T(x))         # stage 2: behave exactly like T on x
    return Mw
def ACC(w): yield; return w == "ab"      # accepts only "ab"
def REJ(w): yield; return False          # rejects everything
def LOOP(w):                             # loops on every input
    while True: yield
def SLOW(w):                             # accepts every w, but after 5000 steps
    for _ in range(5000): yield
    return True
X = ["", "ab", "BG-0042", "BG-0043"]
for name, M, w in [("ACC", ACC, "ab"), ("ACC", ACC, "ba"), ("REJ", REJ, "ab"),
                   ("LOOP", LOOP, "ab"), ("SLOW", SLOW, "ab")]:
    print(f"{name:4} w={w}: M on w -> {run(M, w)[0]:3} | M_w on X:",
          [run(f(M, w), x)[0] for x in X])
def fake_R(Mw):                          # a claimed decider for P (bounded run)
    return run(Mw, "BG-0042", cap=1000)[0] == "acc"
print("fake A_TM decider on (SLOW, ab):", fake_R(f(SLOW, "ab")),
      "| truth:", run(SLOW, "ab", cap=10**4)[0])

আসল আউটপুট (ব্রাউজারের Python):

ACC  w=ab: M on w -> acc | M_w on X: ['rej', 'rej', 'acc', 'rej']
ACC  w=ba: M on w -> rej | M_w on X: ['rej', 'rej', 'rej', 'rej']
REJ  w=ab: M on w -> rej | M_w on X: ['rej', 'rej', 'rej', 'rej']
LOOP w=ab: M on w -> cap | M_w on X: ['cap', 'cap', 'cap', 'cap']
SLOW w=ab: M on w -> cap | M_w on X: ['cap', 'cap', 'cap', 'cap']
fake A_TM decider on (SLOW, ab): False | truth: acc

প্রথম লাইন ক্ষেত্র ১: ACC ab গ্রহণ করে, আর Mw চারটি নমুনা string-এর মধ্যে ঠিক BG-0042 গ্রহণ করে, অর্থাৎ T-এর মতো আচরণ। দ্বিতীয় আর তৃতীয় লাইনে M w বর্জন করে, তাই Mw সব বর্জন করে: language ∅. চতুর্থ লাইনে LOOP: Mw প্রতিটি x-এ cap ছোঁয়, কিছুই গ্রহণ করে না। পঞ্চম লাইনটি সবচেয়ে শিক্ষণীয়: SLOW আসলে ab গ্রহণ করে, কিন্তু ৫০০০ ধাপ পরে, তাই ৩০০০-এর cap-এ LOOP আর SLOW হুবহু এক রকম দেখায়। শেষ লাইনে একটি “সীমিত ধাপ চালানো” নকল decider fake_R-কে f-এর সঙ্গে জুড়ে ATM-এর উত্তর চাওয়া হয়েছে: সে বলে False, অথচ সত্যি উত্তর acc. যেকোনো ধাপ-সীমার জন্য এমন একটি ধীর যন্ত্র বানানো যায়; আর উপপাদ্য ৩.১ বলে, শুধু ধাপ-সীমা নয়, কোনো কৌশলের decider-ই সব যন্ত্রে ঠিক হবে না। মনে রাখুন, কোডটি প্রমাণ নয়; এটি প্রমাণের নির্মাণকে ছোট উদাহরণে চোখের সামনে আনে।

৫ · কোন প্রশ্নে Rice খাটে — উদাহরণ আর শ্রেণিবিভাগ

Rice প্রয়োগ করতে দুটি প্রশ্ন জিজ্ঞেস করুন: (ক) একই language-এর দুটি যন্ত্রের উত্তর কি সবসময় এক? (খ) এমন যন্ত্র কি আছে যার ধর্মটি আছে, আর এমন যন্ত্র কি আছে যার নেই? দুটির উত্তর “হ্যাঁ” হলে ধর্মটি undecidable, আর কোনো reduction লিখতে হয় না। নিচের ধর্মগুলো সবই Rice দিয়ে সরাসরি undecidable:

  • L(M) = ∅ (ETM), L(M) = Σ∗, L(M) সসীম, L(M) অসীম
  • L(M) regular, L(M) context-free, L(M) decidable
  • BG-0042 ∈ L(M), L(M)-এ অন্তত একটি palindrome আছে, |L(M)| = 3
  • L(M) = {w : w-এ জোড় সংখ্যক 1}, অর্থাৎ “M কি ঠিক এই নির্দিষ্ট কাজটি করে?”

শেষ উদাহরণটি বিশেষভাবে লক্ষ করুন: “একটি program কি তার specification হুবহু মানে?” প্রশ্নটিও একটি non-trivial semantic ধর্ম, যদি specification-টি একটি language হিসেবে লেখা যায়। পর্ব ৫২-এর REGULARTM প্রমাণে যে বিশেষ নির্মাণ লেগেছিল, Rice-এর ছাতার নিচে তা এক লাইনে আসে: ∅ regular, {0n1n} regular নয়, তাই ধর্মটি non-trivial, আর language-এর ধর্ম বলে semantic.

1L(M) = ∅2L(M) সসীম3M-এর ঠিক ৫টি state4L(M) recognizable5M সব input-এ থামে6M ε গ্রহণ করে ≤ 100 ধাপে
পরীক্ষা
semantic?
non-trivial?
Rice খাটে?
রায়
  1. L(M) = ∅। একই language-এর দুটি যন্ত্রের উত্তর এক, তাই semantic. T∅-এর ধর্মটি আছে, “a দিয়ে শুরু হলে গ্রহণ” করা START_A-এর নেই, তাই non-trivial. Rice: undecidable, আর অনুসিদ্ধান্ত ৩.২ অনুযায়ী recognizable-ও নয়।
  2. L(M) সসীম। Semantic; ∅ সসীম, Σ∗ সসীম নয়, তাই non-trivial. Undecidable. ∅-এর ধর্মটি আছে, তাই এটিও recognizable নয়।
  3. ঠিক ৫টি state. START_A-এর state ৩টি (q0, qacc, qrej); তাতে দুটি অপ্রাপ্য state জুড়লে ৫টি, অথচ language একই। উত্তর বদলায়, তাই semantic নয়, Rice খাটে না। ⟨M⟩ পড়ে state গুনলেই উত্তর: decidable.
  4. L(M) recognizable. প্রতিটি Turing machine-এর language সংজ্ঞা অনুযায়ীই recognizable, তাই ধর্মটি সবার আছে: trivial. “সবসময় হ্যাঁ” বলা যন্ত্রটিই decider.
  5. সব input-এ থামা। অংশ ২-এর M1, M2: একই language, একটি থামে, একটি থামে না। তাই semantic নয়, Rice খাটে না। তবু ধর্মটি undecidable: HALTTM থেকে আলাদা reduction লাগে (অংশ ৬)।
  6. ε-কে ১০০ ধাপের মধ্যে গ্রহণ। একটি যন্ত্র ε এক ধাপে গ্রহণ করে, তার ধীর সংস্করণ ২০০ ধাপে; language এক, উত্তর ভিন্ন, তাই semantic নয়। M-কে ε-এর ওপর ঠিক ১০০ ধাপ চালালেই উত্তর মেলে: decidable.

একটি ধর্ম semantic নয়, তা দেখানোর উপায় খুব হাতে-কলমে: একই language-এর দুটি যন্ত্র খুঁজুন, যাদের উত্তর ভিন্ন। নিচের JavaScript ব্লক দুটি ছোট Turing machine নেয় (START_A: a দিয়ে শুরু হলে গ্রহণ; EVEN: জোড় দৈর্ঘ্য হলে গ্রহণ), আর দুটি এমন রূপান্তর, যা language কখনো বদলায় না: pad দুটি unreachable state জোড়ে, আর detour শুরুতে একবার ডানে গিয়ে আবার বাঁয়ে ফেরে। তারপর পাঁচটি ধর্ম প্রতিটি (যন্ত্র, রূপান্তর) জোড়ায় পরীক্ষা করে।

// A TM is {start, d}: d["q,a"] = [next, write, move]; missing rule = reject.
const START_A = {start: "q0", d: {"q0,a": ["qacc", "a", "R"]}};   // L = a(a+b)*
const EVEN = {start: "q0", d: {"q0,a": ["q1", "a", "R"], "q0,b": ["q1", "b", "R"],
  "q1,a": ["q0", "a", "R"], "q1,b": ["q0", "b", "R"], "q0,_": ["qacc", "_", "R"]}};
function run(M, w, cap = 500) {             // returns [verdict, moves]
  const t = [...w, "_"]; let q = M.start, h = 0;
  for (let k = 0; k < cap; k++) {
    if (q === "qacc" || q === "qrej") return [q, k];
    const r = M.d[q + "," + t[h]] || ["qrej", t[h], "R"];
    q = r[0]; t[h] = r[1]; h = r[2] === "R" ? h + 1 : Math.max(h - 1, 0);
    if (h === t.length) t.push("_");
  } return ["cap", cap];
}
// Two rewrites that never change the language L(M):
const pad = M => ({start: M.start, d: {...M.d,             // 2 unreachable states
  "p1,a": ["p2", "a", "L"], "p2,a": ["p1", "a", "L"]}});
const detour = M => { const d = {...M.d};                 // 2 extra moves at start
  for (const s of "ab_") { d["s0," + s] = ["s1", s, "R"]; d["s1," + s] = ["sB", s, "L"];
    d["sB," + s] = [...(M.d[M.start + "," + s] || ["qrej", s, "R"])]; }
  return {start: "s0", d}; };
const states = M => new Set(["qacc", "qrej", M.start,
  ...Object.keys(M.d).map(k => k.split(",")[0]), ...Object.values(M.d).map(r => r[0])]).size;
const props = {"has exactly 5 states": M => states(M) === 5,
  "table has an L move": M => Object.values(M.d).some(r => r[2] === "L"),
  "accepts ab": M => run(M, "ab")[0] === "qacc",
  "accepts the empty string": M => run(M, "")[0] === "qacc",
  "uses >= 3 moves on ab": M => run(M, "ab")[1] >= 3};
for (const [name, P] of Object.entries(props)) {
  const broken = [];
  for (const [mn, M] of [["START_A", START_A], ["EVEN", EVEN]])
    for (const [tn, tf] of [["pad", pad], ["detour", detour]])
      if (P(M) !== P(tf(M))) broken.push(`${mn}/${tn}`);
  console.log(name.padEnd(25), broken.length ? "NOT semantic: " + broken.join(" ")
    : "same answer on all 4 pairs");
}

আসল আউটপুট (ব্রাউজারের JavaScript):

has exactly 5 states      NOT semantic: START_A/pad
table has an L move       NOT semantic: START_A/pad START_A/detour EVEN/pad EVEN/detour
accepts ab                same answer on all 4 pairs
accepts the empty string  same answer on all 4 pairs
uses >= 3 moves on ab     NOT semantic: START_A/detour

প্রথম লাইন: START_A-এর state ৩টি, pad-এর পরে ৫টি, তাই “ঠিক ৫টি state” একই language-এ ভিন্ন উত্তর দেয়। দ্বিতীয় লাইন: “সারণিতে L move আছে” কোডের চেহারা, দুই রূপান্তরেই বদলায়। পঞ্চম লাইনটি সূক্ষ্ম: “ab-তে অন্তত ৩টি move” আচরণের ধর্ম, কোডের চেহারা নয়, তবু semantic নয়, কারণ detour START_A-এর ১টি move-কে ৩টি করে দেয় অথচ language একই থাকে। “ab গ্রহণ করে” আর “ε গ্রহণ করে” চারটি জোড়াতেই একই উত্তর দেয়, কারণ এগুলো সত্যিই language-এর ধর্ম। সতর্কতা: “চারটি জোড়ায় মিলেছে” প্রমাণ নয় যে ধর্মটি semantic; একটি অমিলই “semantic নয়” প্রমাণ করে, কিন্তু মিল শুধু সমর্থন। Semantic হওয়ার প্রমাণ আসে সংজ্ঞা থেকে: উত্তর যদি শুধু L(M) দিয়ে লেখা যায়।

৬ · Rice-এর সীমানা — syntactic প্রশ্ন, আচরণের প্রশ্ন আর Rice–Shapiro

Rice-এর theorem শক্তিশালী, কিন্তু এর দুটি শর্ত বাদ দিলে সিদ্ধান্তও চলে যায়। প্রমাণের কোন ধাপে কোন শর্ত লাগে, তা বুঝলে ভুল প্রয়োগ এড়ানো যায়। নিচের stepper দেখায়, “M-এর ঠিক ৫টি state” কেন Rice-এর জাল থেকে বেরিয়ে যায়।

1START_A: q0 a → qacc (৩ state)2pad: + p1, p2 (৫ state)3f(⟨M, w⟩) = ⟨M_w⟩4state(M_w) = M + T + জোড়া5decider: ⟨M⟩-এ state গোনা
এই ধাপে
L
state-সংখ্যা
শর্ত
  1. একটি যন্ত্র। START_A-এর একটিমাত্র নিয়ম δ(q0, a) = (qacc, a, R); state তিনটি: q0, qacc আর qrej. Language a(a ∪ b)∗.
  2. একই language, বেশি state. দুটি অপ্রাপ্য state p1, p2 জুড়লে state পাঁচটি, কিন্তু q0 থেকে সেখানে যাওয়ার পথ নেই, তাই language বদলায় না। “ঠিক ৫টি state”-এর উত্তর: প্রথমটির না, দ্বিতীয়টির হ্যাঁ। Semantic শর্ত ভাঙল।
  3. প্রমাণ নকল করার চেষ্টা। f ⟨M, w⟩ থেকে ⟨Mw⟩ লিখতে পারে, এই ধাপে কোনো সমস্যা নেই; f computable.
  4. কোথায় ভাঙে। Mw-এর state-সংখ্যা আসে M আর T-এর state-সংখ্যা আর জোড়া লাগানোর কয়েকটি state থেকে: কোড দেখেই ঠিক হয়, M w গ্রহণ করুক বা না করুক একই থাকে। তাই R-এর উত্তর তিন ক্ষেত্রে একই, আর “⇔” পাওয়া যায় না। প্রমাণের ধাপ ৬–৭ semantic শর্তের ওপরই দাঁড়িয়ে ছিল।
  5. আসল উত্তর। ⟨M⟩ পড়ে state-এর নাম গুনে ৫-এর সঙ্গে মেলান: সসীম কাজ, সবসময় থামে। ধর্মটি decidable, আর এতে Rice-এর কোনো বিরোধ নেই।

Semantic নয়, তবু undecidable. Rice না খাটা মানে decidable নয়; শুধু Rice দিয়ে প্রমাণ হয় না। তিনটি পরিচিত উদাহরণ:

  • TOTAL = {⟨M⟩ : M সব input-এ থামে}। HALTTM থেকে reduction: ⟨M, w⟩ থেকে M′ = “input x উপেক্ষা করে M-কে w-এ চালান; M থামলে গ্রহণ করুন”। M′ সব input-এ থামে ⇔ M w-এ থামে। তাই TOTAL undecidable.
  • “M w-এর ওপর চলার সময় কোনো non-blank ঘরে ␣ লেখে কি?” এটিও undecidable: M-কে বদলে নিন যাতে ␣-এর বদলে একটি নতুন চিহ্ন ␣′ লেখে আর ␣′ পড়লে ␣ পড়ার মতোই চলে, আর গ্রহণ করার মুহূর্তে head-এর ঘরে আগে একটি non-blank চিহ্ন লিখে তার ওপর ␣ লেখে। নতুন যন্ত্রটি এমন ঘরে ␣ লেখে ⇔ M w গ্রহণ করে।
  • সাবধান, উল্টো উদাহরণও আছে: “M w-এর ওপর কখনো head বাঁয়ে সরায় কি?” decidable. M যদি শুধু ডানে চলে, তবে |w| ধাপের পরে head সবসময় ␣-এর ওপর, আর পরের state শুধু আগের state-এর ওপর নির্ভর করে; তাই আরও |Q| + 1 ধাপের মধ্যে কোনো state ফিরে আসে আর আচরণ চক্রে পড়ে। প্রথম |w| + |Q| + 1 ধাপ চালিয়ে বাঁয়ে সরা না দেখলে আর কখনো দেখা যাবে না।

সাধারণ বিভ্রান্তি: (১) “Rice বলে program নিয়ে সব প্রশ্ন undecidable”: না, syntactic প্রশ্ন (state গোনা, কোডে কোনো শব্দ আছে কি না) আর ধাপ-সীমার প্রশ্ন প্রায়ই decidable. (২) “Rice বলে নির্দিষ্ট একটি program যাচাই করা অসম্ভব”: না, undecidable মানে সব program-এ কাজ করা একটি algorithm নেই; একটি নির্দিষ্ট program-এর সঠিকতা প্রায়ই হাতে বা tool দিয়ে প্রমাণ করা যায়। (৩) Rice শুধু Turing machine-এর মতো সম্পূর্ণ ক্ষমতার মডেলের কথা বলে। DFA-র জন্য L(D) = ∅ decidable (পর্ব ২০), CFG-এর জন্যও emptiness decidable (পর্ব ৩৭)।

কোন ধর্ম অন্তত recognizable? Rice শুধু “decidable নয়” বলে। কোন semantic ধর্ম recognizable হতে পারে, তার উত্তর দেয় একটি শক্তিশালী ফল, যা সাধারণত Rice–Shapiro theorem নামে পরিচিত (Rice আর Norman Shapiro-র ১৯৫০-এর দশকের কাজ থেকে; কৃতিত্বের বিবরণ বইভেদে ভিন্ন)। সহজ রূপে: P-এর index set recognizable হলে প্রতিটি recognizable L-এর জন্য, L-এর ধর্মটি আছে ⇔ L-এর কোনো সসীম উপসেটের ধর্মটি আছে। ফল: “L(M) = Σ∗” recognizable নয় (Σ∗-এর আছে, কিন্তু কোনো সসীম উপসেটের নেই), “L(M) অসীম”-ও নয়। অথচ “BG-0042 ∈ L(M)” সসীম সাক্ষী {BG-0042} দিয়ে ধরা যায়, আর তা recognizable. অনুশীলনে এর মানে: যে ধর্ম একটি সসীম সাক্ষী দিয়ে নিশ্চিত হয়, শুধু সেগুলোই “একদিন হ্যাঁ বলব” ধাঁচে খোঁজা যায়।

৭ · Software-এ Rice — virus, dead code, equivalence আর sound বনাম complete

বাস্তব programming ভাষা (Python, C, JavaScript) Turing-complete, তাই প্রতিটি Turing machine-কে একটি program হিসেবে লেখা যায়। তাই Rice-এর theorem সরাসরি software-এ নেমে আসে: program-এর input-output আচরণ নিয়ে যেকোনো non-trivial প্রশ্নের নিখুঁত, সবসময় থামা যাচাইকারী নেই। কয়েকটি পরিচিত উদাহরণ:

Virus detection

Fred Cohen ১৯৮০-এর দশকের মাঝামাঝি তাঁর virus-বিষয়ক কাজে দেখান, “এই program কি virus?” প্রশ্নের নিখুঁত detector অসম্ভব (প্রকাশের সাল ১৯৮৪–৮৭ বলে উল্লেখ পাওয়া যায়)। বাস্তব detection signature, heuristic আর আচরণ দেখে আনুমানিক কাজ করে; বিস্তারিত সাইবার নিরাপত্তা কোর্সের পর্ব ৩৩-এ।

Dead code

“লাইন k কি কোনো input-এ কখনো চলে?” Halting-এর ছদ্মবেশ: কোনো program-এর শেষে লাইন k বসালে সেটি চলে ⇔ program থামে। তাই compiler কিছু dead code ধরে, সব নয়।

Equivalence

দুটি program কি একই কাজ করে? Equivalence problem EQTM undecidable (পর্ব ৫২)। তাই optimizer এমন রূপান্তর ব্যবহার করে, যা নির্মাণেই সঠিক বলে প্রমাণিত, সাধারণ সমতা যাচাই করে না।

Static analysis

Null pointer, শূন্য দিয়ে ভাগ, অসীম loop খোঁজার tool কোড না চালিয়ে উত্তর দেয়। Rice বলে এরা সব program-এ নিখুঁত হতে পারে না; প্রশ্ন শুধু কোন দিকে ভুল করবে।

এখানে দুটি শব্দ দরকার। একটি analyzer “এই program-এ সমস্যা আছে” বললে, সমস্যা আসলে না থাকলে সেটি false positive (মিথ্যা সতর্কতা); সমস্যা থাকলেও না বললে false negative (মিস)। যে analyzer কখনো মিস করে না, তাকে sound বলা হয়; যে কখনো মিথ্যা সতর্কতা দেয় না, তাকে complete. Rice-এর ফল এই ভাষায়:

Turing-complete ভাষায় non-trivial semantic ধর্মের জন্য কোনো analyzer একসঙ্গে sound, complete আর সবসময় থামা হতে পারে না

তিনটির যেকোনো একটি ছাড়তে হয়। Type checker আর অনেক verification tool সাধারণত soundness রাখে আর কিছু সঠিক program-কেও প্রত্যাখ্যান করে; testing আর fuzzing শুধু সত্যিকারের ভুল দেখায় (মিথ্যা সতর্কতা নেই), কিন্তু অনেক ভুল মিস করে; আর কিছু tool সময়সীমা ছুঁলে “জানি না” বলে। নিচের ব্লক বাজারঘরের পাঁচটি discount-script নিয়ে দুই ধরনের যাচাইকারী তুলনা করে। প্রশ্নটি semantic: “কোনো অর্ডার-নম্বর n ≥ 1-এ কি দাম 0 হয়?”

# Bazarghar discount scripts: price (taka) for order number n = 1, 2, 3, ...
# Question (semantic): "can this script ever make an order free (price 0)?"
progs = [  # name, source text, the same rule as a function, true answer + why
    ("D1", "price = 500 - 5*n",                     lambda n: 500 - 5*n,
     True,  "n = 100"),
    ("D2", "price = 0 if n % 1000 == 999 else 500", lambda n: 0 if n % 1000 == 999 else 500,
     True,  "n = 999"),
    ("D3", "price = 0 if n*n == 2 else 500",        lambda n: 0 if n*n == 2 else 500,
     False, "no whole n has n*n = 2"),
    ("D4", "price = max(100, 500 - n)",             lambda n: max(100, 500 - n),
     False, "max(...) >= 100"),
    ("D5", "price = 500 + n % 7",                   lambda n: 500 + n % 7,
     False, "always >= 500"),
]
def static_check(src):        # over-approximate: anything that MIGHT give 0 is flagged
    return "0 if" in src or "-" in src
def bounded_check(rule, N=500):   # under-approximate: report only a real witness n <= N
    return any(rule(n) == 0 for n in range(1, N + 1))
score = {"static": [0, 0], "bounded": [0, 0]}   # [false alarms, misses]
print("name truth static bounded   why")
for name, src, rule, truth, why in progs:
    s, b = static_check(src), bounded_check(rule)
    for k, v in (("static", s), ("bounded", b)):
        if v and not truth: score[k][0] += 1
        if truth and not v: score[k][1] += 1
    print(f"{name:4} {truth!s:5} {s!s:6} {b!s:7}   {why}")
for k, (fa, miss) in score.items():
    print(f"{k:7}: false alarms {fa}, misses {miss}")

আসল আউটপুট (ব্রাউজারের Python):

name truth static bounded   why
D1   True  True   True      n = 100
D2   True  True   False     n = 999
D3   False True   False     no whole n has n*n = 2
D4   False True   False     max(...) >= 100
D5   False False  False     always >= 500
static : false alarms 2, misses 0
bounded: false alarms 0, misses 1

static_check কোড না চালিয়ে শুধু লেখা দেখে: “0 if” বা বিয়োগ থাকলেই সতর্ক করে। এই পাঁচটিতে সে কিছু মিস করেনি, কিন্তু D3 (n·n = 2 কোনো পূর্ণসংখ্যায় হয় না) আর D4 (max দাম ১০০-এর নিচে নামতে দেয় না) নিয়ে দুটি মিথ্যা সতর্কতা দিয়েছে। bounded_check n = 1 থেকে 500 পর্যন্ত চালিয়ে দেখে: যা পায় তা সত্যি (D1-এ n = 100), কোনো মিথ্যা সতর্কতা নেই, কিন্তু D2-এর একমাত্র সাক্ষী n = 999 সীমার বাইরে, তাই মিস। “সত্যি উত্তর” কলাম কোনো algorithm নয়, প্রতিটি লাইনের পাশে লেখা গাণিতিক যুক্তি। এই দুটি যাচাইকারী ইচ্ছা করে সরল; বাস্তবের tool অনেক চতুর। কিন্তু Rice বলে, যত চতুরই হোক, সব script-এ নিখুঁত এবং সবসময় থামা যাচাইকারী বানানো যায় না: script-এর ভাষা যথেষ্ট শক্তিশালী হলে (loop আর অসীম পূর্ণসংখ্যা থাকলে) কোথাও না কোথাও ভুল বা নীরবতা আসবেই।

এই আপসের প্রকৌশল-দিক সফটওয়্যার টেস্টিং কোর্সের পর্ব ০৬-এ static analysis tool-এর আলোচনায় আছে। গভীর তাত্ত্বিক হাতিয়ার, যেমন abstract interpretation, পর্ব ৭৮ “Program analysis-এর সীমা”-তে আসবে, আর পর্ব ৫৫-এ একটি সত্যিকারের analyzer-এর মিথ্যা সতর্কতা আর মিস চালিয়ে দেখা হবে।

৮ · ইতিহাস, আরও গভীরে আর পরীক্ষার প্রস্তুতি

ইতিহাস: Henry Gordon Rice ফলটি প্রকাশ করেন “Classes of Recursively Enumerable Sets and Their Decision Problems” প্রবন্ধে, Transactions of the American Mathematical Society-তে, ১৯৫৩ সালে; এটি তাঁর ১৯৫১ সালের কাছাকাছি সময়ের doctoral কাজের ওপর দাঁড়িয়ে বলে উল্লেখ পাওয়া যায়। মূল ভাষা Turing machine নয়, recursively enumerable set-এর শ্রেণি আর তাদের index: “কোন শ্রেণির r.e. set-এর index-গুলো recursive?” উত্তর: শুধু ফাঁকা শ্রেণি আর সব r.e. set-এর শ্রেণি। আজকের Turing machine-এর ভাষায় লেখা রূপ, যা এই পর্বে দেখেছেন, পরে Sipser, Hopcroft–Ullman-এর মতো পাঠ্যবইয়ে প্রচলিত হয়।

আরও গভীরে: Rice-এর theorem আসলে recursion theory-র একটি বড় ধারার শুরু: index set-গুলোকে কতটা “কঠিন” তা দিয়ে সাজানো যায় (arithmetical hierarchy; যেমন ETM co-recognizable কিন্তু TOTAL recognizable-ও নয়, co-recognizable-ও নয়)। Kleene-এর recursion theorem (পর্ব ৫৬) দিয়ে Rice-এর একটি ছোট বিকল্প প্রমাণও আছে: একটি যন্ত্র নিজের বর্ণনা পেয়ে R-এর উত্তরের উল্টো আচরণ করে। Complexity-তে Rice-এর কোনো সরল সমতুল্য নেই, কারণ সেখানে প্রশ্ন সীমিত সময়ের; আর program analysis-এ ১৯৭৭ সালে Patrick ও Radhia Cousot-এর abstract interpretation কাঠামো Rice-এর সীমার মধ্যে থেকে “sound আনুমানিক উত্তর” দেওয়ার একটি পদ্ধতিগত পথ দেয়।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

  • Rice-এর theorem বিবৃত করুন। Turing machine-এর language-এর প্রতিটি non-trivial ধর্ম undecidable; semantic আর non-trivial দুটি শর্তই উল্লেখ করতে হবে।
  • {⟨M⟩ : L(M) সসীম} কি decidable? না: semantic, ∅ সসীম আর Σ∗ নয়, তাই Rice. ∅-এর ধর্মটি আছে, তাই recognizable-ও নয়।
  • {⟨M⟩ : M-এর ১০টির কম state} কি Rice দিয়ে undecidable? না, ধর্মটি syntactic; state গুনলেই উত্তর, তাই decidable.
  • Rice-এর প্রমাণে reduction-এর দিক কী? ATM ≤m P (বা P̄)। P ≤m ATM লিখলে কিছুই প্রমাণ হয় না।
  • Static analyzer কেন মিথ্যা সতর্কতা দেয়? Rice অনুযায়ী sound, complete আর সবসময় থামা একসঙ্গে অসম্ভব; অধিকাংশ tool ধরা না পড়ার চেয়ে বাড়তি সতর্কতা বেছে নেয়।

৯ · AI-এর যুগে Rice-এর theorem নিয়ে কাজ

AI assistant Rice-এর theorem খুব আত্মবিশ্বাসের সঙ্গে প্রয়োগ করে, আর প্রায়ই ভুল জায়গায়। সাধারণ ভুলগুলো: syntactic প্রশ্নে Rice প্রয়োগ (“state-সংখ্যা undecidable”), শর্ত ছাড়া বিবৃতি (“program নিয়ে সব প্রশ্ন undecidable”), ভুল দিকে reduction (P ≤m ATM), “TOTAL undecidable, Rice দিয়ে” লেখা অথচ TOTAL semantic নয়, আর বানানো ইতিহাস। আরেকটি সূক্ষ্ম ভুল হলো “তাই কোনো static analyzer কাজের নয়” ধরনের অতিরঞ্জন: Rice বলে নিখুঁত নয়, অকেজো নয়।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
“M-এর state-সংখ্যা” বা “কোডে while আছে কি না”-তে Rice প্রয়োগএকই language-এর দুটি যন্ত্র বানান (অপ্রাপ্য state জুড়ে); উত্তর বদলালে ধর্মটি semantic নয়
Non-trivial শর্ত বাদ, যেমন “L(M) recognizable” undecidableএমন একটি যন্ত্র খুঁজুন যার ধর্ম আছে আর একটি যার নেই; না পেলে ধর্মটি trivial
Reduction-এর দিক উল্টো: P ≤m ATMদিকের নিয়ম লিখে মেলান: undecidable সমস্যাটি বাঁ দিকে থাকতে হবে
TOTAL বা “সব input-এ থামে”-কে Rice দিয়ে প্রমাণএকই language, একটি থামে, একটি loop করে: এমন জোড়া দেখালেই Rice বাদ; HALT থেকে আলাদা reduction দিন
বানানো সাল বা প্রবন্ধ, “Rice ১৯৫১ সালে Turing-এর সঙ্গে…”মূল প্রবন্ধের নাম আর সাল (Transactions of the AMS, ১৯৫৩) Sipser বা নির্ভরযোগ্য উৎসে নিজে মিলিয়ে নিন

AI-কে কাজে লাগানোর ভালো উপায়: প্রতিটি ধর্মের জন্য দুটি শর্তের আলাদা যাচাই, reduction-এর দিক আর একটি ছোট পরীক্ষা-কোড একসঙ্গে চাওয়া, যা আপনি নিজে চালাবেন।

আমি গণনার তত্ত্বে Rice-এর theorem শিখছি। Sipser রীতির Turing machine ধরে কাজ করো। ১. Rice-এর theorem পূর্ণ শর্তসহ লেখো: "semantic" আর "non-trivial" দুটির সুনির্দিষ্ট সংজ্ঞা দাও। ২. নিচের প্রতিটি ধর্মের জন্য আলাদা করে বলো: semantic কি না (না হলে একই language-এর দুটি যন্ত্রের উদাহরণ দাও), non-trivial কি না (দুটি সাক্ষী যন্ত্র দাও), তারপর decidable কি না আর কেন: (ক) L(M) সসীম, (খ) M-এর ৭টির কম state, (গ) M সব input-এ থামে, (ঘ) L(M) recognizable. ৩. A_TM থেকে reduction দিয়ে Rice-এর পূর্ণ প্রমাণ দাও; reduction-এর দিক স্পষ্ট লেখো আর loop-এর ক্ষেত্রটি আলাদা করে ব্যাখ্যা করো। ৪. Python standard library দিয়ে step cap-সহ একটি ছোট কোড দাও, যা generator-ভিত্তিক খেলনা যন্ত্রে M_w নির্মাণ চালিয়ে তিন ক্ষেত্র দেখায়। ৫. ইতিহাসের কোনো সাল বা প্রবন্ধ নিয়ে নিশ্চিত না হলে বলো; বানানো রেফারেন্স দিও না।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১Rice-এর theorem কেন শুধু L(M)-এর ধর্ম নিয়ে, M-এর সব আচরণ নিয়ে নয়? “semantic” শর্তটি তুলে দিলে কী ভুল হতো?

প্রমাণের হৃদয় হলো দুটি ধাপ: M w গ্রহণ করলে L(Mw) = L(T), নইলে L(Mw) = ∅. এই দুটি সমতা থেকে ⟨Mw⟩ P-তে আছে কি না, তা বলা যায় শুধু তখনই, যখন P-এর উত্তর যন্ত্রের language দিয়ে পুরোপুরি ঠিক হয়। Mw আর T-এর কোড সম্পূর্ণ আলাদা: Mw-এর ভেতরে M-এর পুরো কোড বসানো, তার state অনেক বেশি, ধাপও অনেক বেশি। তাই কোডের চেহারা বা ধাপের সংখ্যার কোনো ধর্ম এই সমতা থেকে কিছুই জানতে পারে না।

শর্তটি তুলে দিলে theorem মিথ্যা হয়ে যেত, আর তার প্রতি-উদাহরণ খুব সহজ: “M-এর ঠিক ৫টি state” non-trivial কিন্তু decidable. আবার “M ε-কে ১০০ ধাপের মধ্যে গ্রহণ করে” ধর্মটি আচরণের, কোডের চেহারার নয়, তবু decidable, কারণ ১০০ ধাপ চালানো একটি সসীম কাজ। অর্থাৎ “semantic” শব্দটি এখানে দৈনন্দিন অর্থে “আচরণ নিয়ে” নয়; এর সুনির্দিষ্ট অর্থ “শুধু গৃহীত string-এর set দিয়ে নির্ধারিত”। এই পার্থক্য অনেক পাঠ্যবইয়ের সংক্ষিপ্ত বর্ণনায় হারিয়ে যায়, আর তখন পাঠক ভাবেন “program-এর আচরণ নিয়ে সব প্রশ্ন undecidable”.

অন্যদিকে কিছু আচরণের প্রশ্ন semantic না হয়েও undecidable, যেমন TOTAL. তার কারণ ভিন্ন: TOTAL-এর ভেতরে halting প্রশ্ন সরাসরি লুকানো, আর আলাদা reduction দিয়ে তা দেখানো যায়। গবেষণায় Rice-এর অনেক সাধারণীকরণ আছে, যা কিছু আচরণের ধর্মও ঢাকে (যেমন partial function-এর ধর্ম নিয়ে Rice-এর রূপ, যেখানে যন্ত্রের output function-টিই “অর্থ”)। কিন্তু প্রতিটি সাধারণীকরণেই একটি মূল শর্ত থাকে: একই “অর্থের” দুটি program-এর উত্তর এক হতে হবে।

প্রোগ্রামারের জন্য এর মানে: আপনার প্রশ্ন যদি “এই কোড কেমন লেখা” ধরনের হয় (style, নাম, নির্দিষ্ট API-র ব্যবহার), linter নিখুঁতভাবে উত্তর দিতে পারে। প্রশ্ন যদি “এই কোড শেষ পর্যন্ত কী ফল দেয়” ধরনের হয়, তবে সাধারণ ক্ষেত্রে আনুমানিক উত্তরই পাবেন।

মূল উপলব্ধি: Semantic শর্তটিই প্রমাণের চাবিকাঠি; এটি নিশ্চিত করে যে Mw-এর language বদলালেই উত্তর বদলায়, আর কোডের খুঁটিনাটি যেন কোনো ফাঁক না রাখে।

প্র ০২নিখুঁত virus detector অসম্ভব হলে antivirus software কীভাবে কাজ করে? তত্ত্বের এই সীমা বাস্তবে কী ধরনের আপস তৈরি করে?

Fred Cohen ১৯৮০-এর দশকের মাঝামাঝি “computer virus” ধারণাটিকে গাণিতিক রূপ দেন আর দেখান যে কোনো program virus কি না, তা সব ক্ষেত্রে নিখুঁতভাবে বলে দেওয়া algorithm অসম্ভব। তাঁর যুক্তি diagonalization-এর ধাঁচের: ধরুন D একটি নিখুঁত detector. তাহলে এমন একটি program লেখা যায়, যা D-কে নিজের ওপর চালায় আর D যদি বলে “virus”, তবে নিরীহ আচরণ করে, আর D “নিরীহ” বললে ছড়িয়ে পড়ে। Rice-এর দৃষ্টিতে কথাটি আরও সাধারণ: “এই program কি অন্য ফাইল বদলায়” ধরনের আচরণের ধর্ম non-trivial, তাই নিখুঁত যাচাইকারী নেই। (সতর্কতা: “virus” ঠিক কোন formal ধর্ম, তা সংজ্ঞার ওপর নির্ভর করে, আর সব সংজ্ঞা Rice-এর language-এর ধর্মের সঙ্গে হুবহু মেলে না।)

বাস্তবের detection তাই কয়েকটি আনুমানিক কৌশল মেশায়। Signature matching চেনা ক্ষতিকর কোডের নির্দিষ্ট byte-নকশা খোঁজে: এটি syntactic, তাই decidable আর দ্রুত, কিন্তু নতুন বা রূপ-বদলানো (polymorphic) malware মিস করে। Heuristic বিশ্লেষণ সন্দেহজনক গঠন দেখে সতর্ক করে, যাতে মিথ্যা সতর্কতা আসে। আচরণ-পর্যবেক্ষণ (sandbox-এ কিছুক্ষণ চালানো) এই পর্বের bounded_check-এর মতো: যা দেখে তা সত্যি, কিন্তু সময়সীমার পরে সক্রিয় হওয়া কোড ধরতে পারে না। এর সঙ্গে আসে reputation, signed software আর নিয়মিত update.

এই আপস ব্যবহারকারী প্রতিদিন অনুভব করেন: কখনো নিরীহ একটি tool “সন্দেহজনক” বলে আটকে যায় (false positive), কখনো নতুন একটি আক্রমণ ধরা পড়ে না (false negative). প্রতিরক্ষা তাই কখনো এক স্তরে থাকে না: least privilege, backup, আর সন্দেহজনক ফাইল না খোলার অভ্যাস একসঙ্গে কাজ করে। সাইবার নিরাপত্তা কোর্সের পর্ব ৩৩-এ এই কৌশলগুলোর বিস্তারিত আছে।

মূল উপলব্ধি: Rice আর Cohen-এর ফল বলে নিখুঁত detection অসম্ভব; তাই বাস্তব প্রতিরক্ষা কয়েকটি অপূর্ণ কিন্তু পরিপূরক স্তর মেশায়, আর কোন ভুল (মিস না মিথ্যা সতর্কতা) সহ্য করা হবে, সেটি সচেতন সিদ্ধান্ত।

প্র ০৩দুটি program একই কাজ করে কি না, তা undecidable. তাহলে compiler কীভাবে নিশ্চিত হয় যে optimize করা কোড মূল কোডের মতোই আচরণ করে?

Equivalence-এর প্রশ্নটি Rice-এর একটু বাইরের: এখানে একটি নয়, দুটি যন্ত্রের সম্পর্ক। তবু EQTM undecidable, আর আসলে recognizable বা co-recognizable কোনোটিই নয় (পর্ব ৫২)। সহজ যুক্তি: একটি program-কে “সব বর্জন করে” এমন program-এর সঙ্গে তুলনা করতে পারলে ETM-ও decide করা যেত। তাই কোনো compiler “মূল কোড আর optimize করা কোড সমান কি না” যাচাই করে না।

Compiler বরং উল্টো পথে চলে: সে শুধু এমন রূপান্তর ব্যবহার করে, যা নির্মাণের দিক থেকেই সঠিক বলে যুক্তি দেওয়া যায়। যেমন “x * 2-কে x + x লেখা”, “কখনো না পড়া variable-এ লেখা বাদ দেওয়া”, “loop-এর ভেতরের অপরিবর্তিত হিসাব বাইরে আনা”। প্রতিটি রূপান্তরের জন্য একটি সংকীর্ণ, decidable শর্ত থাকে (variable-টি সত্যিই আর পড়া হয় না, কোনো side effect নেই)। শর্তটি নিশ্চিত না হলে compiler রূপান্তরটি করে না। অর্থাৎ optimizer sound থাকে আর অনেক সম্ভাব্য optimization ছেড়ে দেয়: Rice-এর আপসের আরেকটি রূপ।

উচ্চ-নির্ভরতার ক্ষেত্রে আরও দুটি পথ আছে। একটি হলো verified compiler: Xavier Leroy-র নেতৃত্বে তৈরি CompCert নামের C compiler-এর প্রতিটি রূপান্তর একটি proof assistant-এ গাণিতিকভাবে প্রমাণিত (২০০০-এর দশকের মাঝামাঝি থেকে প্রকাশিত কাজ)। এখানে প্রমাণ প্রতিটি নির্দিষ্ট রূপান্তরের, সাধারণ equivalence-এর নয়, তাই Rice-এর সঙ্গে বিরোধ নেই। আরেকটি হলো translation validation: প্রতিবার compile করার পরে একটি আলাদা tool নির্দিষ্ট এই জোড়ার সমতা প্রমাণের চেষ্টা করে; পারলে ভালো, না পারলে “জানি না” বলে সতর্ক করে।

বাজারঘরের দলের জন্য শিক্ষা হলো: refactoring-এর পরে “পুরোনো আর নতুন কোড সমান কি না” কোনো tool নিখুঁতভাবে বলতে পারবে না। তাই ছোট, যুক্তিসঙ্গত ধাপে refactoring, প্রতিটি ধাপের পরে test, আর property-based testing (সফটওয়্যার টেস্টিং কোর্সের পর্ব ৫৮) দিয়ে পুরোনো ও নতুন কোড অনেক এলোমেলো input-এ মেলানো বাস্তবসম্মত পথ।

মূল উপলব্ধি: Equivalence undecidable বলে compiler সাধারণ সমতা যাচাই করে না; সে নির্মাণেই সঠিক রূপান্তর ব্যবহার করে, আর প্রয়োজনে নির্দিষ্ট রূপান্তরের প্রমাণ বা প্রতি-ক্ষেত্রে যাচাইয়ের ওপর নির্ভর করে।

প্র ০৪Type checker প্রতিটি program-এ থামে আর একটি semantic প্রশ্নের (“চলার সময় type-এর ভুল হবে কি?”) উত্তর দেয় বলে মনে হয়। এটি কি Rice-এর বিরোধী?

না, আর কেন নয়, তা বোঝা খুব শিক্ষণীয়। আসল semantic প্রশ্ন হলো “এই program চলার সময় কখনো type-এর ভুলে আটকাবে কি?” এটি non-trivial আচরণের প্রশ্ন, আর Turing-complete ভাষায় সাধারণভাবে undecidable. Type checker এই প্রশ্নের উত্তর দেয় না; সে একটি ভিন্ন, syntactic প্রশ্নের উত্তর দেয়: “এই program কি type-এর নিয়মগুলো মানে?” নিয়মগুলো কোডের গঠনের ওপর লেখা, তাই সাধারণ type system-এ যাচাই decidable আর দ্রুত।

দুটি প্রশ্নের সম্পর্ক এক দিকের। Robin Milner ১৯৭৮ সালে ML ভাষার জন্য যে ফলটি দেন, তার স্লোগান “well-typed programs cannot go wrong”: নিয়ম মানা program চলার সময় নির্দিষ্ট ধরনের type-এর ভুল করে না। অর্থাৎ type checker sound: সে type-এর ভুল মিস করে না। কিন্তু complete নয়: এমন program আছে যা কখনো type-এর ভুল করবে না, অথচ checker তাকে প্রত্যাখ্যান করে। উদাহরণ: “if (n*n == 2) return "free"; else return 500;” ধরনের কোড, যার একটি শাখা কখনো চলে না কিন্তু ভিন্ন type ফেরত দেয়; checker সেই শাখাও বিচার করে। এই পর্বের D3 script-এর মিথ্যা সতর্কতা ঠিক এই ধাঁচের।

আরেকটি সূক্ষ্মতা: কিছু ভাষার type system এত শক্তিশালী যে type যাচাই নিজেই undecidable হয়ে যায়। C++ template বা কিছু উন্নত type system-এর বৈশিষ্ট্য নিয়ে এমন ফলের কথা সাহিত্যে পাওয়া যায়; বাস্তব compiler তখন একটি গভীরতা-সীমা বসিয়ে “আর এগোব না” বলে, ঠিক আমাদের step cap-এর মতো। ভাষা-নকশাকারীরা তাই সচেতনভাবে বেছে নেন: বেশি প্রকাশক্ষমতা, নাকি সবসময় থামা যাচাই।

এখান থেকে একটি সাধারণ কৌশল শেখা যায়: undecidable semantic প্রশ্নের বদলে একটি decidable syntactic “প্রতিনিধি” প্রশ্ন বেছে নিন, যার “হ্যাঁ” আসল প্রশ্নের নিরাপদ উত্তর নিশ্চিত করে। Linter, type checker, ownership checker সবাই এই ধাঁচে কাজ করে, আর পর্ব ৭৮-এ abstract interpretation এই কৌশলকে পদ্ধতিগত রূপ দেবে।

মূল উপলব্ধি: Type checker Rice ভাঙে না; সে একটি decidable syntactic প্রশ্নের উত্তর দেয়, যা আসল semantic প্রশ্নের sound কিন্তু অসম্পূর্ণ প্রতিনিধি।

প্র ০৫Rice-এর theorem নেতিবাচক ফল। এর ইতিবাচক দিক কী: কোন ধরনের semantic প্রশ্নের উত্তর অন্তত “একদিন হ্যাঁ” বলা যায়, আর testing এখানে কোথায় বসে?

Rice শুধু decidability নিয়ে কথা বলে, কিন্তু undecidable প্রশ্নের মধ্যেও পার্থক্য আছে। “BG-0042 ∈ L(M)” undecidable, তবু recognizable: M-কে BG-0042-এ চালান, গ্রহণ করলে “হ্যাঁ”। একটি সসীম সাক্ষী, আর তা যাচাই করার একটি সসীম গণনা, যথেষ্ট। অন্যদিকে “L(M) = ∅” বা “L(M) = Σ∗” এমন কোনো সসীম সাক্ষী দিয়ে নিশ্চিত হয় না: যত string-ই পরীক্ষা করুন, পরের string-এ উত্তর বদলাতে পারে।

অংশ ৬-এর Rice–Shapiro theorem এই অনুভূতিকে সুনির্দিষ্ট করে: একটি semantic ধর্ম recognizable হতে হলে, L-এর ধর্মটি থাকা আর L-এর কোনো সসীম অংশের ধর্মটি থাকা সমান হতে হবে। মোটামুটি বলা যায়, recognizable ধর্ম মানে “একটি সসীম প্রমাণ দেখানো যায় এমন ধর্ম”। Rice-এর মূল প্রবন্ধ আর পরের কাজে এমন ধর্মের পুরো চরিত্র দেওয়া আছে বলে উল্লেখ পাওয়া যায়।

Testing ঠিক এখানে বসে। একটি test case হলো একটি সসীম সাক্ষী: “input x-এ program ভুল ফল দেয়”। ভুল থাকলে আর সেটি একটি সসীম input-এ দেখা গেলে, যথেষ্ট test (বা fuzzing, সফটওয়্যার টেস্টিং কোর্সের পর্ব ৬০) একদিন তা খুঁজে পাবে। কিন্তু “কোনো ভুল নেই” প্রমাণ করতে testing-এর কোনো সসীম সাক্ষী নেই। Edsger Dijkstra-র বহুল উদ্ধৃত কথা, মোটামুটি ১৯৬৯–৭০ সালের: “program testing ভুলের উপস্থিতি দেখাতে পারে, অনুপস্থিতি কখনো নয়।” Rice–Shapiro এই কথার একটি গাণিতিক ছায়া।

অনুপস্থিতি প্রমাণের জন্য তাই অন্য পথ লাগে: একটি নির্দিষ্ট program-এর জন্য মানুষের লেখা বা tool-সহায়িত প্রমাণ (invariant, proof assistant), যা Rice নিষেধ করে না, কারণ Rice “সব program-এ কাজ করা একটি algorithm” নিষেধ করে, “এই program-এর প্রমাণ” নয়।

মূল উপলব্ধি: যে ধর্ম একটি সসীম সাক্ষী দিয়ে দেখানো যায়, তা অন্তত খুঁজে পাওয়া যায় (recognizable); testing এই ধরনের খোঁজ, তাই ভুল খুঁজে পায় কিন্তু ভুলের অনুপস্থিতি প্রমাণ করে না।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। rice_reduction.py আর semantic_test.js ব্লকে নিজের যন্ত্র বা ধর্ম লিখে উত্তর যাচাইও করতে পারেন।

  1. প্রমাণ: FINITETM = {⟨M⟩ : L(M) সসীম}. Rice-এর দুটি শর্ত আলাদা করে যাচাই করে দেখান যে FINITETM undecidable, তারপর বলুন এটি recognizable কি না।

    Semantic: L(M1) = L(M2) হলে একটির language সসীম ⇔ অন্যটির সসীম, কারণ একই set. Non-trivial: T∅ (সব বর্জন করে) এর language ∅, যা সসীম, তাই ⟨T∅⟩ ∈ FINITETM; “সব গ্রহণ করে” এমন যন্ত্রের language Σ∗, অসীম, তাই সেটি নেই। দুটি শর্তই মেলে, তাই Rice অনুযায়ী undecidable. ∎

    Recognizable? না। ⟨T∅⟩ ∈ FINITETM, তাই অনুসিদ্ধান্ত ৩.২ অনুযায়ী A̅TM ≤m FINITETM, আর A̅TM recognizable নয়। (Complement “L(M) অসীম”-ও recognizable নয়, Rice–Shapiro অনুযায়ী; তাই FINITETM co-recognizable-ও নয়।)

  2. প্রমাণ (ভুল খুঁজুন): একজন লিখেছেন: “P = {⟨M⟩ : BG-0042 ∈ L(M)} undecidable. প্রমাণ: f(⟨M⟩) = ⟨M, BG-0042⟩ নিন। তাহলে ⟨M⟩ ∈ P ⇔ f(⟨M⟩) ∈ ATM, অর্থাৎ P ≤m ATM. ATM undecidable, তাই P undecidable.” কোথায় ভুল? সঠিক যুক্তি দিন, আর এই reduction আসলে কী প্রমাণ করে, বলুন।

    ভুল: Reduction-এর দিক উল্টো। P ≤m ATM মানে “P, ATM-এর চেয়ে কঠিন নয়”। ATM undecidable হওয়া থেকে P সম্পর্কে কিছুই আসে না: যেকোনো decidable language-ও ATM-এ reduce করা যায়। নিয়ম: “A ≤m B আর A undecidable ⇒ B undecidable”; undecidable সমস্যাটি বাঁ দিকে থাকতে হবে।

    যা প্রমাণ হয়: f computable আর ⇔ ঠিক, তাই P ≤m ATM সত্য; ATM recognizable বলে P-ও recognizable (একটি সঠিক, কিন্তু ভিন্ন সিদ্ধান্ত)।

    সঠিক যুক্তি: P semantic (শুধু L(M)-এর ওপর নির্ভর) আর non-trivial (শুধু BG-0042 গ্রহণ করা T-এর আছে, T∅-এর নেই), তাই Rice. অথবা সরাসরি ATM ≤m P, অংশ ৩-এর Mw দিয়ে।

  3. নির্মাণ: P2 = {⟨M⟩ : L(M) = {BG-0042, BG-0043}}. Rice-এর প্রমাণের ধাঁচে T বেছে নিন, ⟨T∅⟩ ∉ P2 কি না দেখান, Mw-এর high-level বর্ণনা দিন, আর দেখান যে ⟨M, w⟩ ∈ ATM ⇔ ⟨Mw⟩ ∈ P2.

    T = “input x-এর ওপর: x = BG-0042 বা x = BG-0043 হলে গ্রহণ, নইলে বর্জন।” L(T) = {BG-0042, BG-0043}, তাই ⟨T⟩ ∈ P2. L(T∅) = ∅ ≠ সেই set, তাই ⟨T∅⟩ ∉ P2: complement নেওয়ার দরকার নেই।

    Mw = “input x-এর ওপর: M-কে w-এ চালান; বর্জন করলে বর্জন; গ্রহণ করলে T-কে x-এ চালান আর T-এর রায় দিন।” M w গ্রহণ করলে L(Mw) = {BG-0042, BG-0043} ∈ P2; বর্জন বা loop করলে L(Mw) = ∅, তাই P2-এ নেই। f M-কে চালায় না, তাই computable. অতএব ATM ≤m P2.

    পরীক্ষা: rice_reduction.py-তে T-এর শেষ লাইন return x in ("BG-0042", "BG-0043") করে, X-এ BG-0044 যোগ করে scratch-এ চালানো হয়েছে: (ACC, ab)-এর Mw ঠিক BG-0042 আর BG-0043 গ্রহণ করে, (ACC, ba) আর (LOOP, ab)-এর Mw কিছুই গ্রহণ করে না।

  4. ফল অনুমান: semantic_test.js ব্লকের props-এ একটি ষষ্ঠ ধর্ম যোগ করা হলো: "even number of rules": M => Object.keys(M.d).length % 2 === 0. START_A-এর নিয়ম ১টি, EVEN-এর ৫টি; pad দুটি নিয়ম যোগ করে, আর detour নয়টি নতুন নিয়ম (s0, s1, sB, প্রতিটি a, b, ␣-এর জন্য) যোগ করে। নতুন লাইনটি কী ছাপবে? চালানোর আগে অনুমান করুন।

    pad নিয়মের সংখ্যা ২ বাড়ায়, তাই জোড়-বিজোড় বদলায় না: START_A 1 → 3 (দুটিই বিজোড়), EVEN 5 → 7 (দুটিই বিজোড়)। তাই pad এই ধর্ম “ভাঙে” না। detour ৯ বাড়ায়: START_A 1 → 10 (বিজোড় → জোড়), EVEN 5 → 14 (বিজোড় → জোড়)। তাই আউটপুট:

    even number of rules      NOT semantic: START_A/detour EVEN/detour

    Scratch-এ চালিয়ে হুবহু এই লাইন আর নিয়মের সংখ্যা 1, 10, 7, 14 পাওয়া গেছে। শিক্ষা: pad একা দেখলে মনে হতো ধর্মটি “টিকে গেছে”, কিন্তু আরেকটি রূপান্তর এক মুহূর্তে ভেঙে দেয়। মিল কখনো semantic-এর প্রমাণ নয়।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমRice-এর theorem-এর প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. বিরোধের জন্য ধরে নেওয়া: P-এর একটি decider R আছে
  2. দরকার হলে P-এর বদলে P̄ নিয়ে নিশ্চিত করা যে ⟨T∅⟩ P-তে নেই
  3. P-এর একটি সদস্য যন্ত্র T বেছে নেওয়া
  4. ⟨M, w⟩ থেকে ⟨Mw⟩ লেখার computable f সংজ্ঞায়িত করা
  5. দেখানো: M w গ্রহণ করে ⇔ ⟨Mw⟩ ∈ P
  6. R আর f মিলে ATM decide হয়, যা অসম্ভব: বিরোধ

Turing machine-এর নিচের কোন ধর্মটি Rice-এর theorem দিয়ে সরাসরি undecidable প্রমাণ করা যায়?

  • M-এর অন্তত ১০টি state আছে
  • L(M)-এ BG-0042 string-টি আছে
  • M ε-কে ৫০ ধাপের মধ্যে গ্রহণ করে
  • L(M) Turing-recognizable

একটি undecidable ধর্ম P-এর জন্য mapping reduction দিয়ে প্রমাণ লিখতে হবে, যেখানে ATM জানা undecidable language. কোন reduction দেখাতে হবে?

  • P ≤m ATM
  • P̄ ≤m ATM
  • HALTTM ≤m ATM
  • ATM ≤m P

TOTAL = {⟨M⟩ : M প্রতিটি input-এ থামে}. Rice-এর theorem আর TOTAL-এর সম্পর্ক নিয়ে কোনটি সঠিক?

  • TOTAL semantic নয়, তাই Rice সরাসরি খাটে না; তবু এটি অন্য reduction দিয়ে undecidable
  • Rice খাটে না, তাই TOTAL decidable
  • TOTAL semantic আর non-trivial, তাই Rice সরাসরি খাটে
  • TOTAL trivial, কারণ প্রতিটি যন্ত্র কোনো না কোনো input-এ থামে

P একটি non-trivial semantic ধর্ম, আর যে যন্ত্র সব input বর্জন করে (language ∅) তার বর্ণনা P-তে আছে। P সম্পর্কে সবচেয়ে শক্ত সঠিক সিদ্ধান্ত কোনটি?

  • P decidable, কারণ ∅-এর ধর্ম আছে
  • P undecidable, তবে recognizable
  • P undecidable, আর Turing-recognizable-ও নয়
  • Rice এই ক্ষেত্রে খাটে না

একটি static analyzer “শূন্য দিয়ে ভাগ”-এর জন্য sound বলে দাবি করা হয়। এর অর্থ কী?

  • এটি কখনো মিথ্যা সতর্কতা দেয় না
  • শূন্য দিয়ে ভাগের প্রতিটি সম্ভাব্য ঘটনা এটি ধরে, তবে মিথ্যা সতর্কতাও দিতে পারে
  • এটি প্রতিটি program-এ নিখুঁত উত্তর দেয় আর সবসময় থামে
  • এটি program সব input-এ চালিয়ে দেখে

Rice-এর প্রমাণে f ইনপুট ⟨M, w⟩ থেকে ⟨Mw⟩ লেখে, যেখানে Mw প্রথমে M-কে w-এ চালায় আর গ্রহণ হলে T-এর মতো চলে। M যদি w-এ চিরকাল চলে (loop), তবে কী হয়?

  • f নিজে loop করে, তাই f computable নয়
  • L(Mw) = L(T)
  • L(Mw) = ∅, আর f তবু থামে
  • প্রমাণটি এই ক্ষেত্রে ভেঙে যায়

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. Rice-এর theorem: Turing machine-এর language-এর প্রতিটি non-trivial ধর্ম undecidable. দুটি শর্ত: semantic (একই L ⇒ একই উত্তর) আর non-trivial (কিছুর আছে, কিছুর নেই)।
  2. প্রমাণ: ATM ≤m P. Mw প্রথমে M-কে w-এ চালায়, গ্রহণ হলে T-এর মতো চলে; তাই L(Mw) = L(T) বা ∅. f শুধু কোড লেখে।
  3. ∅-এর ধর্মটি থাকলে P recognizable-ও নয় (যেমন ETM, FINITETM); সসীম সাক্ষী দিয়ে দেখানো যায় এমন ধর্ম recognizable হতে পারে (Rice–Shapiro).
  4. Rice খাটে না: syntactic ধর্ম (state গোনা), ধাপ-সীমার প্রশ্ন, trivial ধর্ম, আর DFA বা CFG-এর মতো দুর্বল মডেল। Rice না খাটলেও কিছু প্রশ্ন (TOTAL) অন্য reduction-এ undecidable.
  5. Software-এ: নিখুঁত virus, dead-code বা equivalence যাচাইকারী নেই; analyzer sound, complete আর সবসময় থামা, তিনটির একটি ছাড়ে।

পরের পর্বে: Post correspondence problem: ডোমিনো সাজিয়ে ওপর-নিচ মেলানোর নিরীহ একটি ধাঁধা, যা undecidable; আর সেখান থেকে CFG-এর ambiguity আর equivalence-এর মতো grammar-এর প্রশ্ন কেন undecidable.

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান