এই পর্বে যা শিখবেন
- Computable function আর mapping reduction-এর সুনির্দিষ্ট সংজ্ঞা, আর decidability ও recognizability কোন দিকে “বয়ে যায়” তার প্রমাণ
- ATM ≤m HALTTM, ETM, REGULARTM আর EQTM-এর পূর্ণ reduction প্রমাণ, দুই দিকের “⇔” সহ
- Python-এ reduction function f লিখে দেখা যে f শুধু যন্ত্রের নিয়মের সারণি নতুন করে লেখে, আর ছোট ক্ষেত্রে “⇔” brute force-এ মেলে
- Mapping বনাম Turing reduction, computation history-র পরিচয়, আর কেন ATM ≤m ETM অসম্ভব
- Reduction প্রমাণ লেখার একটি নির্ভরযোগ্য ছাঁচ আর সবচেয়ে সাধারণ তিনটি ভুল ধরার উপায়
১ · Reduction-এর ধারণা — এক সমস্যার উত্তর দিয়ে আরেকটির উত্তর
পর্ব ৫১ “Diagonalization আর halting problem”-এ একটি কঠিন কাজ হয়েছে: diagonalization দিয়ে প্রমাণ যে ATM = {⟨M, w⟩ : M w গ্রহণ করে} undecidable, অর্থাৎ সব input-এ থেমে সঠিক উত্তর দেয় এমন কোনো Turing machine নেই। এখন প্রতিটি নতুন সমস্যার জন্য কি আবার নতুন করে diagonal টেবিল বানাতে হবে? না। অনেক সহজ একটি পথ আছে: নতুন সমস্যাকে পুরনো জানা-কঠিন সমস্যার সঙ্গে জুড়ে দেওয়া। এই জুড়ে দেওয়ার নাম reduction.
ধরুন আপনি রাজশাহীতে নতুন এসেছেন, বাংলা পড়তে পারেন কিন্তু একটি জাপানি রেসিপি-বই পেয়েছেন। আপনার বন্ধুর কাছে একটি নির্ভরযোগ্য অনুবাদ-যন্ত্র আছে, যা যেকোনো জাপানি বাক্যকে হুবহু বাংলায় বদলে দেয়। তাহলে “জাপানি রেসিপি বোঝা” সমস্যাটি “বাংলা রেসিপি বোঝা”-তে নেমে এল। এখান থেকে দুটি সিদ্ধান্ত টানা যায়, আর দুটিই একই দিকে: বাংলা বোঝা সহজ হলে জাপানি রেসিপি বোঝাও সহজ। আবার, কেউ যদি প্রমাণ করে যে জাপানি রেসিপি বোঝা অসম্ভব, তাহলে বাংলা বোঝাও অসম্ভব হতে হবে, নইলে অনুবাদ করে বুঝে ফেলা যেত। অনুবাদ-যন্ত্রটি হলো f, জাপানি হলো A, বাংলা হলো B.
এই পর্বের পুরো কৌশল ঐ উপমার দ্বিতীয় বাক্যে। কোনো সমস্যা B অসম্ভব, তা দেখাতে আমরা একটি জানা-অসম্ভব সমস্যা A নিই আর দেখাই: A-এর প্রতিটি প্রশ্নকে যান্ত্রিকভাবে B-এর প্রশ্নে অনুবাদ করা যায়। তাহলে B-এর একটি decider থাকলে A-এরও decider হতো, যা অসম্ভব। পর্ব ০৪-এ এর এক পাতার পূর্বরূপ দেখেছেন; এখানে সংজ্ঞা, প্রমাণ আর চারটি পূর্ণ উদাহরণ।
বাস্তবের একটি প্রশ্ন দিয়ে শুরু করি। বাজারঘরের discount দল ছোট ছোট script লেখে, যা অর্ডার দেখে ছাড় হিসাব করে। দলনেতা চান একটি স্বয়ংক্রিয় যাচাইকারী: “এই script কি কখনো কোনো অর্ডারে ১০০০ টাকার বেশি ছাড় দেবে?” প্রশ্নটি শুনতে নিরীহ। কিন্তু এই পর্ব শেষে আপনি নিজেই দেখাতে পারবেন, সব script-এ সবসময় সঠিক উত্তর দেয় এমন যাচাইকারী থাকতে পারে না: যেকোনো program P আর input w থেকে এমন একটি script বানানো যায়, যা “P-কে w-এর ওপর চালান, থামলে ২০০০ টাকা ছাড় দিন”। Script-টি বড় ছাড় দেয় ঠিক তখন, যখন P w-এ থামে। তাই যাচাইকারী থাকলে halting problem সমাধান হয়ে যেত। এটিই একটি reduction, আর এর গঠন এই পর্বের প্রতিটি প্রমাণে ফিরে আসবে।
ইতিহাস: Turing ১৯৩৬ সালেই নিজের যন্ত্র-সম্পর্কিত undecidable প্রশ্ন থেকে Hilbert-এর Entscheidungsproblem-এর নেতিবাচক উত্তর টানেন, যা কার্যত একটি reduction. ১৯৩৯ সালের গবেষণাপত্রে Turing “oracle machine”-এর ধারণা দেন, যেখান থেকে আজকের Turing reduction. আর Emil Post ১৯৪৪ সালের “Recursively enumerable sets of positive integers and their decision problems” প্রবন্ধে বিভিন্ন ধরনের reducibility পদ্ধতিগতভাবে আলোচনা করেন; তার একটি “many-one reducibility”, যাকে Sipser-এর বইয়ে mapping reducibility বলা হয়। দুই নামই চালু, অর্থ একই।
২ · Computable function আর mapping reduction — সংজ্ঞা আর দিকের নিয়ম
Reduction-এর অনুবাদ-যন্ত্রকে নিজেও একটি algorithm হতে হবে, নইলে পুরো যুক্তি ভেঙে পড়ে। তাই প্রথমে সংজ্ঞা।
একটি function f: Σ∗ → Σ∗ computable, যদি এমন একটি Turing machine থাকে যা প্রতিটি input w-এ থামে আর থামার সময় tape-এ শুধু f(w) রেখে যায়। অর্থাৎ f একটি total function: প্রতিটি w-এ সংজ্ঞায়িত, আর সবসময় সসীম সময়ে হিসাব হয়।
Language A mapping reducible B-তে, লেখা হয় A ≤m B, যদি এমন একটি computable function f থাকে যে প্রতিটি w ∈ Σ∗-এর জন্য
w ∈ A ⇔ f(w) ∈ B
এই f-কে বলা হয় A থেকে B-তে mapping reduction. ছোট “m” এসেছে mapping (বা many-one) থেকে।
সংজ্ঞার তিনটি অংশ আলাদা করে দেখুন, কারণ প্রতিটি অংশ বাদ দেওয়াই একটি পরিচিত ভুল। প্রথমত, f computable: f-কে সব input-এ থামতে হবে। দ্বিতীয়ত, শর্তটি ⇔: A-এর সদস্য B-তে যায় (“⇒”), আর A-এর বাইরের সদস্য B-এর বাইরে যায় (“⇐”, যা contrapositive আকারে লিখলে w ∉ A ⇒ f(w) ∉ B). তৃতীয়ত, শর্তটি সব w-এর জন্য, এমনকি যে string কোনো বৈধ ⟨M, w⟩ নয়, তার জন্যও। f-কে one-to-one বা onto হতে হয় না: A-এর অনেক সদস্য B-এর একই সদস্যে যেতে পারে, আর B-এর অনেক সদস্যে কেউ না-ও পৌঁছাতে পারে।
Mapping reduction-এর ছবি: f দুই ভাগই রক্ষা করে
বাঁয়ে A-এর জগৎ Σ∗, ডানে B-এর। সবুজ অংশ সদস্য, ধূসর অংশ বাইরের string.
ধরুন A ≤m B. তাহলে:
১. B decidable হলে A decidable.
২. B Turing-recognizable হলে A Turing-recognizable.
অনুসিদ্ধান্ত (contrapositive): A undecidable হলে B undecidable; A recognizable না হলে B-ও recognizable নয়।
প্রমাণ (অংশ ১):
- ধরুন MB B-এর একটি decider, আর f-এর হিসাবকারী যন্ত্র F (সব input-এ থামে)। — অনুমান
- নতুন যন্ত্র N = “input w-এর ওপর: F দিয়ে f(w) হিসাব করুন; তারপর MB-কে f(w)-এর ওপর চালান আর তার রায়ই দিন।” — নির্মাণ
- F সবসময় থামে, MB সবসময় থামে, তাই N সব input-এ থামে: N একটি decider. — দুটি থামা যন্ত্রের পরপর চালানো
- N w গ্রহণ করে ⇔ MB f(w) গ্রহণ করে ⇔ f(w) ∈ B ⇔ w ∈ A. শেষ ধাপটি reduction-এর “⇔”. তাই N A-কে decide করে। ∎
অংশ ২-এর প্রমাণ হুবহু একই, শুধু MB একটি recognizer; তখন N-ও loop করতে পারে, কিন্তু ঠিক A-এর সদস্যই গ্রহণ করে। অনুসিদ্ধান্তটি contrapositive: “B সহজ ⇒ A সহজ” সত্য হলে “A কঠিন ⇒ B কঠিন”-ও সত্য।
আরও দুটি ছোট কিন্তু খুব কাজের তথ্য, দুটিই সংজ্ঞা থেকে সরাসরি আসে:
- Complement: একই f দিয়ে A ≤m B হলে A ≤m B, কারণ w ∈ A ⇔ f(w) ∈ B-এর দুই পাশ উল্টালে w ∉ A ⇔ f(w) ∉ B. এখানে A মানে A-এর complement, Σ∗ ∖ A; কিছু বইয়ে co-A-ও লেখা হয়।
- Transitivity: A ≤m B আর B ≤m C হলে A ≤m C, কারণ দুটি computable function জুড়লে (g ∘ f) আবার computable. তাই undecidability একটি শিকলের মতো ছড়িয়ে পড়ে: ATM থেকে HALTTM, সেখান থেকে আরও দূরে।
একটি সূক্ষ্ম কিন্তু দরকারি পার্থক্য মনে রাখুন। Co-Turing-recognizable (সংক্ষেপে co-recognizable) language মানে যার complement recognizable. পর্ব ৫০ “Decidable আর Turing-recognizable language”-এর মূল উপপাদ্য: L decidable ⇔ L recognizable আর co-recognizable দুটোই। আর পর্ব ৫১-এর ফল: ATM recognizable (universal machine দিয়ে, পর্ব ৪৮) কিন্তু decidable নয়, তাই ATM recognizable নয়। এই তিনটি তথ্যই এই পর্বের পুরো হাতিয়ার।
৩ · প্রথম reduction — ATM ≤m HALTTM
HALTTM = {⟨M, w⟩ : M একটি Turing machine আর M w-এ থামে (গ্রহণ বা বর্জন করে)}। পর্ব ৫১-এ এর একটি ঝলক এসেছে; এখানে পূর্ণ প্রমাণ।
ATM ≤m HALTTM. তাই HALTTM undecidable.
মূল চিন্তা: M গ্রহণ করলে কিছু বদলাবেন না, কিন্তু M বর্জন করলে তাকে জোর করে চিরকাল চালিয়ে দিন। তাহলে “থামা” আর “গ্রহণ” একই কথা হয়ে যায়।
নির্মাণ: f = “input x-এর ওপর: x যদি কোনো বৈধ ⟨M, w⟩ না হয়, একটি নির্দিষ্ট string ⟨L∞, ε⟩ output দিন, যেখানে L∞ সব input-এ loop করে। নইলে M′ = ‘input y-এর ওপর: M-কে y-এর ওপর চালান; M গ্রহণ করলে গ্রহণ, M বর্জন করলে loop করুন’ বানিয়ে ⟨M′, w⟩ output দিন।”
প্রমাণ:
- f computable: f M চালায় না, শুধু M-এর নিয়মের সারণি পড়ে একটি নতুন সারণি লেখে (নিচের কোডে হুবহু এটাই)। সারণি সসীম, তাই f সব input-এ থামে। অবৈধ x-এর জন্য f একটি স্থির string দেয়। — computable
- ⟨M, w⟩ ∈ ATM হলে M w গ্রহণ করে, তাই M′ w গ্রহণ করে, অর্থাৎ থামে: ⟨M′, w⟩ ∈ HALTTM. — “⇒”
- ⟨M, w⟩ ∉ ATM হলে দুই ক্ষেত্র: M w বর্জন করে (তখন M′ loop করে), অথবা M w-এ loop করে (তখন M′-ও loop করে)। দুই ক্ষেত্রেই M′ w-এ থামে না: ⟨M′, w⟩ ∉ HALTTM. অবৈধ x-এর ছবি ⟨L∞, ε⟩-ও HALTTM-এর বাইরে। — “⇐”-এর contrapositive
- উপপাদ্য ২.৩ অনুযায়ী HALTTM decidable হলে ATM decidable হতো, যা পর্ব ৫১-এ অসম্ভব প্রমাণিত। তাই HALTTM undecidable. ∎
এবার f-কে সত্যিকারের কোডে লিখি। যন্ত্রের নিয়ম পর্ব ৪৮-এর ছোট format-এ (q0 1 q1 = R মানে δ(q0, 1) = (q1, 1, R), “=” মানে পড়া চিহ্নটিই লেখা, ␣ ছাপা হয় _), আর কোর্সের রীতি অনুযায়ী সারণিতে না থাকা নিয়ম qreject-এ যায়। f_halt সারণির প্রতিটি “qreject-এ যাও” (লেখা বা নীরব) বদলে দেয় নতুন state qloop-এ, যেখান থেকে যন্ত্র চিরকাল ডানে হাঁটে। Simulator-এ step cap ৫০০: cap ছোঁয়া মানে “এই সীমার মধ্যে রায় নেই”, “কখনো থামবে না” প্রমাণ নয়। পরের ব্লক একই namespace ব্যবহার করবে।
from itertools import product
from collections import Counter
B = "_" # blank
def T(table): # "q read next write move; ..."
d = {}
for rule in table.split(";"):
q, reads, r, w, mv = rule.split()
for s in reads.split(","): d[(q, s)] = (r, s if w == "=" else w, mv)
return d
def run(d, w, cap=500): # direct simulation with a step cap
q, tape, h = "q0", list(w) or [B], 0
for step in range(cap + 1):
if q in ("qacc", "qrej"): return q[1:]
if step == cap: return "cap" # no verdict yet, NOT "loops"
q, tape[h], mv = d.get((q, tape[h]), ("qrej", tape[h], "R"))
h = h + 1 if mv == "R" else max(h - 1, 0)
if h == len(tape): tape.append(B)
def f_halt(d, w): # A_TM <=m HALT_TM: rewrite the table, never run M
gamma = {s for (_, a), (_, b, _) in d.items() for s in (a, b)} | set(w) | {B}
states = {q for (q, _) in d} | {r for (r, _, _) in d.values()}
new = {}
for q in sorted(states - {"qacc", "qrej"}):
for s in sorted(gamma): # missing rule = reject -> loop
r, b, mv = d.get((q, s), ("qrej", s, "R"))
new[(q, s)] = ("qloop" if r == "qrej" else r, b, mv)
for s in gamma: new[("qloop", s)] = ("qloop", s, "R") # walk right forever
return new, w
PAR = T("q0 0 q0 = R; q0 1 q1 = R; q0 _ qacc = R; q1 0 q1 = R; q1 1 q0 = R")
LOOP = T("q0 a qacc = R; q0 b q1 = R; q1 a,b,_ q0 = L")
for name, M, sigma in [("PAR", PAR, "01"), ("LOOP", LOOP, "ab")]:
words = ["".join(t) for k in range(7) for t in product(sigma, repeat=k)]
tally = Counter((run(M, w), run(*f_halt(M, w))) for w in words) # (M, M')
print(name, "M -> M':", dict(tally))
M2, _ = f_halt(LOOP, "")
print("|LOOP| =", len(LOOP), "rules, |LOOP'| =", len(M2), "rules")আসল আউটপুট (ব্রাউজারের Python):
PAR M -> M': {('acc', 'acc'): 64, ('rej', 'cap'): 63}
LOOP M -> M': {('rej', 'cap'): 1, ('acc', 'acc'): 63, ('cap', 'cap'): 63}
|LOOP| = 5 rules, |LOOP'| = 9 rules
প্রতিটি জোড়া (M-এর ফল, M′-এর ফল) গোনা হয়েছে, দৈর্ঘ্য ০ থেকে ৬ পর্যন্ত সব ১২৭টি input-এ। PAR (জোড় সংখ্যক 1) কখনো loop করে না: ৬৪টি গ্রহণ M′-এও গ্রহণ, আর ৬৩টি বর্জন M′-এ cap ছোঁয়, কারণ M′ সেখানে qloop-এ চিরকাল হাঁটে। LOOP (পর্ব ৪৮-এর যন্ত্র: a দিয়ে শুরু হলে গ্রহণ, b দিয়ে শুরু হলে চিরকাল দোলে, ε-তে বর্জন) তিন ফলই দেখায়: গ্রহণ → গ্রহণ, বর্জন → cap, cap → cap. কোথাও ('acc', 'cap') বা ('rej', 'acc') নেই: ঠিক “গ্রহণ ⇔ থামা”. একটি সতর্কতা: এই brute force উপপাদ্যের প্রমাণ নয়, কারণ cap কখনো loop প্রমাণ করে না; প্রমাণ ওপরের চার ধাপে। কোডটি দেখায় f কতটা যান্ত্রিক: LOOP-এর ৫টি নিয়ম থেকে LOOP′-এর ৯টি নিয়ম, M না চালিয়েই।
নিচের stepper f-এর কাজ আর তিনটি instance-এর ভাগ্য ধাপে ধাপে দেখায়।
1q0 a → qacc, a, R2q0 b → q1, b, R3q0 ␣ → qloop, ␣, R ★4q1 a,b,␣ → q0, =, L5qloop a,b,␣ → qloop, R
| instance | |
| LOOP-এর ফল | |
| LOOP′-এর ফল | |
| A ⇔ HALT |
- f-এর input. f পায় ⟨LOOP, w⟩: LOOP-এর ৫টি নিয়ম আর একটি w. f LOOP-কে কোনো input-এ চালায় না; শুধু সারণি পড়ে। লাইন ১, ২, ৪ মূল নিয়ম, অপরিবর্তিত।
- নীরব বর্জন খোঁজা। LOOP-এ (q0, ␣)-এর কোনো নিয়ম নেই, তাই কোর্সের রীতিতে সেটি qreject. f সেখানে লেখে “q0 ␣ → qloop, ␣, R” (লাইন ৩, ★ = নতুন নিয়ম)। LOOP-এ qreject-এ যাওয়া আর কোনো নিয়ম নেই।
- qloop যোগ। qloop-এ প্রতিটি চিহ্নে একই state-এ থেকে, চিহ্ন না বদলে, ডানে সরা (লাইন ৫, তিনটি নিয়ম; চিহ্ন না বদলালে “a → R” ধাঁচে লেখা হয়)। ফল LOOP′: ৫ + ১ + ৩ = ৯টি নিয়ম, কোডের আউটপুটের সঙ্গে মেলে। f-এর output ⟨LOOP′, w⟩, w অপরিবর্তিত।
- w = a. LOOP প্রথম ধাপেই qacc-এ যায়; LOOP′-এও লাইন ১ একই, তাই গ্রহণ করে থামে। ⟨LOOP, a⟩ ∈ ATM আর ⟨LOOP′, a⟩ ∈ HALTTM: হ্যাঁ ⇔ হ্যাঁ।
- w = ε. LOOP ␣ পড়ে, নিয়ম নেই, বর্জন: থামে কিন্তু গ্রহণ করে না। LOOP′ একই জায়গায় qloop-এ যায় আর চিরকাল ডানে হাঁটে। না ⇔ না: বর্জন থেকে loop বানানোই এই reduction-এর প্রাণ।
- w = ba. LOOP b পড়ে q1-এ যায়, q1 বাঁয়ে ফেরে q0-তে, আবার b: চিরকাল। LOOP′-এ এই অংশ অপরিবর্তিত, তাই সেও loop করে। না ⇔ না। তিন ক্ষেত্রেই “M w গ্রহণ করে ⇔ M′ w-এ থামে”.
উল্টো দিকও সত্য: HALTTM ≤m ATM. f′(⟨M, w⟩) = ⟨M″, w⟩, যেখানে M″ = “M চালান; M গ্রহণ বা বর্জন যা-ই করুক, গ্রহণ করুন।” তাহলে M w-এ থামে ⇔ M″ w গ্রহণ করে। দুই দিকে reduction থাকায় ATM আর HALTTM “সমান কঠিন”: একটির decider থাকলে অন্যটিরও থাকত। HALTTM-ও তাই recognizable কিন্তু co-recognizable নয়।
৪ · ETM — complement-এর পথে reduction
ETM = {⟨M⟩ : L(M) = ∅}, অর্থাৎ “এই যন্ত্র কি কোনো string-ই গ্রহণ করে না?” DFA-র জন্য এই emptiness problem সহজ: শুরুর state থেকে কোনো accept state-এ পৌঁছানো যায় কি না দেখলেই হয় (পর্ব ২০), আর CFG-র জন্যও decidable (পর্ব ৩৭)। Turing machine-এ এসে ছবিটি বদলে যায়।
ATM ≤m ETM. তাই ETM undecidable; আর ETM Turing-recognizable-ও নয়।
এখানে লক্ষ করুন: reduction যাচ্ছে ETM-এর complement-এ, ETM-এ নয়। কারণটি প্রমাণের পরে।
নির্মাণ: f(⟨M, w⟩) = ⟨M1⟩, যেখানে M1 = “input x-এর ওপর: x ≠ w হলে বর্জন করুন। x = w হলে M-কে w-এর ওপর চালান, M গ্রহণ করলে গ্রহণ করুন।” w-টি M1-এর নিয়মের ভেতরেই “তারের মতো” বসানো (hard-wired). অবৈধ input-এর জন্য f একটি নির্দিষ্ট ⟨M∅⟩ দেয়, যে সব বর্জন করে।
প্রমাণ:
- f computable: x আর w মেলানোর জন্য |w| + 1টি state-এর একটি শিকল, মাথা আবার ঘর ০-তে ফেরানোর কয়েকটি state, আর M-এর নিয়ম নতুন নামে। সবই সারণি লেখা, M চালানো নয়। — computable
- M w গ্রহণ করলে L(M1) = {w}, ফাঁকা নয়: ⟨M1⟩ ∈ ETM. — “⇒”
- M w গ্রহণ না করলে (বর্জন বা loop) M1 w-কেও গ্রহণ করে না, আর অন্য সব x বর্জন করে: L(M1) = ∅, তাই ⟨M1⟩ ∉ ETM. অবৈধ input-এর ছবি ⟨M∅⟩-ও তাই। — “⇐”
- অতএব ATM ≤m ETM, তাই ETM undecidable. Decidable language complement-এ বদ্ধ (decider-এর গ্রহণ-বর্জন উল্টে দিলেই হয়), তাই ETM decidable হলে ETM-ও হতো। অতএব ETM undecidable. — complement-এ বদ্ধতা
- ETM recognizable: সব string-এর ওপর M-কে পালা করে (পর্ব ৪৫-এর dovetailing) চালান, কোনোটি গ্রহণ হলেই গ্রহণ করুন। তাই ETM co-recognizable. ETM recognizable-ও হলে পর্ব ৫০-এর উপপাদ্যে decidable হতো, যা ধাপ ৪-এর বিরোধী। তাই ETM recognizable নয়। ∎
কেন সরাসরি ATM ≤m ETM নয়? কারণ এমন কোনো reduction-ই নেই। থাকলে একই f দিয়ে ATM ≤m ETM হতো; ETM recognizable, তাই উপপাদ্য ২.৩ অনুযায়ী ATM-ও recognizable হতো, যা মিথ্যা। Mapping reduction recognizability-ও বহন করে, তাই সে “উল্টানো” মানতে পারে না। Sipser-এর বইয়ে ETM-এর প্রমাণ এজন্য একটি সাধারণ “decider ধরে নিয়ে বিরোধ” যুক্তি দিয়ে লেখা, যা আসলে অংশ ৭-এর Turing reduction.
এবার M1-কে সত্যিকারের নিয়মের সারণি হিসেবে বানাই। M-এর state-গুলোর নাম বদলে m. লাগানো হয়, যাতে তুলনার state-এর সঙ্গে সংঘর্ষ না হয়। মাথা ফেরানোর জন্য |w| + 1 বার বাঁয়ে সরানো হয়; শেষ সরানোটি ঘর ০-তে পড়ে, যেখানে কোর্সের রীতিতে বাঁয়ে সরলে head জায়গায় থাকে। এরপর ছোট সব x-এ M1 চালিয়ে দেখা হয় L(M1) সত্যিই {w} নাকি ∅.
def f_empty(d, w): # <M, w> -> <M1>, L(M1) = {w} if M accepts w, else empty
gamma = {s for (_, a), (_, b, _) in d.items() for s in (a, b)} | set(w) | {B}
n, ren = len(w), lambda q: q if q in ("qacc", "qrej") else "m." + q
c = ["q0"] + [f"c{i}" for i in range(1, n + 1)] # compare x with w
back = ["m.q0"] + [f"b{i}" for i in range(1, n + 1)] # walk back to cell 0
M1 = {(c[i], w[i]): (c[i + 1], w[i], "R") for i in range(n)} # x != w: reject
M1[(c[n], B)] = (back[n], B, "L")
for k in range(1, n + 1):
for s in gamma: M1[(back[k], s)] = (back[k - 1], s, "L")
for (q, s), (r, b, mv) in d.items(): M1[(ren(q), s)] = (ren(r), b, mv)
return M1
def lang(d, sigma, n=4): # accepted strings up to length n (capped)
words = ["".join(t) for k in range(n + 1) for t in product(sigma, repeat=k)]
res = {x: run(d, x) for x in words}
return [x or "ε" for x in words if res[x] == "acc"], sum(v == "cap" for v in res.values())
for name, M, sigma, w in [("PAR", PAR, "01", "11"), ("PAR", PAR, "01", "10"),
("LOOP", LOOP, "ab", "ab"), ("LOOP", LOOP, "ab", "ba"),
("LOOP", LOOP, "ab", "")]:
M1 = f_empty(M, w)
acc, caps = lang(M1, sigma)
print(f"{name:4} w={w or 'ε':2} M on w: {run(M, w):3} |M1|={len(M1):2} rules"
f" L(M1) up to len 4: {acc} capped: {caps}")আসল আউটপুট (ব্রাউজারের Python):
PAR w=11 M on w: acc |M1|=14 rules L(M1) up to len 4: ['11'] capped: 0
PAR w=10 M on w: rej |M1|=14 rules L(M1) up to len 4: [] capped: 0
LOOP w=ab M on w: acc |M1|=14 rules L(M1) up to len 4: ['ab'] capped: 0
LOOP w=ba M on w: cap |M1|=14 rules L(M1) up to len 4: [] capped: 1
LOOP w=ε M on w: rej |M1|= 6 rules L(M1) up to len 4: [] capped: 0
পাঁচটি instance, পাঁচটি M1. যেখানে M w গ্রহণ করে (PAR-এ 11, LOOP-এ ab), দৈর্ঘ্য ৪ পর্যন্ত M1 ঠিক একটি string গ্রহণ করে: w নিজে। যেখানে করে না, সেখানে একটিও নয়। LOOP w = ba-র লাইনটি গুরুত্বপূর্ণ: M1 ba-তে LOOP চালায় আর cap ছোঁয় (capped: 1); L(M1) তবু ফাঁকা, কারণ loop মানে গ্রহণ নয়। নিয়মের সংখ্যা: |w| = 2 হলে তুলনার ২টি, ␣-এর ১টি, ফেরার 2 × 3 = ৬টি আর M-এর ৫টি, মোট ১৪; w = ε হলে শুধু ১ + ৫ = ৬. লক্ষ করুন, M1-এর আকার |w|-এর রৈখিক: f সত্যিই সস্তা একটি লেখার কাজ।
1q0 a → c1, R (তুলনা)2c1 b → c2, R (তুলনা)3c2 ␣ → b2, L4b2, b1: সব চিহ্নে বাঁয়ে5m.*: LOOP-এর ৫ নিয়ম
| configuration | |
| কোন অংশ |
- f-এর কাজ। f পায় ⟨LOOP, ab⟩ আর লেখে M1: তুলনার ২টি নিয়ম, ␣-এর ১টি, ফেরার ৬টি আর LOOP-এর ৫টি (নাম বদলে m.q0, m.q1; সারণিতে m.* লেখা). M1 এখন x = ab নিয়ে শুরু করছে: configuration q0 ab.
- প্রথম তুলনা। q0 a পড়ে, যা w-এর প্রথম চিহ্ন: c1-এ যায়, ডানে সরে। x-এর প্রথম চিহ্ন b হলে কোনো নিয়ম থাকত না, আর M1 সঙ্গে সঙ্গে বর্জন করত।
- দ্বিতীয় তুলনা। c1 b পড়ে c2-তে যায়। দুটি চিহ্নই মিলেছে।
- দৈর্ঘ্যও মিলেছে। c2 ␣ পড়ে, অর্থাৎ x-এ আর কিছু নেই, x = ab = w. x লম্বা হলে c2-এর সামনে a বা b থাকত, নিয়ম নেই, বর্জন। এবার b2-তে গিয়ে বাঁয়ে সরা শুরু।
- ফেরা। b2 থেকে b1, মাথা ঘর ০-তে। মোট |w| + 1 = 3টি বাঁ-সরা লাগে: দুটি সত্যিকারের, শেষটি বাঁ প্রান্তে।
- LOOP শুরু। b1 থেকে m.q0, বাঁয়ে সরার চেষ্টা কিন্তু ঘর ০-তে head জায়গায় থাকে। এখন tape-এ ab, মাথা শুরুতে, state m.q0: ঠিক যেন LOOP-কে ab দেওয়া হয়েছে।
- রায়। LOOP a পড়ে গ্রহণ করে, তাই M1 ab গ্রহণ করে: L(M1) = {ab}, ফাঁকা নয়, ⟨M1⟩ ∈ ETM. ⟨LOOP, ba⟩ হলে M1 ba-তে loop করত আর বাকি সব বর্জন করত: L(M1) = ∅.
৫ · REGULARTM — language-এর আকার বদলে দেওয়া
REGULARTM = {⟨M⟩ : L(M) একটি regular language}। প্রশ্নটি বাস্তবে এমন: “এই জটিল program যে কাজ করে, তা কি আসলে একটি সাধারণ regex দিয়েই করা যেত?” উত্তর দেওয়ার কোনো সাধারণ algorithm নেই।
ATM ≤m REGULARTM. তাই REGULARTM undecidable.
কৌশলটি ETM-এর চেয়ে চতুর। এবার M2-এর language দুটি আকারের একটি নেবে: M w গ্রহণ করলে একটি regular language, না করলে একটি non-regular language. সবচেয়ে সুবিধাজনক জোড়া: Σ∗ (regular) আর {0n1n : n ≥ 0} (non-regular, পর্ব ১৭)।
নির্মাণ: f(⟨M, w⟩) = ⟨M2⟩, যেখানে M2 = “input x-এর ওপর: x যদি 0n1n আকারের হয়, গ্রহণ করুন। নইলে M-কে w-এর ওপর চালান, M গ্রহণ করলে গ্রহণ করুন।”
প্রমাণ:
- f computable: 0n1n যাচাইয়ের একটি স্থির যন্ত্র আর M-এর নিয়ম, মাঝে w লেখার অংশ, সবই সারণি জোড়া। — computable
- M w গ্রহণ করলে: 0n1n আকারের x প্রথম ধাপেই গৃহীত, বাকি সব x দ্বিতীয় ধাপে। L(M2) = Σ∗, regular. — “⇒”
- M w গ্রহণ না করলে: দ্বিতীয় ধাপ কখনো গ্রহণ দেয় না (বর্জন বা loop), তাই L(M2) = {0n1n}, non-regular. — “⇐”
- তাই ⟨M, w⟩ ∈ ATM ⇔ ⟨M2⟩ ∈ REGULARTM; উপপাদ্য ২.৩ থেকে REGULARTM undecidable. ∎
এই ধাঁচটি সাধারণ: L(M′)-কে “M w গ্রহণ করে কি না” অনুযায়ী দুটি ভিন্ন জাতের language-এর একটি বানিয়ে দিন, যাদের একটি প্রশ্নের “হ্যাঁ” দিকে, অন্যটি “না” দিকে। পর্ব ৫৩ “Rice-এর theorem”-এ এই ধাঁচটিই একবারে সব “language নিয়ে প্রশ্ন”-এর জন্য প্রমাণ হবে।
নিচের ব্লকে একটি নতুন “খেলনা program-ভাষা”: প্রতিটি program একটি Python generator, যার প্রতিটি yield এক ধাপ, আর return True/False মানে গ্রহণ/বর্জন। f_regular M-কে চালায় না; শুধু একটি নতুন program M2 বানিয়ে ফেরত দেয়। এই ব্লক নিজের namespace-এ চলে।
from itertools import product
# Toy program language: a program is a generator; every "yield" is one step,
# "return True/False" is accept/reject. run() executes it under a step cap.
def run(P, x, cap=300):
g = P(x)
try:
for _ in range(cap): next(g)
return "cap" # no verdict within the cap
except StopIteration as stop:
return "acc" if stop.value else "rej"
def EVEN(x): # accepts strings of even length
for _ in x: yield
return len(x) % 2 == 0
def SPIN(x): # loops forever on inputs starting with 1
while x.startswith("1"): yield
return True
def f_regular(M, w): # A_TM <=m REGULAR_TM: builds M2, never runs M
def M2(x):
n = len(x) // 2
yield # (one step for the shape check)
if x == "0" * n + "1" * n: return True # x in {0^n 1^n}: accept
return (yield from M(w)) # otherwise accept iff M accepts w
return M2
words = ["".join(t) for k in range(7) for t in product("01", repeat=k)]
for name, M, w in [("EVEN", EVEN, "0110"), ("EVEN", EVEN, "011"),
("SPIN", SPIN, "0"), ("SPIN", SPIN, "10")]:
M2 = f_regular(M, w)
res = [run(M2, x) for x in words]
acc = [x or "ε" for x, r in zip(words, res) if r == "acc"]
shown = acc if len(acc) < 10 else f"all {len(acc)} strings"
print(f"{name} w={w:4} M on w: {run(M, w)} L(M2) up to len 6: {shown}"
f" capped: {res.count('cap')}")আসল আউটপুট (ব্রাউজারের Python):
EVEN w=0110 M on w: acc L(M2) up to len 6: all 127 strings capped: 0
EVEN w=011 M on w: rej L(M2) up to len 6: ['ε', '01', '0011', '000111'] capped: 0
SPIN w=0 M on w: acc L(M2) up to len 6: all 127 strings capped: 0
SPIN w=10 M on w: cap L(M2) up to len 6: ['ε', '01', '0011', '000111'] capped: 123
যখন M w গ্রহণ করে, M2 দৈর্ঘ্য ৬ পর্যন্ত সব ১২৭টি string গ্রহণ করে: Σ∗-এর ছায়া। যখন করে না, M2 ঠিক চারটি string গ্রহণ করে, ε, 01, 0011, 000111: {0n1n}-এর ছায়া। শেষ লাইনে SPIN “10”-এ চিরকাল ঘোরে, তাই বাকি ১২৩টি x-এ M2 cap ছোঁয়; সেগুলো গ্রহণ নয়, তাই language একই। মনে রাখুন, সসীম দৈর্ঘ্যের ছায়া দেখে regularity প্রমাণ হয় না (যেকোনো সসীম set regular); কোড দেখায় f-এর আচরণ, প্রমাণ আসে ওপরের যুক্তি আর pumping lemma থেকে।
৬ · EQTM — recognizable-ও নয়, co-recognizable-ও নয়
EQTM = {⟨M1, M2⟩ : L(M1) = L(M2)}। Software-এর ভাষায়: “নতুন লেখা function কি পুরনোটার সঙ্গে সব input-এ একই কাজ করে?” এটি equivalence problem-এর Turing machine রূপ। প্রথমে undecidability খুব সহজে আসে: ETM ≤m EQTM, f(⟨M⟩) = ⟨M, M∅⟩, যেখানে M∅ সব বর্জন করে; L(M) = ∅ ⇔ L(M) = L(M∅)। কিন্তু আরও শক্ত একটি ফল সত্য।
EQTM Turing-recognizable নয়, আর co-Turing-recognizable-ও নয়।
প্রমাণে দুটি আলাদা reduction লাগে, দুটিই ATM থেকে, আর দুটিই অংশ ২-এর complement-নিয়ম ব্যবহার করে। নিচের stepper পুরো যুক্তি ধাপে ধাপে সাজায়।
1f: ⟨M, w⟩ → ⟨M_rej, M_w⟩2A_TM ≤m co-EQ_TM3co-A_TM ≤m EQ_TM4g: ⟨M, w⟩ → ⟨M_acc, M_w⟩5A_TM ≤m EQ_TM6co-A_TM ≤m co-EQ_TM
| M w গ্রহণ করে | |
| M w গ্রহণ করে না | |
| সিদ্ধান্ত |
- প্রথম f. ⟨M, w⟩ থেকে দুটি যন্ত্র: Mrej সব input বর্জন করে (L = ∅), আর Mw = “যেকোনো input-এ M-কে w-এর ওপর চালান, M গ্রহণ করলে গ্রহণ”। M w গ্রহণ করলে L(Mw) = Σ∗, না করলে ∅.
- “গ্রহণ ⇔ অসমান”। M w গ্রহণ করলে ∅ ≠ Σ∗, অসমান; না করলে ∅ = ∅, সমান। তাই ⟨M, w⟩ ∈ ATM ⇔ f(⟨M, w⟩) ∉ EQTM: ATM ≤m EQTM.
- Complement নিয়ম। একই f দিয়ে ATM ≤m EQTM. EQTM recognizable হলে উপপাদ্য ২.৩ অনুযায়ী ATM recognizable হতো: মিথ্যা। তাই EQTM recognizable নয়।
- দ্বিতীয় g. এবার প্রথম যন্ত্র Macc, যে সব গ্রহণ করে (L = Σ∗); দ্বিতীয়টি একই Mw.
- “গ্রহণ ⇔ সমান”। M w গ্রহণ করলে Σ∗ = Σ∗, সমান; না করলে Σ∗ ≠ ∅. তাই ATM ≤m EQTM.
- দ্বিতীয় অসম্ভবতা। Complement নিয়মে ATM ≤m EQTM; তাই EQTM recognizable নয়, অর্থাৎ EQTM co-recognizable নয়। দুই দিকের দরজাই বন্ধ। ∎
এখন পর্যন্ত দেখা সমস্যাগুলোকে এক সারণিতে রাখি। “recognizable” কলাম মানে language নিজে recognizable, “co-recognizable” মানে তার complement recognizable.
| সমস্যা | decidable | recognizable | co-recognizable | কোথা থেকে |
|---|---|---|---|---|
| EDFA, ACFG | হ্যাঁ | হ্যাঁ | হ্যাঁ | পর্ব ২০, ৩৭, ৫০ |
| ATM, HALTTM | না | হ্যাঁ | না | পর্ব ৫১, অংশ ৩ |
| ETM | না | না | হ্যাঁ | অংশ ৪ |
| REGULARTM | না | না | না | অংশ ৫ আর নিচের অনুচ্ছেদ |
| EQTM | না | না | না | অংশ ৬ |
REGULARTM-এর সারির প্রমাণও দুটি reduction দিয়ে হয়। অংশ ৫-এর f দেয় ATM ≤m REGULARTM, তাই complement নিয়মে ATM ≤m REGULARTM: REGULARTM co-recognizable নয়। আর ভূমিকা উল্টে M3 = “x যদি 0n1n আকারের হয়, M-কে w-এর ওপর চালান আর M গ্রহণ করলে গ্রহণ করুন; অন্য সব x বর্জন করুন” নিলে M w গ্রহণ করলে L(M3) = {0n1n} (non-regular), না করলে ∅ (regular). তাই ATM ≤m REGULARTM, অর্থাৎ ATM ≤m REGULARTM: REGULARTM recognizable-ও নয়।
৭ · Computation history আর Turing reduction — আরও শক্ত হাতিয়ার
এ পর্যন্ত প্রতিটি reduction-এ নতুন যন্ত্র M-কে চালিয়েছে। কিন্তু অনেক প্রশ্ন যন্ত্র নিয়ে নয়: grammar, domino বা সমীকরণ নিয়ে। সেখানে ATM থেকে reduce করতে একটি সেতু লাগে, যার নাম computation history.
M w গ্রহণ করলে তার accepting computation history হলো configuration-এর সসীম ক্রম C1#C2#…#Cl, যেখানে C1 = q0 w শুরুর configuration, প্রতিটি Ci ⊢ Ci+1 (M-এর এক ধাপ), আর Cl একটি accepting configuration. (Configuration-এর u q v লেখা পর্ব ৪৩-এর।)
মূল পর্যবেক্ষণ: একটি string সত্যিই M-এর w-এর ওপর accepting history কি না, তা যাচাই করা খুব সহজ ও স্থানীয় কাজ: শুরু ঠিক কি না, শেষ accepting কি না, আর পাশাপাশি প্রতিটি জোড়া Ci, Ci+1 শুধু head-এর আশপাশে আলাদা কি না। তাই “M w গ্রহণ করে” প্রশ্নটি বদলে যায় “এমন কোনো string আছে কি, যা একটি বৈধ history?” প্রশ্নে। এই কৌশলে প্রমাণ হয়:
- ELBA = {⟨B⟩ : B একটি linear bounded automaton আর L(B) = ∅} undecidable, যদিও ALBA decidable (Sipser-এর বইয়ে দুটিই আছে)।
- ALLCFG = {⟨G⟩ : L(G) = Σ∗} undecidable: “বৈধ history নয়” এমন সব string একটি CFG দিয়ে বর্ণনা করা যায়।
- Post correspondence problem undecidable: history-কে domino-র সারিতে সাজানো। এগুলোর পূর্ণ নির্মাণ পর্ব ৫৪ “Post correspondence problem আর grammar-এর undecidable প্রশ্ন”-এ।
এবার দ্বিতীয় হাতিয়ার। Mapping reduction-এ B-কে মাত্র একবার প্রশ্ন করা যায়, আর তার উত্তরই হুবহু চূড়ান্ত উত্তর। যদি B-কে বারবার প্রশ্ন করা যায়, উত্তর উল্টানো যায়, পরের প্রশ্ন আগের উত্তরের ওপর বাছা যায়? তখন পাওয়া যায় আরও সাধারণ ধারণা।
B-এর জন্য একটি oracle Turing machine হলো এমন TM, যে চলার মাঝে যেকোনো string y নিয়ে এক ধাপে জেনে নিতে পারে “y ∈ B?” A Turing reducible B-তে, লেখা A ≤T B, যদি B-এর oracle-সহ একটি যন্ত্র আছে যা A decide করে।
সম্পর্কগুলো এমন। প্রথমত, A ≤m B হলে A ≤T B: f(w) হিসাব করে oracle-কে একবার জিজ্ঞেস করুন। দ্বিতীয়ত, দিকের নিয়মের প্রথম অংশ Turing reduction-এও খাটে: A ≤T B আর B decidable হলে A decidable (oracle-এর জায়গায় decider বসান)। তৃতীয়ত, উল্টোটি সত্য নয়। সবচেয়ে সরল উদাহরণ: ATM ≤T ATM, oracle-এর উত্তর উল্টে দিলেই হলো। কিন্তু ATM ≤m ATM নয়, কারণ তাহলে ATM recognizable হতো। একইভাবে ETM ≤T ATM সত্য (M থেকে এমন M′ বানান যে সব string পালা করে চালিয়ে কোনোটি গ্রহণ হলে গ্রহণ করে, তারপর oracle-কে জিজ্ঞেস করুন ⟨M′, ε⟩ ∈ ATM? আর উত্তর উল্টে দিন), অথচ অংশ ৪-এ দেখেছেন ETM ≤m ATM অসম্ভব।
কোনটি কখন: শুধু “undecidable” দেখাতে হলে দুটোই চলে, আর Turing reduction লেখা প্রায়ই সহজ (“ধরুন R B decide করে; তাহলে A-এর decider S এভাবে…”)। কিন্তু recognizability নিয়ে কিছু বলতে হলে mapping reduction লাগে, কারণ Turing reduction complement থেকে আলাদা করতে পারে না। আর polynomial সময়ের সংস্করণ ≤p (পর্ব ৫৯ “Polynomial-time reduction আর NP-completeness”) mapping reduction-এরই দ্রুত রূপ।
৮ · সাধারণ ভুল আর reduction প্রমাণের ছাঁচ
Reduction-এর প্রমাণ ছোট, কিন্তু তিনটি জায়গায় বারবার ভুল হয়: দিক, f-এর computability, আর “⇔”-এর একটি দিক বাদ পড়া। সবচেয়ে পরিচিতটি দিয়ে শুরু।
1দাবি: COUPON undecidable2“প্রমাণ”: COUPON ≤m A_TM3তাহলে কী জানা গেল?4পরীক্ষা: E_DFA ≤m A_TM5সংশোধন: HALT_TM ≤m COUPON6তিন শর্ত যাচাই
| reduction | |
| যা পাওয়া যায় |
- দাবি। COUPON = {⟨P⟩ : বাজারঘরের discount script P কোনো অর্ডারে ১০০০ টাকার বেশি ছাড় দেয়}। দাবি: COUPON undecidable.
- “প্রমাণ”। একজন লিখলেন: “f(⟨P⟩) = ⟨MP, ε⟩, যেখানে MP সব অর্ডার পালা করে চালিয়ে বড় ছাড় পেলে গ্রহণ করে। তাহলে ⟨P⟩ ∈ COUPON ⇔ f(⟨P⟩) ∈ ATM. ATM undecidable, তাই COUPON undecidable.” Reduction নিজে ঠিক, কিন্তু দিক উল্টো।
- আসলে কী জানা গেল? COUPON ≤m ATM থেকে উপপাদ্য ২.৩ বলে: ATM decidable হলে COUPON decidable (ATM তা নয়, তাই কিছু মেলে না), আর ATM recognizable বলে COUPON recognizable. Undecidability নিয়ে কিছুই না।
- পরীক্ষা। একই যুক্তি একটি সহজ সমস্যায় চালিয়ে দেখুন। যেকোনো decidable L-এর জন্য L ≤m ATM: f(x) = x ∈ L হলে একটি “সব গ্রহণ করা” যন্ত্র আর ε, নইলে একটি “সব বর্জন করা” যন্ত্র আর ε. তাহলে ভুল যুক্তিটি EDFA-কেও undecidable বলত, যা মিথ্যা। যে যুক্তি মিথ্যা প্রমাণ করে, সেটি যুক্তিই নয়।
- সংশোধন। জানা-কঠিন থেকে নতুন সমস্যার দিকে: f(⟨P′, w⟩) = ⟨S⟩, যেখানে S = “যেকোনো অর্ডারে: P′-কে w-এর ওপর চালান; থামলে ২০০০ টাকা ছাড় দিন, অন্যথায় ছাড় নেই।” P′ w-এ থামে ⇔ S কোনো অর্ডারে বড় ছাড় দেয়। তাই HALTTM ≤m COUPON, আর COUPON undecidable.
- তিন শর্ত। f computable (S-এর লেখা বানানো মাত্র, P′ চালানো নয়); “⇔”-এর দুই দিক (থামলে বড় ছাড়, না থামলে কোনো ছাড়ই নয়); আর দিক: জানা-কঠিন HALTTM বাঁয়ে, নতুন COUPON ডানে। ∎
নিচের ছোট JavaScript সাহায্যকারী ঠিক এই যুক্তি যান্ত্রিকভাবে করে: জানা তথ্য আর একটি দাবি করা reduction দিলে সে শুধু উপপাদ্য ২.৩-এর চারটি বৈধ সিদ্ধান্ত টানে, আর দেখে আপনার দাবি সেগুলোর একটি কি না। NEWPROB মানে যে নতুন সমস্যার কিছুই জানা নেই।
// What does "A <=m B" really let you conclude? Known facts in, valid conclusions out.
const known = { // dec = decidable, rec = Turing-recognizable
A_TM: { dec: false, rec: true }, coA_TM: { dec: false, rec: false },
E_DFA: { dec: true, rec: true }, NEWPROB: {}, // NEWPROB: unknown
};
function consequences(A, B) { // the only four valid moves
const a = known[A], b = known[B], out = [];
if (b.dec === true) out.push([A, "dec", true]); // B decidable => A decidable
if (b.rec === true) out.push([A, "rec", true]); // B recognizable => A recognizable
if (a.dec === false) out.push([B, "dec", false]); // A undecidable => B undecidable
if (a.rec === false) out.push([B, "rec", false]); // A not rec. => B not rec.
return out;
}
function check(A, B, claim) { // claim = [problem, property, value]
const out = consequences(A, B);
const clash = out.find(([p, k, v]) => known[p][k] === !v);
const ok = out.some(c => c.join() === claim.join());
const verdict = clash ? "IMPOSSIBLE: no such f exists (contradicts known facts)"
: ok ? "valid" : "does NOT follow (wrong direction?)";
console.log(`${A} <=m ${B} => ${claim[0]} ${claim[1]}=${claim[2]} : ${verdict}`);
}
check("A_TM", "NEWPROB", ["NEWPROB", "dec", false]); // the right direction
check("NEWPROB", "A_TM", ["NEWPROB", "dec", false]); // the classic mistake
check("NEWPROB", "E_DFA", ["NEWPROB", "dec", true]); // easy side: decidable
check("E_DFA", "NEWPROB", ["NEWPROB", "dec", true]); // wrong way round again
check("coA_TM", "NEWPROB", ["NEWPROB", "rec", false]); // non-recognizability
check("A_TM", "E_DFA", ["E_DFA", "dec", false]); // would contradict factsআসল আউটপুট (ব্রাউজারের JavaScript):
A_TM <=m NEWPROB => NEWPROB dec=false : valid
NEWPROB <=m A_TM => NEWPROB dec=false : does NOT follow (wrong direction?)
NEWPROB <=m E_DFA => NEWPROB dec=true : valid
E_DFA <=m NEWPROB => NEWPROB dec=true : does NOT follow (wrong direction?)
coA_TM <=m NEWPROB => NEWPROB rec=false : valid
A_TM <=m E_DFA => E_DFA dec=false : IMPOSSIBLE: no such f exists (contradicts known facts)
প্রথম দুই লাইন একই সিদ্ধান্ত চায়, কিন্তু শুধু প্রথমটি বৈধ: কঠিনতা ≤ চিহ্নের বাঁ থেকে ডানে যায়। তৃতীয় আর চতুর্থ লাইন সহজতার দিক দেখায়: সহজ সমস্যায় (EDFA) reduce করলে নতুন সমস্যা decidable, কিন্তু সহজ সমস্যা থেকে reduce করলে কিছুই জানা যায় না। পঞ্চম লাইন উপপাদ্য ৬.১-এর কৌশল: ATM থেকে reduce করে non-recognizability. শেষ লাইনটি আরও মজার: ATM ≤m EDFA দাবি করলে জানা তথ্যের সঙ্গে বিরোধ বাধে, তাই এমন f আদৌ থাকতে পারে না। কেউ এমন f “বানিয়ে” দেখালে নিশ্চিত থাকুন, তার f হয় computable নয়, নয়তো “⇔” ভাঙা।
Reduction প্রমাণের ছাঁচ
বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় “X undecidable প্রমাণ করুন” প্রশ্নে এই পাঁচ ধাপের কাঠামো নিরাপদ:
- উৎস বাছুন: জানা-undecidable একটি A (প্রায়ই ATM বা HALTTM; non-recognizability-র জন্য ATM). লিখুন: “দেখাব A ≤m X.”
- f বর্ণনা করুন: “input ⟨M, w⟩-এর ওপর: নিচের যন্ত্র M′ বানান, ⟨M′⟩ output দিন।” M′-এর বর্ণনা দিন উদ্ধৃতিচিহ্নে। অবৈধ input-এর ছবিও বলুন।
- Computability: এক বাক্যে বলুন f শুধু বর্ণনা লেখে, M চালায় না।
- “⇔” দুই দিকে: M w গ্রহণ করলে L(M′) কী, তা X-এর ভেতরে কেন; না করলে (বর্জন এবং loop দুই ক্ষেত্রেই) L(M′) কী, তা X-এর বাইরে কেন।
- উপসংহার: “উপপাদ্য অনুযায়ী X decidable হলে A decidable হতো; বিরোধ। ∎”
| ভুল | কেমন দেখায় | কীভাবে ধরবেন |
|---|---|---|
| উল্টো দিক | নতুন সমস্যা X ≤m ATM দেখিয়ে “X undecidable” | যুক্তিটি EDFA-এ চালান; সেটিকেও undecidable বললে যুক্তি ভুল |
| Non-computable f | “f: M-কে w-এ চালান, গ্রহণ করলে … output দিন” | f কি সব input-এ থামে? M loop করলে f আটকে যায় |
| “⇔”-এর এক দিক বাদ | শুধু “M গ্রহণ করলে M′ ∈ X” দেখানো | M বর্জন করলে আর loop করলে আলাদা করে লিখুন |
| Loop ক্ষেত্র ভুলে যাওয়া | “M গ্রহণ না করলে বর্জন করে” ধরে নেওয়া | “গ্রহণ না করা” = বর্জন বা loop; দুটিই পরীক্ষা করুন |
| Complement গুলিয়ে ফেলা | ATM ≤m ETM “প্রমাণ” | Recognizability মেলান: ĒTM recognizable হলে এটি অসম্ভব |
বাস্তবে এর মানে কী? Undecidability বলে না যে কোনো নির্দিষ্ট program বিশ্লেষণ করা যায় না; বলে, সব input-এ সবসময় থেমে সবসময় সঠিক উত্তর দেয় এমন একটি যাচাইকারী নেই। বাস্তবের static analysis tool, linter বা type checker তাই আনুমানিক: কেউ নিরাপদ পক্ষে থেকে মাঝে মাঝে মিথ্যা সতর্কবার্তা দেয়, কেউ কিছু ভুল এড়িয়ে যায়, কেউ সময়সীমায় থেমে “জানি না” বলে। Software testing কোর্সের পর্ব ০৬-এ static analysis-এর ব্যবহারিক দিক আছে; এই সীমার বিস্তারিত পর্ব ৫৫ “বাস্তবে undecidability” আর পর্ব ৭৮-এ।
আরও গভীরে: ≤T দিয়ে সমস্যাগুলোকে “সমান কঠিন” দলে ভাগ করলে প্রতিটি দলকে বলে Turing degree; decidable সমস্যার দল সবচেয়ে নিচে, আর ATM-এর দল (যাকে প্রায়ই 0′ লেখা হয়) recognizable সমস্যার মধ্যে সবচেয়ে ওপরে। Post ১৯৪৪ সালে প্রশ্ন তোলেন, এই দুইয়ের মাঝে কোনো recognizable degree আছে কি না; ১৯৫৬–৫৭ সালে Muchnik আর Friedberg আলাদাভাবে “আছে” প্রমাণ করেন, যা priority method নামের নতুন কৌশলের জন্ম দেয়। আবার ATM-এর oracle-সহ যন্ত্রের নিজস্ব halting problem আরও কঠিন, এভাবে arithmetical hierarchy-র অসীম সিঁড়ি গড়ে ওঠে; EQTM সেই সিঁড়িতে ATM-এর ওপরের ধাপে বসে।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- Mapping reduction-এর সংজ্ঞা দিন। Computable f, যাতে সব w-এর জন্য w ∈ A ⇔ f(w) ∈ B; লেখা A ≤m B.
- A ≤m B আর A undecidable হলে কী বলা যায়? B undecidable. B undecidable হলে A সম্পর্কে কিছুই বলা যায় না।
- HALTTM undecidable প্রমাণ করুন। ATM ≤m HALTTM: M′ = “M চালান; গ্রহণে গ্রহণ, বর্জনে loop”.
- ETM কি recognizable? না; ĒTM recognizable আর ETM undecidable, তাই ETM recognizable হতে পারে না।
- Mapping আর Turing reduction-এর পার্থক্য? Mapping-এ একবার প্রশ্ন আর উত্তর হুবহু; Turing-এ oracle-কে বারবার, উত্তর উল্টানোও চলে। ĀTM ≤T ATM, কিন্তু ≤m নয়।
৯ · AI-এর যুগে reduction প্রমাণ যাচাই
AI assistant-কে কোনো X-এর undecidability প্রমাণ করতে বললে প্রায়ই আত্মবিশ্বাসী, সুন্দর গোছানো উত্তর আসে, যার ভেতরে ঠিক অংশ ৮-এর ভুলগুলো লুকিয়ে থাকে। সবচেয়ে সাধারণ: উল্টো দিকে reduce করা (“X ≤ ATM, তাই X undecidable”), এমন f লেখা যা নিজেই M চালায় (তাই computable নয়), “⇔”-এর শুধু একটি দিক দেখানো, loop ক্ষেত্র ভুলে যাওয়া, decidable আর recognizable গুলিয়ে ফেলা, আর Rice বা Post-এর উপপাদ্যের শর্ত বাদ দিয়ে বলা। কখনো কখনো সাল বা বইয়ের অধ্যায়ের নম্বরও বানানো হয়।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| “X ≤m ATM, তাই X undecidable” | প্রতিটি ≤ চিহ্নে জিজ্ঞেস করুন: কোনটি জানা-কঠিন? সেটি বাঁয়ে আছে তো? Direction checker-এ চালান |
| f-এর ভেতরে “M-কে w-এ চালান, তারপর …” | f সব input-এ থামে কি না দেখুন; M চালানোর কাজ M′-এর ভেতরে থাকার কথা |
| “⇔”-এর এক দিক, বা “M গ্রহণ না করলে বর্জন করে” | বর্জন আর loop আলাদা করে লিখতে বলুন; ছোট যন্ত্রে brute force-এ দুই দিক মেলান |
| “ETM recognizable” বা “EQTM co-recognizable” | সারণির শ্রেণি মিলান; complement-এর recognizability আলাদা করে যুক্তি দিন |
| বানানো রেফারেন্স বা সাল | Sipser (reducibility অধ্যায়) বা Hopcroft–Motwani–Ullman-এ নিজে খুঁজে মিলিয়ে নিন |
AI-কে কাজে লাগানোর ভালো উপায়: প্রমাণের কাঠামো নিজে ঠিক করে দিন, আর প্রতিটি ধাপ আলাদা করে লিখতে বলুন, যাতে আপনি একটি একটি করে যাচাই করতে পারেন।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Reduction-এর f-কে computable হতে হয় কেন? f-এর ওপর এই শর্ত না থাকলে কী ভেঙে পড়ত?
উপপাদ্য ২.৩-এর প্রমাণে যন্ত্র N দুটি কাজ পরপর করে: প্রথমে f(w) হিসাব, তারপর B-এর decider চালানো। পুরো যুক্তির ভার দাঁড়িয়ে আছে প্রথম কাজটি সবসময় থামার ওপর। f যদি কোনো w-এ থামতে না পারত, N সেখানে আটকে যেত, আর N decider হতো না। তাই “B decidable ⇒ A decidable” ভেঙে পড়ত।
শর্তটি তুলে দিলে কী হয়, একটি চরম উদাহরণে দেখুন। ধরুন যেকোনো function f চলবে, computable হোক বা না হোক। তাহলে ATM-এর জন্য f(x) = “x ∈ ATM হলে 1, নইলে 0” নিন; এটি ATM থেকে {1}-এ একটি “reduction”, কারণ x ∈ ATM ⇔ f(x) ∈ {1}. অথচ {1} একটি সসীম, অতি সহজ language. যুক্তিটি তাহলে বলত “ATM সহজ” বা অন্য দিকে “{1} কঠিন”: দুটিই অর্থহীন। সব কঠিনতা f-এর ভেতরে লুকিয়ে পড়ত। Computable শর্ত ঠিক এটাই আটকায়: অনুবাদক নিজে সমস্যা সমাধান করতে পারবে না, সে শুধু যান্ত্রিকভাবে রূপ বদলাবে।
এই কারণেই reduction প্রমাণের সবচেয়ে পরিচিত ভুল হলো f-এর ভেতরে “M-কে w-এর ওপর চালান” লেখা। এমন f M loop করলে থামে না। ঠিক কৌশল হলো M চালানোর নির্দেশটিকে নতুন যন্ত্র M′-এর বর্ণনার ভেতরে লিখে রাখা। f শুধু বর্ণনা লেখে, যা সবসময় সসীম কাজ; চালানোর ঝুঁকি নেয় M′, যে চলবে কি না সেটাই তো প্রশ্ন। এই পর্বের Python কোডে f_halt আর f_empty ঠিক এভাবে নিয়মের সারণি লেখে, কোনো যন্ত্র না চালিয়ে।
Complexity তত্ত্বে শর্তটি আরও কড়া হয়। পর্ব ৫৯-এর ≤p-এ f-কে polynomial সময়ে চলতে হয়, কারণ সেখানে প্রশ্ন “সমাধান আছে কি” নয়, “দ্রুত সমাধান আছে কি”। f যদি exponential সময় নিত, তাহলে আবারও সব কাজ f-ই করে ফেলত, আর B-এর দ্রুততা দিয়ে A-এর দ্রুততা প্রমাণ হতো না। Logspace reduction-এর মতো আরও দুর্বল f-ও আছে, P-এর ভেতরের সূক্ষ্ম শ্রেণির জন্য। প্রতিটি ক্ষেত্রে নীতি একই: f যে শ্রেণি নিয়ে কথা হচ্ছে, তার চেয়ে দুর্বল বা সমান শক্তির হতে হবে।
মূল উপলব্ধি: f-এর computability শর্ত নিশ্চিত করে যে কঠিনতা অনুবাদকের ভেতরে লুকাতে পারে না; f শুধু বর্ণনা লিখবে, চালাবে না, আর তার শক্তি যে প্রশ্ন নিয়ে কাজ, তার সমান বা কম হবে।
প্র ০২দৈনন্দিন ভাষায় “A-কে B-তে নামিয়ে আনা” শুনলে মনে হয় A-ই বড় সমস্যা। গণিতের দিক কেন উল্টো, আর ছাত্রছাত্রী ও পেশাদার উভয়েই এই ভুল এত বেশি করেন কেন?
“নামিয়ে আনা” কথাটি ভাবায় যেন একটি বড় জিনিসকে ছোট করা হচ্ছে। গণিতে A ≤m B মানে: “B সমাধান করতে পারলে A-ও পারা যায়”। অর্থাৎ B একটি হাতিয়ার, আর A সেই হাতিয়ারে সমাধানযোগ্য একটি কাজ। হাতিয়ার কাজের চেয়ে অন্তত সমান শক্তিশালী হতেই হবে। তাই ≤ চিহ্নের ডান দিকের B অন্তত বাঁ দিকের A-এর মতো কঠিন। একটি উপমা: ঢাকা থেকে চট্টগ্রাম যাওয়াকে “কমলাপুরে পৌঁছে একটি ট্রেন ধরা”-তে নামিয়ে আনলে প্রমাণ হয় ট্রেন ব্যবস্থা এই যাত্রার জন্য যথেষ্ট; যাত্রাটি ট্রেন ব্যবস্থার চেয়ে কঠিন, এমন কিছু প্রমাণ হয় না।
বিভ্রান্তির দ্বিতীয় স্তর আসে contrapositive থেকে। আমরা reduction ব্যবহার করি অসম্ভবতা প্রমাণে, যেখানে সিদ্ধান্তটি উল্টে যায়: “B সহজ ⇒ A সহজ” থেকে “A কঠিন ⇒ B কঠিন”। এক বাক্যে দুবার উল্টানো মাথায় রাখা কঠিন, তাই অনেকেই “X আর ATM-এর মধ্যে একটি reduction আছে, তাই X কঠিন” লিখে ফেলেন, দিক না দেখে। অংশ ৮-এর stepper দেখিয়েছে, এই উল্টো দিকের যুক্তি EDFA-এর মতো সহজ সমস্যাকেও undecidable বলে দিত, কারণ প্রতিটি decidable language ATM-এ reduce হয়।
পেশাদাররাও এই ভুল করেন, বিশেষ করে NP-hardness-এর ক্ষেত্রে। “আমাদের scheduling সমস্যাটা SAT-এ encode করা যায়, তাই এটা NP-hard” কথাটি প্রায়ই শোনা যায়। কিন্তু SAT-এ encode করা মানে X ≤p SAT, যা শুধু বলে X NP-এর ভেতরে আছে (বা SAT solver দিয়ে সমাধান করা যায়); কঠিনতা নয়। NP-hardness দেখাতে উল্টো দিক লাগে: SAT বা আরেকটি NP-hard সমস্যা থেকে X-এ। মজার ব্যাপার হলো, প্রথম কাজটি প্রকৌশলে খুব দরকারি (পর্ব ৭৩-এ SAT solver দিয়ে বাস্তব সমস্যা সমাধান), কিন্তু তা কঠিনতার প্রমাণ নয়।
ব্যবহারিক কৌশল: প্রতিটি reduction পুরো বাক্যে লিখুন, “যদি X-এর একটি decider থাকত, তাহলে ATM-এর decider এভাবে বানাতাম”। এই বাক্যে X আগে এলে আর ATM পরে, দিক ঠিক। অংশ ৮-এর JavaScript checker ঠিক এই নিয়মটিই যান্ত্রিকভাবে প্রয়োগ করে।
মূল উপলব্ধি: A ≤ B মানে B একটি হাতিয়ার যা দিয়ে A সমাধান হয়, তাই B অন্তত A-এর মতো কঠিন; কঠিনতা প্রমাণে জানা-কঠিন সমস্যাকে সবসময় বাঁয়ে রাখতে হয়।
প্র ০৩Turing reduction mapping reduction-এর চেয়ে শক্তিশালী, তবু recognizability প্রমাণে mapping reduction-ই লাগে কেন? এই দুই ধারণার ইতিহাস কী?
Turing reduction-এ B-এর oracle-কে যতবার খুশি প্রশ্ন করা যায়, আর উত্তর নিয়ে যা খুশি করা যায়, উল্টে দেওয়াসহ। এই স্বাধীনতাই তার দুর্বলতা হয়ে দাঁড়ায় যখন প্রশ্ন recognizability নিয়ে। ধরুন A ≤T B আর B recognizable. B-এর oracle-এর জায়গায় B-এর recognizer বসালে, “না” উত্তরের প্রশ্নে recognizer হয়তো কখনো থামবে না, আর পুরো যন্ত্র আটকে যাবে। তাই কিছুই প্রমাণ হয় না। সবচেয়ে স্পষ্ট উদাহরণ: ATM ≤T ATM, অথচ ATM recognizable আর ATM নয়। Turing reduction একটি সমস্যা আর তার complement-কে আলাদা করতে পারে না।
Mapping reduction-এ ঠিক একটি প্রশ্ন, আর তার উত্তরই চূড়ান্ত, কোনো রূপান্তর ছাড়া। ফলে recognizer বসালেও কাঠামো টেকে: f(w) হিসাব করুন (সবসময় থামে), তারপর B-এর recognizer চালান; সে গ্রহণ করলে গ্রহণ। এজন্য EQTM-এর মতো সূক্ষ্ম শ্রেণিবিভাগ (recognizable-ও নয়, co-recognizable-ও নয়) শুধু mapping reduction দিয়েই প্রমাণ করা যায়।
ইতিহাসে দুটিই এসেছে প্রায় একই সময়ে। Turing তাঁর ১৯৩৯ সালের গবেষণাপত্র “Systems of Logic Based on Ordinals”-এ oracle machine (তাঁর ভাষায় o-machine) প্রস্তাব করেন। Emil Post ১৯৪৪ সালের প্রবন্ধে সমস্যাগুলোর মধ্যে আপেক্ষিক কঠিনতার একটি পদ্ধতিগত তত্ত্ব গড়েন, many-one ও one-one reducibility আলোচনা করেন, আর Turing-এর ধারণাকে “Turing reducibility” নামে ব্যবহার করেন বলে সাধারণত বলা হয়। সেই প্রবন্ধেই তিনি প্রশ্ন তোলেন, ATM-এর চেয়ে সহজ কিন্তু undecidable কোনো recognizable সমস্যা আছে কি না, যার উত্তর পরে Friedberg আর Muchnik দেন।
Complexity-তে একই পার্থক্য আবার আসে। Karp ১৯৭২ সালে polynomial many-one reduction ব্যবহার করেন, আর Cook ১৯৭১ সালে polynomial Turing reduction-এর মতো একটি ধারণা। NP আর coNP-এর পার্থক্য রক্ষা করতে Karp-এর কড়া রূপটি বেশি কাজের, ঠিক যেমন recognizable আর co-recognizable-এর পার্থক্য রক্ষায় mapping reduction.
মূল উপলব্ধি: বেশি স্বাধীন reduction বেশি সমস্যাকে জুড়তে পারে কিন্তু কম সূক্ষ্ম পার্থক্য রক্ষা করে; complement-এর পার্থক্য রাখতে হলে একবার প্রশ্ন, হুবহু উত্তরের mapping reduction লাগে।
প্র ০৪EQTM undecidable হলে software-এ “নতুন function পুরনোটার সমান কাজ করে কি না” যাচাই কি অসম্ভব? Compiler, refactoring tool আর পরীক্ষকরা তাহলে কী করেন?
উপপাদ্য ৬.১ খুব শক্ত কথা বলে: EQTM recognizable-ও নয়, co-recognizable-ও নয়। অর্থাৎ এমন কোনো algorithm নেই যা সব ক্ষেত্রে “সমান” নিশ্চিত করে, আর এমনও নেই যা সব “অসমান” ক্ষেত্রে একসময় তা ধরে ফেলে। General-purpose ভাষার দুটি function তুলনায় তাই কোনো নিখুঁত, সাধারণ যাচাইকারী থাকতে পারে না। কিন্তু এর মানে এই নয় যে কাজটি বাস্তবে অসম্ভব; মানে হলো, সব ক্ষেত্রের জন্য একটি পদ্ধতি নেই।
বাস্তবে প্রকৌশলীরা তিন পথে কাজ চালান। প্রথম পথ: সমস্যাটি ছোট করা। Compiler optimisation-এর প্রতিটি রূপান্তর (যেমন একটি অব্যবহৃত variable মুছে ফেলা) এমনভাবে নকশা করা হয় যে সেটি “নির্মাণ অনুযায়ী” অর্থ রক্ষা করে; compiler দুটি যেকোনো program তুলনা করে না, শুধু নির্দিষ্ট নিরাপদ নিয়মে বদলায়। Refactoring tool-ও একইভাবে নির্দিষ্ট ধরনের পরিবর্তন করে। দ্বিতীয় পথ: সীমিত মডেলে যাওয়া। DFA-র equivalence decidable (পর্ব ২০), আর সসীম অবস্থার hardware circuit তুলনায় SAT বা BDD-ভিত্তিক “equivalence checking” শিল্পে ব্যাপকভাবে চলে, কারণ সেখানে সমস্যাটি decidable, যদিও কঠিন। তৃতীয় পথ: পরীক্ষা। Differential testing আর property-based testing-এ দুটি version-কে অনেক input-এ চালিয়ে ফল মেলানো হয়; অমিল পেলে নিশ্চিত প্রমাণ, মিল পেলে শুধু আস্থা।
তৃতীয় পথটি আসলে EQTM-এর একটি অসম্পূর্ণ খোঁজ। উপপাদ্য বলে, এই খোঁজ সব অসমান জোড়া একসময় ধরবে এমন নিশ্চয়তা নেই। কেন? একটি পার্থক্য এমন input-এ লুকিয়ে থাকতে পারে, যেখানে একটি version loop করে আর অন্যটি গ্রহণ করে; সীমিত সময়ের পরীক্ষা loop আর “ধীর” আলাদা করতে পারে না। এই পর্বের কোডে cap-ছোঁয়াকে আলাদা ফল হিসেবে ছাপার কারণও এটাই।
বাজারঘরের দল যদি পুরনো discount script নতুন করে লেখে, তাদের জন্য সৎ পরামর্শ: পরিবর্তনগুলো ছোট ও নিয়মভিত্তিক রাখুন, গুরুত্বপূর্ণ অংশ সসীম state machine বা সারণিতে প্রকাশ করুন যাতে যান্ত্রিক তুলনা সম্ভব হয়, আর বাকিটা ব্যাপক পরীক্ষায় ঢাকুন। কোনো tool “সব ক্ষেত্রে সমতা প্রমাণ করে” বলে দাবি করলে জিজ্ঞেস করুন, কোন সীমিত ভাষা বা কোন শর্তের অধীনে।
মূল উপলব্ধি: EQTM-এর অসম্ভবতা সাধারণ যাচাইকারীকে নিষেধ করে, নির্দিষ্ট কাজকে নয়; বাস্তব tool সীমিত মডেল, নিয়মভিত্তিক রূপান্তর আর পরীক্ষার মিশ্রণে কাজ করে, আর প্রতিটির সীমা জেনেই ব্যবহার করতে হয়।
প্র ০৫Computation history কেন এত শক্তিশালী হাতিয়ার? Turing machine-এর প্রশ্নকে grammar, domino বা সমীকরণের প্রশ্নে বদলাতে এটি কী ভূমিকা রাখে?
এই পর্বের প্রতিটি reduction-এ নতুন বস্তু একটি Turing machine ছিল, যে ভেতরে M চালাতে পারে। কিন্তু grammar বা domino কিছু “চালাতে” পারে না; তাদের শক্তি সীমিত। তাহলে ATM-এর কঠিনতা তাদের মধ্যে কীভাবে ঢোকে? উত্তর: গণনা চালানোর বদলে গণনার লিখিত রেকর্ড যাচাই করানো। একটি accepting computation history হলো configuration-এর সসীম তালিকা, আর তালিকাটি বৈধ কি না, তা দেখতে শুধু পাশাপাশি দুটি configuration তুলনা করতে হয়। পাশাপাশি তুলনা একটি স্থানীয়, সরল কাজ, যা দুর্বল মডেলও পারে।
এভাবে “M w গ্রহণ করে কি?” প্রশ্নটি একটি অস্তিত্বের প্রশ্নে বদলে যায়: “এমন কোনো string আছে কি, যা এই স্থানীয় নিয়মগুলো মানে?” LBA-র ক্ষেত্রে একটি LBA বানানো হয় যা ঠিক বৈধ history গ্রহণ করে; তার language ফাঁকা ⇔ M w গ্রহণ করে না। তাই ELBA undecidable. CFG-র ক্ষেত্রে আরও চতুর কৌশল লাগে, কারণ CFG দুটি পাশাপাশি configuration সরাসরি মেলাতে পারে না; তাই history লেখা হয় পালা করে উল্টো করে, আর “বৈধ নয়” এমন string-এর language বর্ণনা করা হয়, যা একটি CFG পারে। ফলে ALLCFG undecidable. PCP-তে history-কে domino-র সারি হিসেবে সাজানো হয়, যাতে ওপরের সারি সবসময় নিচের চেয়ে এক configuration এগিয়ে থাকে।
ঐতিহাসিকভাবে সবচেয়ে বিখ্যাত প্রয়োগ Hilbert-এর দশম সমস্যা: পূর্ণসংখ্যার বহুপদী সমীকরণের সমাধান আছে কি না নির্ণয়ের algorithm. Martin Davis, Hilary Putnam, Julia Robinson আর ১৯৭০ সালে Yuri Matiyasevich-এর কাজ মিলে দেখায় এমন algorithm নেই (MRDP theorem নামে পরিচিত); মূল ধারণা হলো একটি গণনার পুরো ইতিহাস সংখ্যা দিয়ে লেখা আর তার বৈধতাকে বহুপদী সমীকরণে প্রকাশ। এর বিস্তারিত পর্ব ৫৫-এ হালকাভাবে আসবে; এখানে মূল কথা, একই কৌশল সম্পূর্ণ ভিন্ন জগতে কাজ করে।
Complexity-তেও একই ধারণা ফিরে আসে। পর্ব ৬০-এর Cook–Levin theorem-এ একটি nondeterministic যন্ত্রের polynomial দৈর্ঘ্যের history-কে একটি টেবিলে লিখে তার স্থানীয় বৈধতাকে Boolean সূত্রে প্রকাশ করা হয়। অর্থাৎ undecidability থেকে NP-completeness পর্যন্ত, “গণনার রেকর্ড স্থানীয়ভাবে যাচাইযোগ্য” এই একটি পর্যবেক্ষণ বারবার কাজে লাগে।
মূল উপলব্ধি: Computation history গণনাকে একটি স্থানীয়ভাবে যাচাইযোগ্য বস্তুতে রূপ দেয়, তাই দুর্বল মডেলও “বৈধ রেকর্ড আছে কি” প্রশ্নের মাধ্যমে Turing machine-এর কঠিনতা বহন করতে পারে।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। reduce_halt.py আর reduce_empty.py ব্লকে নিজের যন্ত্র লিখে f_halt আর f_empty দিয়ে উত্তর যাচাইও করতে পারেন।
-
নির্মাণ: ALLTM = {⟨M⟩ : L(M) = Σ∗}. (ক) ATM ≤m ALLTM-এর একটি reduction নকশা করুন আর “⇔” প্রমাণ করুন। (খ) আরও এগিয়ে: ATM ≤m ALLTM-এর একটি reduction দিয়ে দেখান ALLTM recognizable নয়।
(ক) f(⟨M, w⟩) = ⟨Mw⟩, Mw = “input x-এর ওপর: x উপেক্ষা করে M-কে w-এর ওপর চালান; গ্রহণ করলে গ্রহণ।” f শুধু বর্ণনা লেখে, তাই computable. M w গ্রহণ করলে প্রতিটি x গৃহীত, L(Mw) = Σ∗. না করলে (বর্জন বা loop) কোনো x গৃহীত নয়, L(Mw) = ∅ ≠ Σ∗. তাই ⟨M, w⟩ ∈ ATM ⇔ ⟨Mw⟩ ∈ ALLTM, আর ALLTM undecidable.
(খ) g(⟨M, w⟩) = ⟨M′⟩, M′ = “input x-এর ওপর: M-কে w-এর ওপর ঠিক |x| ধাপ চালান। এর মধ্যে M গ্রহণ করলে বর্জন করুন; নইলে গ্রহণ করুন।” ধাপ-সীমার কারণে M′ সব x-এ থামে। M w গ্রহণ না করলে কোনো ধাপ-সীমায় গ্রহণ দেখা যায় না, তাই সব x গৃহীত: L(M′) = Σ∗. M w গ্রহণ করলে, ধরুন t ধাপে, তবে |x| ≥ t এমন সব x বর্জিত: L(M′) সসীম, Σ∗ নয়। তাই ⟨M, w⟩ ∈ ATM ⇔ ⟨M′⟩ ∈ ALLTM. ALLTM recognizable হলে ATM-ও হতো: বিরোধ। (ক) থেকে complement নিয়মে ATM ≤m ALLTM, তাই ALLTM co-recognizable-ও নয়। ∎
-
প্রমাণ (ভুল খুঁজুন): একজন লিখেছেন: “ETM ≤m ATM-এর জন্য f(⟨M⟩) এভাবে: M-কে সব string-এর ওপর পালা করে চালান; কোনোটি গ্রহণ হলে ⟨Mno, ε⟩ output দিন (Mno সব বর্জন করে), কোনোটিই না হলে ⟨Myes, ε⟩ (Myes সব গ্রহণ করে)। তাহলে L(M) = ∅ ⇔ f(⟨M⟩) ∈ ATM.” ভুলটি কোথায়, আর এমন কোনো সঠিক f কেন থাকতেই পারে না?
ভুল: f computable নয়। L(M) = ∅ হলে পালা করে চালানো কখনো শেষ হয় না, তাই f “কোনোটিই না হলে” শাখায় কখনো পৌঁছায় না; f সেই input-এ থামে না। “⇔” শর্তটি কাগজে ঠিক, কিন্তু f-কে সব input-এ থামতে হবে, আর সেখানেই যুক্তি ভাঙে। f নিজে M চালাচ্ছে: সবচেয়ে পরিচিত সংকেত।
কেন অসম্ভব: ETM ≤m ATM থাকলে, ATM recognizable বলে উপপাদ্য ২.৩ অনুযায়ী ETM recognizable হতো। কিন্তু অংশ ৪-এ প্রমাণিত, ETM recognizable নয়। তাই কোনো computable f-ই কাজটি করতে পারে না। (Turing reduction অবশ্য আছে: ETM ≤T ATM, অংশ ৭।)
-
ফল অনুমান: reduce_empty.py-এর f_empty-কে PAR (জোড় সংখ্যক 1 গ্রহণ করে, ৫টি নিয়ম, tape-চিহ্ন 0, 1, ␣) আর w = 0 দিলে M1-এ কয়টি নিয়ম হবে?
lang(M1, "01")দৈর্ঘ্য ৪ পর্যন্ত কী ছাপবে? x = 0-তে M1-এর পুরো configuration-ক্রম লিখুন। তারপর w = 1 দিলে কী বদলায়?নিয়ম: তুলনা ১টি (q0 0 → c1), c1 ␣ → b1 ১টি, ফেরা b1-এ তিন চিহ্নে ৩টি, PAR-এর ৫টি: মোট ১০. Language: PAR 0 গ্রহণ করে (শূন্যটি 1, জোড়), তাই
(['0'], 0): শুধু 0, কোনো cap নেই।Configuration: q0 0 ⊢ 0 c1 ␣ ⊢ b1 0␣ ⊢ m.q0 0␣ (ঘর ০-তে L, head জায়গায়) ⊢ 0 m.q0 ␣ ⊢ 0␣ qacc ␣. পাঁচটি ধাপে গ্রহণ।
w = 1: তুলনার নিয়ম হয় q0 1 → c1; সংখ্যা একই, ১০. কিন্তু PAR 1 বর্জন করে (একটি 1, বিজোড়), তাই
([], 0): L(M1) = ∅. দুটি M1 মাত্র একটি নিয়মে আলাদা, অথচ একটি ETM-এর বাইরে, আরেকটি ভেতরে। Scratch-এ চালিয়ে ঠিক এই ফল পাওয়া গেছে। -
প্রমাণ: (ক) প্রমাণ করুন, A ≤m B আর B ≤m C হলে A ≤m C. (খ) প্রমাণ করুন, A ≤m B হলে A ≤m B. (গ) এ দুটি আর অংশ ৩ ব্যবহার করে দেখান HALTTM recognizable নয়।
(ক) ১. f আর g যথাক্রমে A → B আর B → C-এর computable reduction. ২. h = g ∘ f: F চালিয়ে f(w) পান, তার ওপর G চালান; দুটিই থামে, তাই h computable. ৩. w ∈ A ⇔ f(w) ∈ B ⇔ g(f(w)) ∈ C. ∎
(খ) একই f. ১. w ∈ A ⇔ f(w) ∈ B. ২. দুই পাশ negate করলে w ∉ A ⇔ f(w) ∉ B, অর্থাৎ w ∈ A ⇔ f(w) ∈ B. ∎
(গ) অংশ ৩: ATM ≤m HALTTM. (খ) থেকে ATM ≤m HALTTM. HALTTM recognizable হলে উপপাদ্য ২.৩-এর অংশ ২ অনুযায়ী ATM recognizable হতো, যা মিথ্যা (পর্ব ৫১)। তাই HALTTM recognizable নয়, অর্থাৎ HALTTM co-recognizable নয়। ∎
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমনতুন সমস্যা X undecidable প্রমাণের reduction-এর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- একটি জানা-undecidable সমস্যা A বাছা, যেমন ATM
- f বর্ণনা করা: ⟨M, w⟩ থেকে একটি নতুন যন্ত্রের বর্ণনা লেখা
- দেখানো যে f সব input-এ থামে, অর্থাৎ computable
- “⇔”-এর দুই দিক প্রমাণ: গ্রহণ হলে X-এ, বর্জন বা loop হলে X-এর বাইরে
- উপসংহার: X decidable হলে A decidable হতো, তাই X undecidable
A ≤m B (mapping reduction) জানা আছে। কোন সিদ্ধান্তটি সবসময় বৈধ?
- B undecidable হলে A undecidable
- A undecidable হলে B undecidable
- A decidable হলে B decidable
- A recognizable হলে B recognizable
ATM ≤m HALTTM-এর reduction-এ ⟨M, w⟩ থেকে ⟨M′, w⟩ বানানো হয়। M′-এর কোন বর্ণনা সঠিক?
- M চালানো, আর গ্রহণ বা বর্জন যা-ই হোক, থামা
- input উপেক্ষা করে সবসময় loop করা
- M চালানো; M গ্রহণ করলে গ্রহণ, M বর্জন করলে loop
- f নিজেই M-কে w-এ চালিয়ে ফল দেখে M′ ঠিক করে
ETM = {⟨M⟩ : L(M) = ∅}. এর সম্পর্কে কোন বিবৃতিটি সঠিক?
- ETM undecidable, co-recognizable, কিন্তু recognizable নয়
- ETM decidable, কারণ DFA-র emptiness decidable
- ETM recognizable কিন্তু co-recognizable নয়
- ATM ≤m ETM দিয়ে এর undecidability সরাসরি আসে
একজন লিখলেন: “নতুন সমস্যা X-এর জন্য X ≤m ATM দেখিয়েছি, আর ATM undecidable, তাই X undecidable.” এই যুক্তির মূল্যায়ন কোনটি?
- সঠিক, কারণ reduction transitive
- সঠিক, যদি reduction-টি Turing reduction হয়
- ভুল, কারণ এটি দেখায় X decidable
- ভুল দিক: এতে X সম্পর্কে শুধু recognizability জানা যায়, undecidability নয়
Mapping reduction (≤m) আর Turing reduction (≤T) সম্পর্কে কোনটি সঠিক?
- প্রতিটি Turing reduction একটি mapping reduction
- A ≤T B আর B recognizable হলে A recognizable
- ĀTM ≤T ATM সত্য, কিন্তু ĀTM ≤m ATM সত্য নয়
- Turing reduction দিয়ে undecidability প্রমাণ করা যায় না
EQTM = {⟨M1, M2⟩ : L(M1) = L(M2)}. এর শ্রেণি কোনটি?
- Recognizable নয়, co-recognizable-ও নয়
- Co-recognizable, কিন্তু recognizable নয়
- Recognizable, কিন্তু co-recognizable নয়
- Decidable, product construction দিয়ে
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- A ≤m B মানে computable f, যাতে সব w-এর জন্য w ∈ A ⇔ f(w) ∈ B. f সব input-এ থামে, আর M চালায় না, শুধু বর্ণনা লেখে।
- দিকের নিয়ম: B decidable (recognizable) হলে A decidable (recognizable); A undecidable (non-recognizable) হলে B-ও তাই। জানা-কঠিন সমস্যা সবসময় বাঁয়ে।
- একই f দিয়ে Ā ≤m B̄; আর ≤m transitive.
- ATM ≤m HALTTM, ATM ≤m ĒTM, ATM ≤m REGULARTM; EQTM recognizable-ও নয়, co-recognizable-ও নয়।
- Turing reduction (oracle) বেশি সাধারণ কিন্তু recognizability বহন করে না; computation history দুর্বল মডেলের প্রশ্নকে undecidable দেখানোর সেতু।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ০৪ · Theory of Computation-এর প্রমাণ — string-এর ওপর induction, construction আর diagonalizationপটভূমিReduction-এর দিক আর contrapositive-এর প্রথম পরিচয়।
- পর্ব ৫১ · Diagonalization আর halting problemফিরে দেখুনATM undecidable-এর diagonalization প্রমাণ, এই পর্বের সব reduction-এর উৎস।
- পর্ব ৪৮ · Universal Turing machine — program-ই dataফিরে দেখুন⟨M⟩ encoding আর ATM কেন recognizable.
- পর্ব ২০ · Regular language-এর decision problem — emptiness, equivalence আর inclusionতুলনাDFA-র জন্য যে প্রশ্নগুলো decidable, TM-এ সেগুলোই undecidable.
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৫৩ Rice-এর theorem.
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ১৮ — Cardinality আর Cantor-এর diagonalপাশের ট্র্যাকUndecidability-র গোড়ার গণিত: countable আর uncountable.
- Software Testing · পর্ব ০৬ — Static testing আর static analysisপাশের ট্র্যাকUndecidability-র সীমার মধ্যে বাস্তবের static analysis কীভাবে কাজ করে।