এই পর্বে যা শিখবেন
- HALTTM আর ATM-এর নিখুঁত সংজ্ঞা, আর decider-এর কাছে আমরা ঠিক কী চাই
- যন্ত্র countable আর language uncountable থেকে “recognizable নয় এমন language আছে”-এর প্রমাণ, আর তার সীমা
- ATM undecidable-এর পূর্ণ diagonalization প্রমাণ (যন্ত্র D), আর Python-এ একটি ছোট diagonal টেবিল
- ATM recognizable কিন্তু ĀTM recognizable নয়; reduction দিয়ে HALTTM undecidable, আর reduction-এর দিক কেন গুরুত্বপূর্ণ
- Programmer-এর ভাষায় halts() কেন লেখা যায় না, timeout কেন সমাধান নয়, আর এই theorem-এর মানে কী নয়
১ · বাজারঘরের স্বপ্নের যাচাইকারী — “এই program কি কখনো থামবে?”
বাজারঘর বিক্রেতাদের একটি সুবিধা দিতে চায়: প্রত্যেকে নিজের ছাড়ের নিয়ম একটি ছোট script হিসেবে লিখে দেবেন, যেমন “তিনটি শার্ট কিনলে চতুর্থটি অর্ধেক দামে”। Checkout-এর সময় script চলবে। ভয় একটাই: কোনো script যদি ভুল করে অসীম loop-এ পড়ে, তাহলে ক্রেতার checkout আটকে যাবে। তাই দলের প্রস্তাব, script জমা নেওয়ার আগেই একটি “থামা-যাচাইকারী” প্রতিটি script আর প্রতিটি সম্ভাব্য অর্ডার দেখে বলবে, script থামবে কি না। যাচাইকারীর কাছে দুটি দাবি: উত্তর সবসময় ঠিক হবে, আর যাচাইকারী নিজে সবসময় থামবে।
ক্রিকেটের third umpire-এর কথা ভাবুন। একটি review এলে তাঁকে একটি সিদ্ধান্ত দিতেই হয়, আর সেটি ঠিক হওয়া চাই; “আরও ভাবছি” বলে খেলা অনন্তকাল থামিয়ে রাখা যায় না। থামা-যাচাইকারীর দায়িত্বও তেমন: প্রতিটি প্রশ্নে সসীম সময়ে একটি সঠিক “হ্যাঁ” বা “না”। এই পর্বে প্রমাণ হবে, program-এর থামা নিয়ে এমন umpire থাকা গাণিতিকভাবে অসম্ভব।
প্রশ্নটিকে পর্ব ০৫-এর রীতিতে language হিসেবে লেখা যাক। একটি Turing machine M আর input w-কে একটি string ⟨M, w⟩ হিসেবে encode করা যায় (কীভাবে, তা পর্ব ৪৮-এ দেখেছেন)। তাহলে দুটি language:
পর্ব ৪৩-এ দেখেছেন, একটি TM কোনো input-এ তিনভাবে শেষ হতে পারে: accept, reject, অথবা কখনো না থামা (loop). HALTTM জিজ্ঞেস করে “প্রথম দুটির একটি কি ঘটবে?”, আর ATM জিজ্ঞেস করে “প্রথমটি কি ঘটবে?”। বাজারঘরের যাচাইকারী মানে HALTTM-এর একটি decider: এমন TM, যা প্রতিটি input-এ থামে আর ঠিক HALTTM-এর string-গুলো গ্রহণ করে। Church–Turing thesis (পর্ব ৪৭) অনুযায়ী “কোনো TM নেই” মানে “কোনো algorithm নেই”, যেকোনো ভাষায়, যেকোনো কম্পিউটারে।
এই পর্বের পথ তিন ধাপে। প্রথমে একটি গোনার যুক্তি দেখাবে, undecidable language থাকতেই হবে (অংশ ২)। তারপর diagonalization দেখাবে, নির্দিষ্টভাবে ATM undecidable (অংশ ৩–৪)। শেষে একটি reduction ATM থেকে HALTTM-এ অসম্ভবতা বয়ে নিয়ে যাবে (অংশ ৬)। মাঝখানে অংশ ৫ দেখাবে, ATM-এর “হ্যাঁ” দিক আর “না” দিক কেন সমান নয়।
২ · গোনার যুক্তি — যন্ত্র কম, language বেশি
প্রথম ফলটি প্রায় হিসাবের খাতা থেকে আসে। পরীক্ষার হলে প্রত্যেক পরীক্ষার্থীর একটি রোল নম্বর থাকে: ১, ২, ৩, … তালিকা অসীম হতে পারে, কিন্তু প্রত্যেকে একটি সসীম নম্বর পান। যে set-এর উপাদানদের এভাবে নম্বর দেওয়া যায়, সেটি countable. Turing machine-দের এমন রোল নম্বর দেওয়া যায়; language-দের যায় না।
Σ = {0, 1} হলে Σ-এর ওপর এমন একটি language আছে, যা কোনো Turing machine recognize করে না। আরও শক্ত করে: Turing-recognizable language-গুলোর set countable, অথচ সব language-এর set uncountable.
প্রমাণ।
- প্রতিটি TM M একটি সসীম বস্তু, তাই একটি binary string ⟨M⟩ হিসেবে লেখা যায়, আর আলাদা যন্ত্রের বর্ণনা আলাদা। — encoding, পর্ব ৪৮
- Σ∗ countable: shortlex ক্রমে ε, 0, 1, 00, … প্রতিটি string একটি সসীম অবস্থান পায় (পর্ব ০২)। Countable set-এর যেকোনো subset-ও countable, তাই সব TM-এর বর্ণনার set countable. — Σ∗ গোনা যায়
- প্রতিটি TM ঠিক একটি language L(M) recognize করে। তাই recognizable language-গুলোর set হলো একটি countable set-এর ছবি (M ↦ L(M)), যা নিজেও countable. — countable set-এর ছবি countable
- সব language-এর set হলো P(Σ∗), আর Cantor-এর theorem অনুযায়ী এটি uncountable (পর্ব ০২)। — Cantor
- একটি countable set একটি uncountable set-এর সমান হতে পারে না, তাই কিছু language recognizable নয়। ∎
যুক্তিটি আসলে আরও বেশি বলে: recognizable language-গুলো সব language-এর মধ্যে নগণ্য একটি অংশ, যেমন সব বাস্তব সংখ্যার মধ্যে ভগ্নাংশগুলো। কিন্তু এর একটি বড় দুর্বলতা আছে। এটি অস্তিত্ব দেখায়, নাম দেখায় না। হয়তো যে language-গুলো চেনা যায় না, সেগুলো সবই অর্থহীন, এলোমেলো set, যা কেউ কখনো জানতে চাইবে না। পর্ব ০৪-এ diagonalization দিয়ে একটি নির্দিষ্ট language D = {wi : wi ∉ L(Mi)} বানানো হয়েছিল, কিন্তু সেটিও কৃত্রিম। আমাদের দরকার একটি স্বাভাবিক প্রশ্ন, যেটি programmer সত্যিই জিজ্ঞেস করেন: “এই program এই input-এ কী করবে?” Cantor-এর diagonal ধারণাই (ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ১৮) সেখানে নিয়ে যায়, একটি নতুন মোড় দিয়ে।
৩ · ATM undecidable — diagonalization-এর পূর্ণ প্রমাণ
এবার মূল theorem. প্রমাণটি contradiction-এর প্রমাণ: ধরে নেব ATM-এর একটি decider আছে, তারপর সেটি দিয়ে এমন একটি যন্ত্র বানাব যার আচরণ অসম্ভব।
ATM = {⟨M, w⟩ : M একটি TM আর M w গ্রহণ করে} decidable নয়।
প্রমাণ।
- বিপরীতে ধরি, H একটি decider যা ATM decide করে। অর্থাৎ যেকোনো TM M আর string w-এর জন্য H(⟨M, w⟩) থামে, আর M w গ্রহণ করলে accept করে, M w গ্রহণ না করলে (reject বা loop করলে) reject করে। — অনুমান
- H ব্যবহার করে একটি নতুন TM D বানাই। D = “input ⟨M⟩ পেলে, যেখানে M একটি TM: (ক) input থেকে string ⟨M, ⟨M⟩⟩ বানান; (খ) সেই string-এ H চালান; (গ) H accept করলে reject করুন, H reject করলে accept করুন।” — নির্মাণ
- D সত্যিই একটি TM: ধাপ (ক) শুধু একটি string নকল করা, যা যান্ত্রিক; ধাপ (খ)-এ H একটি subroutine; ধাপ (গ) দুটি উত্তর অদলবদল। H সবসময় থামে, তাই D-ও সবসময় থামে। — D একটি decider
- D-এর সংজ্ঞা থেকে, যেকোনো TM M-এর জন্য: D ⟨M⟩ গ্রহণ করে ⇔ H ⟨M, ⟨M⟩⟩ reject করে ⇔ M ⟨M⟩ গ্রহণ করে না। — H-এর সঠিকতা
- D নিজেও একটি TM, তাই ধাপ ৪-এ M = D বসানো যায়: D ⟨D⟩ গ্রহণ করে ⇔ D ⟨D⟩ গ্রহণ করে না। কোনো বক্তব্য তার নিজের অস্বীকারের সমতুল্য হতে পারে না। — স্ববিরোধ
- অনুমানটি ছাড়া বাকি সব ধাপ নিখুঁত, তাই অনুমানটিই মিথ্যা: ATM-এর কোনো decider নেই। ∎
যন্ত্র D-এর ভেতরে কী আছে
D নিজে কিছু নতুন হিসাব করে না; সে শুধু H-কে একটি বিশেষ প্রশ্ন করে আর উত্তর উল্টে দেয়।
শেষ ধাপটি সবচেয়ে সূক্ষ্ম, তাই নিচের stepper-এ আলাদা করে দেখুন। “D নিজের বর্ণনা পায়” কথাটি অদ্ভুত শোনালেও এতে কোনো চালাকি নেই: ⟨D⟩ অন্য যেকোনো string-এর মতোই একটি string, আর একটি program আরেকটি program-এর source code input হিসেবে নিতে পারে; compiler রোজ তা-ই করে। এই ধরনের self-reference-ই diagonalization-এর প্রাণ।
- ধরি H আছে
A_TM deciderসবসময় থামে - D বানানো
H-এর উল্টোinput ⟨M⟩ - D-কে ⟨D⟩
H(⟨D, ⟨D⟩⟩)নিজের বর্ণনা - H বলে accept
D rejectH ভুল - H বলে reject
D acceptH আবার ভুল - H থাকতে পারে না
A_TM undecidableঅনুমান মিথ্যা
- অনুমান। ধরি H নামে একটি TM আছে, যা প্রতিটি ⟨M, w⟩-এ থামে আর ঠিক বলে M w গ্রহণ করে কি না। এই একটিমাত্র অনুমান থেকেই সব কিছু আসবে।
- নির্মাণ। D input ⟨M⟩ নেয়, H-কে জিজ্ঞেস করে “M কি নিজের বর্ণনা ⟨M⟩ গ্রহণ করে?”, আর উত্তরের উল্টো করে। H সবসময় থামে বলে D-ও সবসময় থামে, তাই D-এর উত্তর সবসময় accept বা reject; loop-এর সুযোগ নেই।
- নিজের বর্ণনা। D একটি TM, তাই তারও একটি বর্ণনা ⟨D⟩ আছে। D-কে ⟨D⟩ দিলে D ভেতরে H-কে জিজ্ঞেস করে: “D কি ⟨D⟩ গ্রহণ করে?” অর্থাৎ D নিজের আচরণ নিয়েই প্রশ্ন করছে।
- প্রথম ক্ষেত্র। H যদি accept করে, তার দাবি “D ⟨D⟩ গ্রহণ করে”। কিন্তু D-এর নিয়মে H accept করলে D reject করে। তাহলে D ⟨D⟩ গ্রহণ করে না, অর্থাৎ H-এর উত্তর ভুল।
- দ্বিতীয় ক্ষেত্র। H যদি reject করে, তার দাবি “D ⟨D⟩ গ্রহণ করে না”। কিন্তু তখন D accept করে। আবার H ভুল। H-এর তৃতীয় কোনো বিকল্প নেই, কারণ সে decider: থামতেই হবে।
- সিদ্ধান্ত। দুই ক্ষেত্রেই H একটি নির্দিষ্ট input ⟨D, ⟨D⟩⟩-এ ভুল উত্তর দেয়, অথচ ধরা হয়েছিল H সব input-এ ঠিক। তাই এমন H থাকতে পারে না। লক্ষ করুন, স্ববিরোধ D নিয়ে নয়, H নিয়ে: D শুধু H থাকলেই থাকত।
৪ · কেন “diagonal” — Python-এ একটি ছোট টেবিল
প্রমাণটির নাম diagonalization কেন, তা একটি টেবিলে পরিষ্কার হয়। সব TM-কে একটি তালিকায় সাজান: M1, M2, … (অংশ ২ অনুযায়ী এটি সম্ভব)। সারি i হলো যন্ত্র Mi, কলাম j হলো string ⟨Mj⟩, আর ঘর (i, j)-তে লেখা Mi ⟨Mj⟩ গ্রহণ করে কি না। H থাকলে প্রতিটি ঘর পূরণ করা যেত। D কর্ণ, অর্থাৎ ঘর (i, i), বরাবর প্রতিটি উত্তর উল্টে নিজের সারি বানায়। কিন্তু D নিজেও কোনো Mk, তাই তার সারি টেবিলে আছে, আর ঘর (k, k)-তে সারিটিকে নিজের উল্টো হতে হবে।
পর্ব ০৪-এর diagonal-এর সঙ্গে পার্থক্যটি লক্ষ করুন। সেখানে D ছিল শুধু একটি language, কোনো যন্ত্র নয়; তাই সে তালিকার বাইরে থেকে গেল, কোনো স্ববিরোধ হলো না। এখানে D একটি যন্ত্র, কারণ তাকে H দিয়ে বানানো হয়েছে। তাই D-কে তালিকার ভেতরে থাকতে হয়, আর সেখানেই বিস্ফোরণ।
নিচের ব্লকে পাঁচটি খুব ছোট “program” আছে, প্রতিটি একটি Python function, যা input হিসেবে একটি string (আরেকটি program-এর source code) নেয়। ⟨Pi⟩ হলো Pi-এর নিজের source text. প্রতিটি yield একটি ধাপ, আর প্রতিটি run-এ ধাপের সীমা, অর্থাৎ step cap, ১,০০০। ঘরে A মানে accept, R মানে reject, ~ মানে সীমার মধ্যে থামেনি।
LIB = '''
def P1(s):
yield; return True # accept every input
def P2(s):
yield; return len(s) % 2 == 0 # accept even length
def P3(s):
while "while" in s: yield # loop on text with a loop
return True
def P4(s):
yield; return False # reject every input
def P5(s):
yield; return "False" in s # accept if text says False
'''
env = {}; exec(LIB, env)
names = ["P1", "P2", "P3", "P4", "P5"]
desc = {"P" + c[1]: "def " + c for c in LIB.split("def ")[1:]} # <P_i>
def run(name, s, cap=1000): # "A" accept, "R" reject, "~" cap
g = env[name](s)
for _ in range(cap):
try: next(g)
except StopIteration as e: return "A" if e.value else "R"
return "~"
print(" " + " ".join(f"<{m}>" for m in names))
for p in names:
print(p, " " + " ".join(run(p, desc[m]) for m in names))
D = ["R" if run(m, desc[m]) == "A" else "A" for m in names] # flip diagonal
print("D ", " " + " ".join(D))
for i, p in enumerate(names):
print(f"D vs {p}: differs at <{p}> ({run(p, desc[p])} vs {D[i]})")
print("lengths:", [len(desc[m]) for m in names])আসল আউটপুট (ব্রাউজারের Python):
<P1> <P2> <P3> <P4> <P5>
P1 A A A A A
P2 R R R R A
P3 A A ~ A A
P4 R R R R R
P5 R R R A A
D R A A A R
D vs P1: differs at <P1> (A vs R)
D vs P2: differs at <P2> (R vs A)
D vs P3: differs at <P3> (~ vs A)
D vs P4: differs at <P4> (R vs A)
D vs P5: differs at <P5> (A vs R)
lengths: [73, 73, 95, 73, 80]
P2-এর সারি source-এর দৈর্ঘ্যের ওপর নির্ভর করে: চারটি বর্ণনা ৭৩ অক্ষরের (বিজোড়), তাই R; P5-এর বর্ণনা ৮০ অক্ষরের, তাই A. P3 নিজের বর্ণনায় “while” পায়, তাই সীমা পর্যন্ত চলে: ~। D-এর সারি কর্ণের প্রতিটি ঘর উল্টায় (~ মানে “গ্রহণ করেনি”, তাই D-তে A), আর শেষের পাঁচ লাইন দেখায়, D প্রতিটি সারি থেকে অন্তত নিজের কর্ণের ঘরে আলাদা। একটি সতর্কতা: এখানে H-এর জায়গায় একটি সীমিত-ধাপের run ব্যবহার করা হয়েছে, যা শুধু এই পাঁচটি জানা program-এ কাজ করে। সব program-এ কাজ করা H যে থাকতে পারে না, সেটাই theorem ৩.১।
1 ⟨1⟩ ⟨2⟩ ⟨3⟩ ⟨4⟩ ⟨5⟩2P1: [A] A A A A3P2: R [R] R R A4P3: A A [~] A A5P4: R R R [R] R6P5: R R R A [A]7D : R A A A R
| কর্ণের ঘর | |
| D-এর ঘর |
- টেবিল। সারি i মানে program Pi, কলাম j মানে input ⟨Pj⟩; সংখ্যাগুলো ওপরের ব্লকের আসল আউটপুট। বন্ধনীর ঘরগুলো কর্ণ: প্রতিটি program নিজের বর্ণনায়।
- প্রথম কর্ণ। P1 সব কিছু গ্রহণ করে, তাই P1(⟨P1⟩) = A. D উল্টো করে: R. ফলে D ≠ P1, পার্থক্য কলাম ১-এ।
- দ্বিতীয় কর্ণ। ⟨P2⟩-এর দৈর্ঘ্য 73, বিজোড়, তাই P2 reject করে। D-এর ঘর A, তাই D ≠ P2.
- তৃতীয় কর্ণ। P3 নিজের বর্ণনায় “while” পায় আর কখনো থামে না। গ্রহণ না করা মানে ATM-এর ভাষায় “না”, তাই D-এর ঘর A. এখানে লক্ষ করুন: আসল H থাকলে সে loop-কে চিরকাল অপেক্ষা না করেই “না” বলত।
- চতুর্থ কর্ণ। P4 সব বর্জন করে, P4(⟨P4⟩) = R, তাই D-এর ঘর A আর D ≠ P4.
- পঞ্চম কর্ণ। ⟨P5⟩-এর লেখায় “False” আছে, তাই P5 গ্রহণ করে; D-এর ঘর R. D পাঁচটি সারির প্রতিটি থেকে আলাদা।
- D নিজে? আসল প্রমাণে তালিকায় সব TM আছে, আর H থাকলে D-ও একটি TM, ধরুন Mk. তাহলে ঘর (k, k)-তে D-এর মান হতে হবে D(⟨D⟩)-এর উল্টো: অসম্ভব। ছোট টেবিলে আমরা D-কে সারি হিসেবে বসাতে পারিনি, কারণ আমাদের “H” আসল decider নয়।
৫ · ATM recognizable, কিন্তু co-recognizable নয়
পর্ব ৪৮-এ প্রমাণ হয়েছে, universal Turing machine U-এর language ঠিক ATM: U ⟨M, w⟩ পেলে M-কে w-তে নকল করে, M গ্রহণ করলে গ্রহণ করে। M loop করলে U-ও loop করে, তাই U একটি recognizer, decider নয়। এখন আমরা জানি, এর চেয়ে ভালো কিছু সম্ভব নয়। প্রশ্ন জাগে, উল্টো দিকটা কেমন? “M w গ্রহণ করে না” কি recognize করা যায়?
একটি language L co-Turing-recognizable (সংক্ষেপে co-recognizable), যদি তার complement L̄ = Σ∗ ∖ L Turing-recognizable হয়।
L decidable ⇔ L আর L̄ দুটিই recognizable.
প্রমাণের রূপরেখা (পূর্ণ প্রমাণ পর্ব ৫০-এ)। (⇒) L-এর decider নিজেই L-এর recognizer, আর তার উত্তর উল্টালে L̄-এর decider. (⇐) ধরি M1 L চেনে, M2 L̄ চেনে। Input w-এ দুটিকে পালা করে এক ধাপ এক ধাপ চালান (dovetailing). w হয় L-এ, নয় L̄-এ, তাই দুটির একটি সসীম ধাপে গ্রহণ করবেই: M1 গ্রহণ করলে accept, M2 গ্রহণ করলে reject. এই যন্ত্র সবসময় থামে আর ঠিক বলে। ∎
ĀTM (ATM-এর complement) Turing-recognizable নয়। অর্থাৎ ATM recognizable, কিন্তু co-recognizable নয়।
প্রমাণ।
- ATM recognizable, কারণ L(U) = ATM. — পর্ব ৪৮
- বিপরীতে ধরি ĀTM-ও recognizable. — অনুমান
- তাহলে theorem ৫.২ অনুযায়ী ATM decidable. — দুই দিক recognizable
- এটি theorem ৩.১-এর বিরোধী, তাই অনুমানটি মিথ্যা। ∎
একটি খুঁটিনাটি: Σ∗-এর যেসব string কোনো বৈধ ⟨M, w⟩ নয়, সেগুলোও ĀTM-এ পড়ে। বৈধতা পরীক্ষা করা decidable, তাই এতে ফলাফল বদলায় না। অনুভূতির দিক থেকে ফলটির মানে: “হ্যাঁ” উত্তরের একটি সসীম সাক্ষী আছে, গ্রহণ পর্যন্ত পুরো computation history, যা দেখে যে কেউ যাচাই করতে পারে। “না” উত্তরের এমন কোনো সাধারণ সসীম সাক্ষী নেই: “আমি এক কোটি ধাপ দেখেছি, এখনো গ্রহণ করেনি” কোনো প্রমাণ নয়। একই যুক্তিতে HALTTM recognizable (M থামলেই গ্রহণ), কিন্তু তার complement, অর্থাৎ “M কখনো থামে না”, recognizable নয়।
Language-এর শ্রেণির মানচিত্র
বাঁ দিকের অঞ্চল recognizable, ডান দিকের co-recognizable; দুটির ছেদ ঠিক decidable language (theorem ৫.২)।
৬ · HALTTM undecidable — ATM থেকে reduction
বাজারঘরের আসল প্রশ্ন ছিল থামা নিয়ে, গ্রহণ নিয়ে নয়। HALTTM-এর জন্য নতুন diagonal প্রমাণ লেখা যায়, কিন্তু তার দরকার নেই। একটি সহজ কৌশল আছে: দেখান যে HALTTM-এর decider হাতে পেলে ATM-এর decider বানানো যেত। ATM-এর decider যেহেতু নেই, HALTTM-এরও নেই।
HALTTM = {⟨M, w⟩ : M একটি TM আর M w-এ থামে} decidable নয়।
প্রমাণ।
- বিপরীতে ধরি, R একটি TM যা HALTTM decide করে। — অনুমান
- R দিয়ে একটি TM S বানাই। S = “input ⟨M, w⟩ পেলে: (১) ⟨M, w⟩-এ R চালান; (২) R reject করলে reject করুন; (৩) R accept করলে M-কে w-তে থামা পর্যন্ত নকল করুন; (৪) M accept করে থামলে accept, reject করে থামলে reject করুন।” — নির্মাণ
- S সবসময় থামে: R decider, আর ধাপ (৩)-এ নকল শুরু হয় শুধু তখন, যখন R নিশ্চিত করেছে M w-এ থামবে। — S decider
- S ঠিক উত্তর দেয়: M w গ্রহণ করলে M থামে, R accept করে, নকলে M গ্রহণ করে, S accept করে। M w reject করলে নকলে M reject করে, S reject করে। M w-এ loop করলে R reject করে, S reject করে। তিন ক্ষেত্রেই S ⟨M, w⟩ গ্রহণ করে ⇔ M w গ্রহণ করে। — তিনটি ক্ষেত্র
- তাহলে S ATM-এর decider, যা theorem ৩.১ অনুযায়ী থাকতে পারে না। তাই R-ও নেই। ∎
নিচের stepper বাজারঘরের তিনটি কাল্পনিক যন্ত্রে S-এর আচরণ দেখায়: Mcode অর্ডার কোড যাচাই করে (“BG-” আর চারটি অঙ্ক হলে accept, নইলে reject; সবসময় থামে), আর Mhash ডান দিকে হেঁটে একটি # খোঁজে, না পেলে চিরকাল হাঁটে।
1S, input ⟨M, w⟩:2 ১. ⟨M, w⟩-এ R চালান3 ২. R reject → reject4 ৩. R accept → M-কে w-তে5 থামা পর্যন্ত নকল6 ৪. M accept → accept7 M reject → reject
| input | |
| R-এর উত্তর | |
| M-এর নকল | |
| S-এর উত্তর |
- S-এর গঠন। S-এর ভেতরে ধরে নেওয়া decider R আর একটি সাধারণ simulator (U-এর মতো)। নকলটি বিপজ্জনক হতে পারত, কারণ M loop করলে নকলও loop করে; R সেই বিপদ আগে থেকে সরিয়ে দেয়।
- প্রথম instance, ধাপ ১। ⟨Mcode, BG-0042⟩। Mcode সব input-এ থামে, তাই R accept করে। S এখনো জানে না M গ্রহণ করবে নাকি বর্জন।
- নকল। R নিশ্চয়তা দিয়েছে, তাই S নিশ্চিন্তে Mcode-কে BG-0042-এ চালায়। কোডটি বৈধ, Mcode accept করে থামে, S accept করে: ঠিক উত্তর, কারণ ⟨Mcode, BG-0042⟩ ∈ ATM.
- দ্বিতীয় instance. ⟨Mcode, XY-9⟩। R আবার accept করে (Mcode থামে)। নকলে Mcode reject করে থামে, তাই S reject করে: ঠিক, কারণ M গ্রহণ করেনি।
- তৃতীয় instance. ⟨Mhash, 7⟩। Input-এ কোনো # নেই, Mhash চিরকাল ডানে হাঁটবে। R reject করে, আর S কোনো নকল ছাড়াই সঙ্গে সঙ্গে reject করে। এটি ঠিক, কারণ loop মানে গ্রহণ নয়। S কখনো আটকে থাকে না।
- সিদ্ধান্ত। সব input-এ S থামে আর ঠিক বলে M w গ্রহণ করে কি না, অর্থাৎ S হতো ATM-এর decider. Theorem ৩.১ বলে এমন যন্ত্র নেই, তাই R-ও নেই: HALTTM undecidable.
দিকের নিয়ম, যা উল্টানো যাবে না: এখানে ATM-কে HALTTM-এ নামানো হয়েছে: “HALTTM-এর decider থাকলে ATM-এর decider থাকত”। সাধারণ রূপ: A-কে B-তে reduce করলে, B decidable হলে A decidable; আর A undecidable হলে B undecidable. জানা কঠিন সমস্যাটি (ATM) সবসময় বাঁয়ে, যেটির কঠোরতা প্রমাণ করতে চান (HALTTM) সেটি ডানে। উল্টো দিকে, অর্থাৎ HALTTM-কে ATM-এ নামিয়ে, HALTTM সম্পর্কে কিছুই প্রমাণ হতো না।
এই প্রমাণটি S-এর ভেতরে R-কে একটি subroutine হিসেবে ব্যবহার করে, আর উত্তর ঠিক করতে নিজেও কিছু কাজ করে (নকল চালায়)। পর্ব ৫২-এ এর একটি কঠোর রূপ আসবে, mapping reduction A ≤m B: একটি computable function f, যাতে প্রতিটি w-এর জন্য w ∈ A ⇔ f(w) ∈ B. এখানে f হতে পারে ⟨M, w⟩ ↦ ⟨M′, w⟩, যেখানে M′ হুবহু M, শুধু M যেখানে reject করত, M′ সেখানে চিরকাল loop করে। তাহলে M′ থামে ⇔ M গ্রহণ করে, তাই ATM ≤m HALTTM. অনুশীলন ১-এ M′-এর 7-tuple নিজে লিখবেন।
৭ · Programmer-এর ভাষায় — halts(f, x) কেন লেখা যায় না
একই যুক্তি Python-এর ভাষায় বললে প্রায় এক পাতার গল্প। ধরুন কেউ দাবি করলেন, তিনি একটি function halts(f, x) লিখেছেন, যা যেকোনো function f আর input x-এ সবসময় থামে আর ঠিক বলে f(x) থামবে কি না। নিচের program-টি একটি চিন্তা-পরীক্ষা: এটি চালানোর জন্য নয়, কারণ ঠিক এমন halts লেখা অসম্ভব, সেটাই দেখানো হচ্ছে।
def halts(f, x): # claimed: always returns, always right
...
def trouble(f):
if halts(f, f): # "f(f) will stop"?
while True: # then loop forever
pass
return "done" # "f(f) runs forever"? then stop at once
trouble(trouble) # does this call stop?trouble(trouble)-এর কথা ভাবুন। halts(trouble, trouble) যদি True দেয়, অর্থাৎ “থামবে”, তবে trouble অসীম loop-এ ঢোকে: থামে না। False দিলে, অর্থাৎ “থামবে না”, trouble সঙ্গে সঙ্গে return করে: থামে। দুই ক্ষেত্রেই halts ভুল। এটি অংশ ৩-এর D, শুধু “গ্রহণ”-এর বদলে “থামা” আর ⟨M⟩-এর বদলে Python function object. এই ছোট রূপটি ১৯৬৫ সালে Christopher Strachey-র The Computer Journal-এ লেখা একটি চিঠি (“An impossible program”) থেকে programmer-দের মধ্যে পরিচিত হয় বলে সাধারণত উল্লেখ করা হয়।
যুক্তিটি যেকোনো প্রস্তাবিত checker-এর ক্ষেত্রে হাতে-কলমে দেখা যায়: প্রতিটি checker-এর জন্য তার নিজের trouble program বানান, আর দেখুন checker সেখানে ভুল করে। নিচের JavaScript ব্লকে পাঁচটি checker আছে; trouble program-কে এখানে T বলা হয়েছে, আর প্রতিটি run-এ ১০,০০০ ধাপের সীমা।
// THOUGHT EXPERIMENT: every claimed checker is wrong on its own T
const CAP = 10000;
function run(prog, input) { // one next() = one step
const it = prog(input);
for (let n = 0; n < CAP; n++) if (it.next().done) return `halts (${n} steps)`;
return `still running at ${CAP}`;
}
function makeT(willHalt) { // the contrarian program T
return function* T(p) {
if (willHalt(p, p)) { while (true) yield; } // "halts"? then loop
}; // "loops"? then stop at once
}
const checkers = {
"always yes": (p, x) => true,
"always no": (p, x) => false,
"no while in source": (p, x) => !String(p).includes("while"),
"even source length": (p, x) => String(p).length % 2 === 0,
"run up to the cap": (p, x) => run(p, x).startsWith("halts"),
};
for (const [name, willHalt] of Object.entries(checkers)) {
const T = makeT(willHalt);
try {
const says = willHalt(T, T) ? "halts" : "loops";
console.log(`${name}: says T(T) ${says}; really ${run(T, T)}`);
} catch (e) {
console.log(`${name}: never answered (${e.name})`);
}
}আসল আউটপুট (ব্রাউজারের JavaScript):
always yes: says T(T) halts; really still running at 10000
always no: says T(T) loops; really halts (0 steps)
no while in source: says T(T) loops; really halts (0 steps)
even source length: says T(T) loops; really halts (0 steps)
run up to the cap: never answered (RangeError)
প্রথম চারটি checker নিজের T-তে উল্টো ভবিষ্যদ্বাণী করে। “always yes” বলে থামবে, অথচ T ১০,০০০ ধাপ পরেও চলছে (আর চিরকাল চলবে, কারণ while (true) থেকে বের হওয়ার পথ নেই)। বাকি তিনটি বলে থামবে না, অথচ T সঙ্গে সঙ্গে থামে। পঞ্চম checker সবচেয়ে শিক্ষণীয়: সে T(T) চালিয়ে দেখতে চায়, কিন্তু T প্রথম ধাপেই আবার checker-কে ডাকে, যে আবার T চালায়… JavaScript-এর call stack ফুরিয়ে RangeError হয়। অর্থাৎ এই checker নিজেই এই input-এ উত্তর দেয় না, তাই সে decider নয়। চিন্তা-পরীক্ষার কথাটি মনে রাখুন: পাঁচটি checker ভুল দেখানো প্রমাণ নয়; প্রমাণ হলো অংশ ৩-এর যুক্তি, যা প্রতিটি সম্ভাব্য checker-এ খাটে।
“সীমা দিয়ে চালিয়ে দেখি” কেন যথেষ্ট নয়
সবচেয়ে স্বাভাবিক প্রস্তাব: program-টি N ধাপ চালান; থামলে “থামে”, না থামলে “থামে না”। প্রথম অর্ধেক ঠিক, দ্বিতীয় অর্ধেক অনুমান। নিচের ব্লক N = 1000 সীমায় কয়েকটি program চালায়। goldbach_search 4 থেকে শুরু করে প্রতিটি জোড় সংখ্যা দুটি মৌলিক সংখ্যার যোগফল কি না দেখে, আর এমন একটি না পেলেই থামে।
def run(prog, x, cap): # one yield = one step
n = 0
for _ in prog(x):
n += 1
if n > cap: return "unknown", cap # step cap: no verdict
return "halts", n
def countdown(n):
while n > 0: n -= 1; yield
def forever(n):
while True: yield
def late(n): # halts after exactly n steps
for _ in range(n): yield
def collatz(n):
while n != 1: n = n // 2 if n % 2 == 0 else 3 * n + 1; yield
def goldbach_search(_): # halts iff Goldbach is false
prime = lambda k: k > 1 and all(k % d for d in range(2, int(k ** .5) + 1))
n = 4
while any(prime(p) and prime(n - p) for p in range(2, n // 2 + 1)):
n += 2; yield
CAP = 1000
for f, x in [(countdown, 5), (forever, 0), (late, 1000), (late, 1001),
(collatz, 27), (goldbach_search, None)]:
v, n = run(f, x, CAP)
print(f"{f.__name__:16}{str(x):6}{v:8}{n}")
res = [run(collatz, k, CAP) for k in range(1, 10_001)]
worst = max(range(len(res)), key=lambda i: res[i][1])
print("collatz 1..10000:", sum(v == "halts" for v, _ in res), "halt;",
"max", res[worst][1], "steps at n =", worst + 1)আসল আউটপুট (ব্রাউজারের Python):
countdown 5 halts 5
forever 0 unknown 1000
late 1000 halts 1000
late 1001 unknown 1000
collatz 27 halts 111
goldbach_search None unknown 1000
collatz 1..10000: 10000 halt; max 261 steps at n = 6171
“unknown” তিন রকম program থেকে এসেছে, আর সীমা দেখে তাদের আলাদা করা যায় না। forever সত্যিই কখনো থামে না। late(1001) থামে, ঠিক এক ধাপ পরে: “unknown”-কে “থামে না” পড়লে এখানে ভুল হতো, আর N যত বড়ই নিন, late(N + 1) সেই N-কে হারায়। goldbach_search থামবে কি না, কেউ জানে না: এটি থামে ঠিক তখন, যখন Goldbach-এর অনুমান মিথ্যা, আর সেই অনুমান আজও খোলা প্রশ্ন। Collatz-এর loop প্রথম ১০,০০০টি input-এর প্রতিটিতে থেমেছে (সবচেয়ে বেশি ২৬১ ধাপ, n = 6171-এ), কিন্তু প্রতিটি ধনাত্মক n-এ থামবে কি না, সেটিও অপ্রমাণিত অনুমান; কম্পিউটারে খুব বড় সীমা পর্যন্ত যাচাই হয়েছে, প্রমাণ হয়নি। HALTTM-এর একটি decider থাকলে এমন অনেক খোলা প্রশ্নের উত্তর একটি প্রশ্নেই পাওয়া যেত; এটি নিজে কোনো প্রমাণ নয়, তবে undecidability কেন বিশ্বাসযোগ্য, তার একটি অনুভূতি দেয়।
৮ · এর মানে কী নয় — আর ইতিহাস
Halting problem-এর ফলাফল প্রায়ই অতিরঞ্জিত হয়। Theorem-টি ঠিক একটি কথা বলে: এমন কোনো একক algorithm নেই, যা সব program আর সব input-এ থেমে ঠিক উত্তর দেয়। এর বাইরে অনেক কিছুই সম্ভব।
- নির্দিষ্ট program নিয়ে প্রমাণ করা যায়।
countdownথামে, কারণ প্রতিটি ধাপে n কমে আর n কখনো ঋণাত্মক হয় না। এমন “প্রতি ধাপে কমে এমন মাপ” দেখিয়ে অসংখ্য বাস্তব program-এর থামা প্রমাণ করা যায়, হাতে বা tool দিয়ে। Undecidability শুধু বলে, একটি যান্ত্রিক পদ্ধতি সব program-এ এটি পারবে না। - দুর্বল মডেলে প্রশ্নটি decidable. DFA সবসময় থামে, আর DFA বা CFG-এর acceptance decidable (পর্ব ২০, পর্ব ৩৭)। যে program-এর স্মৃতি একটি নির্দিষ্ট সীমায় বাঁধা, তার অবস্থাও সসীম সংখ্যক; pigeonhole অনুযায়ী না থামলে কোনো অবস্থা ফিরে আসবেই, তাই নীতিগতভাবে থামা নির্ণয় করা যায় (সময় অবশ্য অবস্থার সংখ্যার মতো বিশাল হতে পারে)।
- Timeout অন্য প্রশ্নের উত্তর দেয়। “N ধাপের মধ্যে থামে?” decidable, আর বাস্তবে খুব দরকারি: server, test runner আর বাজারঘরের checkout script সবই সময় বা ধাপের বাজেট রাখে। কিন্তু এটি প্রশ্ন বদলে দেয়, সমাধান করে না। কোনো computable নিয়ম দিয়ে প্রতিটি program-এর জন্য “যথেষ্ট বড় N” বের করা যায় না; গেলে halting decidable হতো (পর্ব ৫৫-এর Busy Beaver এর চরম রূপ)।
- বাস্তব tool আনুমানিক কাজ করে। Static analysis tool, type checker বা termination checker তিনটি উত্তরের একটি দেয়: “নিশ্চিত থামে”, “নিশ্চিত সমস্যা”, অথবা সতর্কতা/“জানি না”। তারা হয় কিছু ভুল সতর্কতা দেয়, নয়তো কিছু সমস্যা ধরতে পারে না; দুটোই শূন্য করা অসম্ভব (পর্ব ৫৩-এর Rice-এর theorem এর সাধারণ রূপ)। Software testing কোর্সের পর্ব ০৬-এ এমন tool-এর ব্যবহারিক দিক আছে।
- কম্পিউটারের দুর্বলতা নয়। ফলটি যন্ত্রের গতি বা মেমরি নিয়ে নয়। নিয়ম মেনে চলা মানুষ, ভবিষ্যতের কম্পিউটার, quantum কম্পিউটার, সবার জন্য একই সীমা, কারণ সবাই Turing machine দিয়ে নকল করা যায় (পর্ব ৪৭)।
Alan Turing-এর ১৯৩৬ সালের প্রবন্ধ “On Computable Numbers” আজকের ভাষার halting problem ঠিক এই রূপে বলেনি। Turing দেখান, কোনো যন্ত্র নির্ণয় করতে পারে না যে একটি প্রদত্ত যন্ত্র অসীম সংখ্যক অঙ্ক ছাপতে থাকবে কি না (তাঁর ভাষায় “circle-free” কি না), আর একটি যন্ত্র কখনো একটি নির্দিষ্ট চিহ্ন ছাপবে কি না; এখান থেকে তিনি Entscheidungsproblem-এর নেতিবাচক উত্তর দেন। প্রায় একই সময়ে Alonzo Church λ-calculus দিয়ে আলাদাভাবে একই উত্তর দেন (এই ইতিহাসের বিস্তারিত পর্ব ৪৭-এ)। “Halting problem” নামটি পরে আসে; সাধারণত Martin Davis-কে এর কৃতিত্ব দেওয়া হয়, যাঁর ১৯৫৮ সালের বই Computability and Unsolvability-তে শব্দটি আছে, আর তিনি নিজে বলেছেন ১৯৫০-এর দশকের শুরুতে বক্তৃতায় এটি ব্যবহার করেছিলেন। উৎসভেদে খুঁটিনাটি একটু আলাদা। পাঠ্যবইয়ের ATM-রূপের প্রমাণ, যা এখানে দেখলেন, Sipser-এর Introduction to the Theory of Computation-এর উপস্থাপনা অনুসরণ করে।
আরও গভীরে: HALTTM শুধু undecidable নয়, recognizable language-গুলোর মধ্যে “সবচেয়ে কঠিন”: প্রতিটি recognizable language A-এর জন্য A ≤m HALTTM, তাই একে r.e.-complete বলা হয়। এর চেয়ে কম কিন্তু শূন্যের চেয়ে বেশি কঠিন recognizable set আছে কি না, এই Post-এর প্রশ্ন (১৯৪৪) Friedberg আর Muchnik ১৯৫০-এর দশকের মাঝামাঝি আলাদাভাবে “হ্যাঁ” উত্তর দিয়ে মেটান। আর যদি HALTTM-এর উত্তর জাদুকরীভাবে জানা থাকে (একটি oracle), তবু সেই oracle-সহ যন্ত্রগুলোর নিজস্ব halting problem একই diagonal যুক্তিতে undecidable থেকে যায়; এভাবে undecidability-র এক অসীম সিঁড়ি (arithmetical hierarchy) পাওয়া যায়, যার প্রথম ধাপ ATM.
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- ATM undecidable, প্রমাণ করুন। Decider H ধরে D বানান, যা ⟨M⟩-এ H(⟨M, ⟨M⟩⟩)-এর উল্টো করে; D(⟨D⟩)-এ স্ববিরোধ।
- ATM কি recognizable? ĀTM? প্রথমটি হ্যাঁ (universal TM); দ্বিতীয়টি না, কারণ দুটিই recognizable হলে ATM decidable হতো।
- HALTTM undecidable দেখাতে কোন দিকে reduce করবেন? ATM-কে HALTTM-এ: HALT-এর decider থেকে ATM-এর decider.
- Timeout দিয়ে কেন halting problem মেটে না? যেকোনো সীমা N-এর পরে থামা program আছে; “N ধাপে থামে?” আলাদা, decidable প্রশ্ন।
- Undecidable মানে কি কোনো program-এর থামা প্রমাণ করা যায় না? না; নির্দিষ্ট program-এ যায়, শুধু সব program-এ কাজ করা একক algorithm নেই।
৯ · AI-এর যুগে halting problem আর undecidability
এই বিষয়ে AI assistant-এর ভুল খুব চেনা। প্রমাণে: D-কে H-এর বদলে U দিয়ে বানানো (তখন D loop করতে পারে, স্ববিরোধ হয় না), “H loop করলে” ধরনের তৃতীয় ক্ষেত্র ঢোকানো (H decider, loop করে না), reduction-এর দিক উল্টো লেখা, বা “recognizable” আর “decidable” গুলিয়ে ফেলা। ব্যবহারিক দিকে: “আমার এই loop detector সব অসীম loop ধরে” ধরনের দাবি। নিচের ব্লকে এমন একটি খসড়া (AI-এর উত্তরের ধাঁচে বানানো উদাহরণ) যাচাই করা হয়েছে। Program এখানে একটি শুরুর মান আর একটি step function; None মানে থেমেছে।
# A program = start value + a step function (None means "halted")
def countdown(x): return None if x == 0 else x - 1
def cycle(x): return (x + 1) % 3 # 0, 1, 2, 0, ... forever
def climb(x): return x + 1 # 0, 1, 2, 3, ... forever
def collatz(x): return None if x == 1 else (x // 2 if x % 2 == 0 else 3 * x + 1)
def ai_check(step, x, cap=10_000): # AI draft
seen = set()
for _ in range(cap):
if x is None: return "halts"
if x in seen: return "loops"
seen.add(x); x = step(x)
return "halts" # AI: "no state repeated, so it must finish"
def fixed_check(step, x, cap=10_000): # honest version
seen = set()
for _ in range(cap):
if x is None: return "halts"
if x in seen: return "loops" # pigeonhole: a real cycle
seen.add(x); x = step(x)
return "unknown" # cap hit: no verdict
truth = {"countdown": "halts", "cycle": "loops", "climb": "loops",
"collatz": "halts"}
for f, x in [(countdown, 7), (cycle, 0), (climb, 0), (collatz, 27)]:
a, b = ai_check(f, x), fixed_check(f, x)
mark = "" if a == truth[f.__name__] else " <-- WRONG"
print(f"{f.__name__:10} truth={truth[f.__name__]:6} ai={a:6} fixed={b}{mark}")আসল আউটপুট (ব্রাউজারের Python):
countdown truth=halts ai=halts fixed=halts
cycle truth=loops ai=loops fixed=loops
climb truth=loops ai=halts fixed=unknown <-- WRONG
collatz truth=halts ai=halts fixed=halts
খসড়াটির অর্ধেক ঠিক: কোনো অবস্থা ফিরে এলে program সত্যিই চিরকাল ঘুরবে (একই অবস্থা থেকে একই ভবিষ্যৎ), তাই cycle-এ “loops” ঠিক। ভুল শেষ লাইনে: “কোনো অবস্থা ফেরেনি, তাই থামবে” শুধু সীমিত স্মৃতির program-এ খাটে। climb-এর অবস্থা অসীম, কখনো ফেরে না, কখনো থামেও না; খসড়া বলে “halts”. সংশোধিত রূপ সীমায় পৌঁছালে সৎভাবে “unknown” বলে। তিনটি উত্তর (থামে, থামে না, জানি না) দেওয়া checker বৈধ আর দরকারি; শুধু “জানি না” কখনো পুরোপুরি বাদ দেওয়া যায় না।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| D বানানো হয়েছে U (simulator) দিয়ে, H (decider) দিয়ে নয় | দেখুন D সবসময় থামে কি না; না থামলে D(⟨D⟩) loop করতে পারে, কোনো স্ববিরোধ নেই |
| “ATM ≤ HALTTM, তাই ATM undecidable” | দিক মিলিয়ে নিন: reduction শুধু ডানের সমস্যাকে কঠিন প্রমাণ করে; ATM-এর undecidability আসে diagonal থেকে |
| “ATM recognizable নয়” বা “ĀTM recognizable” | U-এর কথা মনে করুন; আর theorem ৫.২ দিয়ে দুই দিক মিলিয়ে দেখুন |
| “যথেষ্ট বড় timeout দিলে halting problem মেটে” বা “এই detector সব loop ধরে” | late(N + 1) বা climb-এর মতো পাল্টা-উদাহরণ নিজে চালিয়ে দেখুন |
| বানানো ইতিহাস (“Turing ১৯৩৬ সালে ‘halting problem’ নামে প্রমাণ করেন”) | Sipser বা Hopcroft–Motwani–Ullman-এ মিলিয়ে নিন; নাম আর রূপ পরে এসেছে |
AI-কে কাজে লাগানোর ভালো উপায়: প্রমাণের প্রতিটি ধাপের যুক্তি আলাদা করে চাওয়া, প্রতিটি যন্ত্র সবসময় থামে কি না স্পষ্ট করে জিজ্ঞেস করা, আর “পরীক্ষার কোড” চাওয়া যা আপনি নিজে চালাবেন।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Turing ১৯৩৬ সালে আসলে কী প্রমাণ করেছিলেন, আর আজকের পাঠ্যবই কেন ATM আর HALTTM-রূপে প্রমাণটি দেখায়?
Turing-এর প্রবন্ধে যন্ত্রগুলো input নিয়ে হ্যাঁ/না বলত না; তারা একটি বাস্তব সংখ্যার দশমিক (আসলে binary) অঙ্ক একটার পর একটা ছাপত। একটি যন্ত্র “ভালো” ছিল, যদি সে অসীম সংখ্যক অঙ্ক ছাপতে থাকে; কোনো এক জায়গায় আটকে গেলে সেটি তাঁর হিসাবে খারাপ। এখানে “থামা” বরং সমস্যা, সাফল্য নয়। Turing দেখান, কোনো যন্ত্র সব যন্ত্রের বর্ণনা দেখে বলতে পারে না কোনটি ভালো, আর এর একটি ধারাবাহিকতায় দেখান, একটি যন্ত্র কখনো একটি নির্দিষ্ট চিহ্ন ছাপবে কি না, তা-ও নির্ণয় করা যায় না। শেষটিকে logic-এর সূত্রে রূপ দিয়ে তিনি Hilbert-এর Entscheidungsproblem-এর “না” উত্তর পান। প্রমাণে diagonal ধারণা ছিল, কিন্তু আজকের সরল D-এর রূপে নয়।
পরে, যখন computability একটি স্বতন্ত্র বিষয় হয়ে উঠল, input-ভিত্তিক decision problem-এর ভাষা স্বাভাবিক হয়ে গেল: একটি যন্ত্র, একটি input, একটি হ্যাঁ/না প্রশ্ন। এই ভাষায় সবচেয়ে সরল undecidable প্রশ্ন হলো “থামবে কি?”, যা Martin Davis সহ অনেকের লেখায় halting problem নামে স্থির হয়। Sipser-এর বই আরও এক ধাপ এগিয়ে ATM-কে মূল উদাহরণ বানায়, কারণ তার diagonal প্রমাণ সবচেয়ে পরিচ্ছন্ন: D-কে শুধু “উত্তর উল্টাতে” হয়, loop বানাতে হয় না। তারপর HALTTM আসে reduction দিয়ে, যা ছাত্রদের পরের সব প্রমাণের ছাঁচ শেখায়।
এখান থেকে একটি শিক্ষা: একই গাণিতিক সত্য বিভিন্ন রূপে লেখা যায়, আর পাঠ্যবইয়ের রূপটি প্রায়ই মূল প্রবন্ধের রূপ নয়। ইতিহাস লিখতে গেলে তাই “Turing ১৯৩৬ সালে halting problem প্রমাণ করেন” বলার চেয়ে “Turing ১৯৩৬ সালে যে ফল দেন, তার আধুনিক রূপ halting problem” বলা বেশি সঠিক।
মূল উপলব্ধি: Turing-এর মূল ফল ছিল অসীম ছাপার যন্ত্র নিয়ে আর Entscheidungsproblem-এর উত্তর; আজকের ATM/HALTTM-রূপ একই সত্যের পরিষ্কার, শেখানোর উপযোগী পুনর্লিখন।
প্র ০২একটি laptop-এর মেমরি সসীম। তাহলে তার জন্য halting problem কি আসলে decidable? যদি হয়, তত্ত্বটি অবাস্তব নয় কি?
কঠোর অর্থে হ্যাঁ। একটি যন্ত্রের মোট মেমরি (RAM, disk, register) যদি B bit হয়, তার সম্ভাব্য অবস্থা বড়জোর 2Bটি। একটি deterministic program প্রতি ধাপে এক অবস্থা থেকে আরেক অবস্থায় যায়। 2B ধাপের পরেও না থামলে pigeonhole অনুযায়ী কোনো অবস্থা দুবার এসেছে, আর তখন থেকে program একই চক্রে চিরকাল ঘুরবে। তাই “2B ধাপ চালিয়ে দেখুন” একটি সঠিক decider, অন্তত নীতিগতভাবে। অংশ ৯-এর fixed_check ঠিক এই ধারণার ছোট রূপ।
সমস্যা হলো সংখ্যাটির আকার। কয়েক গিগাবাইট মেমরি মানে B কয়েক হাজার কোটি, আর 2B এমন একটি সংখ্যা যার অঙ্কই কয়েক হাজার কোটি। মহাবিশ্বের বয়সে যত ন্যানোসেকেন্ড, তা এর তুলনায় শূন্যের কাছাকাছি। তাছাড়া একটি program বাইরের জগৎ থেকে input নেয়, network-এ কথা বলে, disk বদলায়; “সম্পূর্ণ অবস্থা” ধরে রাখাও অবাস্তব। তাই সসীম-মেমরির decidability একটি গাণিতিক কৌতূহল, ব্যবহারিক কৌশল নয়।
তত্ত্ব কেন অসীম tape ধরে? কারণ algorithm-এর নকশা মেমরির একটি নির্দিষ্ট পরিমাণের ওপর নির্ভর করে না। একটি sorting program-কে বেশি মেমরি দিলে সে বড় তালিকা সাজায়; তার নিয়ম বদলায় না। “সব input-এ কাজ করে এমন পদ্ধতি” নিয়ে প্রশ্ন করতে হলে মেমরি “যত দরকার তত” ধরতেই হয়। সেই মডেলে halting undecidable, আর বাস্তবে এর প্রতিফলন হলো: কোনো সাধারণ পদ্ধতি বাস্তব সময়ে সব program বিশ্লেষণ করতে পারে না। Complexity theory (মডিউল ১০–১১) এই “বাস্তব সময়” প্রশ্নটিকেই নিখুঁত করে।
মূল উপলব্ধি: সসীম মেমরিতে halting নীতিগতভাবে decidable, কিন্তু exponential-এর চেয়েও ভয়ংকর খরচে; অসীম-মেমরির মডেল সেই বাস্তবতাকেই পরিষ্কার ভাষায় ধরে।
প্র ০৩HALTTM-এর একটি decider থাকলে গণিতের কোন কোন খোলা প্রশ্ন মিটে যেত? এই পর্যবেক্ষণ কি undecidability-র প্রমাণ?
অনেক বিখ্যাত অনুমানের একটি বিশেষ গঠন আছে: “সব n-এর জন্য একটি যাচাইযোগ্য ধর্ম সত্য”। Goldbach-এর অনুমান এমন: প্রতিটি জোড় n ≥ 4 দুটি মৌলিক সংখ্যার যোগফল, আর একটি নির্দিষ্ট n-এর জন্য এটি সসীম হিসাবে যাচাই করা যায়। তাহলে একটি program লেখা যায় যা n = 4, 6, 8, … একে একে দেখে আর প্রথম ব্যতিক্রমে থামে, ঠিক অংশ ৭-এর goldbach_search. Program থামে ⇔ অনুমান মিথ্যা। Halting decider থাকলে একটি প্রশ্নেই Goldbach মিটে যেত। একই কৌশল খাটে আরও অনেক অনুমানে, যাদের এমন “সব n-এ সসীম যাচাই” রূপ আছে; Riemann hypothesis-এরও এমন একটি সমতুল্য রূপ আছে বলে জানা যায়।
Collatz একটু আলাদা। একটি নির্দিষ্ট n-এর ক্রম 1-এ পৌঁছায় কি না, তা নিজেই একটি halting প্রশ্ন; কিন্তু “সব n-এ পৌঁছায়” রূপটি এক ধাপ জটিল, কারণ কোনো n-এর ক্রম অসীমে ছুটে গেলে সেটি সসীম সময়ে ধরা পড়ে না। তাই Collatz-এর জন্য সাধারণ halting decider-এর সঙ্গে আরেকটু চালাকি লাগত। এটি দেখায়, “খোলা প্রশ্ন” সবগুলো একই কঠিনতার স্তরে নয়।
এই পর্যবেক্ষণ প্রমাণ নয়। কোনো অনুমান খোলা থাকা মানে মানুষ এখনো প্রমাণ পায়নি, অসম্ভব নয়; Fermat-এর শেষ উপপাদ্য তিনশো বছর পর প্রমাণ হয়েছে। প্রমাণ আসে শুধু diagonal যুক্তি থেকে। তবে পর্যবেক্ষণটি একটি অনুভূতি দেয়: একটি সাধারণ halting decider হতো সব গাণিতিক অনুসন্ধানের এক যন্ত্র, আর এমন যন্ত্র “অবিশ্বাস্য রকমের ভালো” শোনায়। একই ভাবনা Busy Beaver function-এ চরম রূপ পায় (পর্ব ৫৫): ছোট যন্ত্রের সর্বোচ্চ ধাপ জানলেই থামা নির্ণয় করা যেত, আর ৫ state-এর যন্ত্রের মান প্রমাণ করতেই বহু মানুষের যৌথ কাজ লেগেছে, যা ২০২৪ সালে শেষ হয় বলে জানানো হয়েছে।
মূল উপলব্ধি: Halting decider অনেক খোলা প্রশ্ন এক ধাক্কায় মিটিয়ে দিত; এটি undecidability-কে বিশ্বাসযোগ্য করে, কিন্তু প্রমাণ আসে শুধু diagonalization থেকে।
প্র ০৪Halting problem undecidable হলে বাজারঘরের দল checkout script-এর সমস্যা বাস্তবে কীভাবে সামলাবে? “প্রশ্ন বদলানো” আর “আনুমানিক উত্তর” কৌশলগুলোর দাম কী?
প্রথম কৌশল প্রশ্ন বদলানো। দল ঠিক করতে পারে, প্রতিটি script সর্বোচ্চ ধরুন দশ হাজার ধাপ বা পঞ্চাশ মিলিসেকেন্ড চলবে; সীমা পেরোলে script থামিয়ে দিয়ে ছাড় ছাড়াই checkout হবে। এখন প্রশ্নটি “script কি থামে?” নয়, “script কি বাজেটের মধ্যে থামে?”, যা decidable আর সহজ। দাম: কিছু বৈধ কিন্তু ধীর script বাদ পড়বে, আর বিক্রেতাকে সীমাটি জানাতে হবে। বাস্তবের অনেক ব্যবস্থা, যেমন server-এর request timeout বা ব্যবহারকারীর দেওয়া code চালানোর sandbox, এভাবেই কাজ করে।
দ্বিতীয় কৌশল ভাষা দুর্বল করা। Script-এর ভাষায় যদি শুধু সসীম তালিকার ওপর loop থাকে (অর্ডারের প্রতিটি পণ্যের জন্য একবার), আর কোনো while বা recursion না থাকে, তবে প্রতিটি script নিশ্চিত থামবে, কোনো বিশ্লেষণ ছাড়াই। পর্ব ৪৭-এ দেখেছেন, Turing completeness ইচ্ছা করে এড়ানোর এটিই কারণ। দাম: কিছু নিয়ম লেখা কঠিন বা অসম্ভব হবে।
তৃতীয় কৌশল আনুমানিক বিশ্লেষণ। একটি static checker script পড়ে তিনটির একটি বলবে: “নিশ্চিত থামে” (যেমন সব loop-এর একটি কমতে থাকা counter আছে), “নিশ্চিত সমস্যা”, বা “জানি না, মানুষ দেখুক”। একে বলা হয় sound বিশ্লেষণ, যদি “নিশ্চিত থামে” বললে সেটি সবসময় সত্য হয়; তাহলে কিছু ভালো script-ও “জানি না” পাবে। উল্টোভাবে, কোনো ভালো script বাদ না দিতে চাইলে কিছু খারাপ script পার পাবে। Undecidability বলে, দুই দিকের ভুলই একসঙ্গে শূন্য করা যায় না।
সবশেষে পরীক্ষা: fuzz testing আর property-based testing দিয়ে অনেক এলোমেলো অর্ডারে script চালানো (Software testing কোর্সের পর্ব ৬০)। এটি ভুল খুঁজে পায়, কিন্তু ভুল না থাকার প্রমাণ দেয় না।
মূল উপলব্ধি: Undecidable প্রশ্নের মুখে প্রকৌশলীরা প্রশ্ন বদলান, ভাষা দুর্বল করেন, বা “জানি না”-সহ আনুমানিক উত্তর মেনে নেন; প্রতিটি কৌশলের দাম কিছু ভালো ক্ষেত্র হারানো।
প্র ০৫মিথ্যাবাদীর হেঁয়ালি (“এই বাক্যটি মিথ্যা”), Russell-এর হেঁয়ালি আর D(⟨D⟩)-এর মিল কোথায়? হেঁয়ালি আর contradiction-এর প্রমাণের পার্থক্য কী?
তিনটিতেই একই গঠন: কিছু একটা নিজের সম্পর্কে কথা বলে, আর বলে “আমি যা, তার উল্টো”। “এই বাক্যটি মিথ্যা” সত্য হলে মিথ্যা, মিথ্যা হলে সত্য। Russell-এর set R = {x : x ∉ x} (যে set নিজের সদস্য নয়, তাদের set): R ∈ R ⇔ R ∉ R. আর D ⟨D⟩ গ্রহণ করে ⇔ D ⟨D⟩ গ্রহণ করে না। একটি পরিচিত লোককথার রূপ: এক গ্রামের নাপিত শুধু তাঁদেরই দাড়ি কামান, যাঁরা নিজের দাড়ি নিজে কামান না। নাপিত নিজের দাড়ি কামান কি না? দুই উত্তরই স্ববিরোধী।
পার্থক্য হলো আমরা স্ববিরোধ থেকে কী সিদ্ধান্ত নিই। হেঁয়ালিতে স্ববিরোধ আমাদের ভাষা বা তত্ত্বের একটি ত্রুটি দেখায়। Russell-এর হেঁয়ালি তৎকালীন সরল set theory ভেঙে দেয়; পরে axiom বদলে “যেকোনো শর্ত দিয়ে set বানানো যায়” নিয়মটি বাদ দেওয়া হয়। নাপিতের গল্পের সমাধান সহজ: এমন নাপিত নেই। Contradiction-এর প্রমাণে ঠিক এই দ্বিতীয় পথটি নেওয়া হয়: স্ববিরোধ দেখায় যে একটি অনুমান, এখানে “H আছে”, মিথ্যা। D(⟨D⟩) কোনো হেঁয়ালি নয়, কারণ D-এর অস্তিত্ব শর্তসাপেক্ষ; H না থাকলে D-ও নেই, আর কোনো স্ববিরোধও নেই।
Gödel-এর incompleteness theorem (১৯৩১) একই কৌশলের আরেকটি রূপ: একটি গাণিতিক বাক্য, যা পরোক্ষভাবে বলে “আমাকে এই তত্ত্বে প্রমাণ করা যায় না”। সেখানে সিদ্ধান্ত হয়, তত্ত্বটি সামঞ্জস্যপূর্ণ হলে সত্য অথচ অপ্রমাণযোগ্য বাক্য আছে। একটি প্রশ্ন থেকে যায়: একটি যন্ত্র কীভাবে নিজের বর্ণনা “জানে”? এখানে আমরা ⟨D⟩ বাইরে থেকে input দিয়েছি। পর্ব ৫৬-এর recursion theorem দেখাবে, যন্ত্র নিজেই নিজের বর্ণনা বানাতে পারে, যেমন একটি program নিজের source code ছাপতে পারে।
মূল উপলব্ধি: Self-reference আর “উল্টো করা” মিলে স্ববিরোধ তৈরি করে; হেঁয়ালিতে তা ভাষার ত্রুটি দেখায়, আর diagonalization-এ তা একটি অনুমানকে মিথ্যা প্রমাণ করে।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। halts_within.py আর loop_detector.py ব্লক বদলে নিজের ধারণাও চালিয়ে দেখতে পারেন।
-
নির্মাণ: M = (Q, Σ, Γ, δ, q0, qaccept, qreject) একটি Turing machine. এমন একটি M′ = (Q′, Σ, Γ, δ′, q0, qaccept, q′reject)-এর 7-tuple লিখুন, যাতে প্রতিটি w-এর জন্য M′ w-এ থামে ⇔ M w গ্রহণ করে। এটি দিয়ে ATM ≤m HALTTM-এর function f লিখুন।
দুটি নতুন state যোগ করুন: qloop আর একটি নতুন, কখনো-না-পৌঁছানো q′reject; Q′ = Q ∪ {qloop, q′reject}। δ′ গঠন:
- δ(q, a) = (r, b, D) আর r ≠ qreject হলে δ′(q, a) = δ(q, a).
- δ(q, a) = (qreject, b, D) হলে δ′(q, a) = (qloop, b, D). যেসব (q, a)-র নিয়ম নেই (implicit reject), সেখানেও (qloop, a, R).
- প্রতিটি a ∈ Γ-এর জন্য δ′(qloop, a) = (qloop, a, R): চিরকাল ডানে হাঁটা।
M w গ্রহণ করলে M′ একই পথে qaccept-এ থামে। M reject করলে M′ qloop-এ ঢুকে আর থামে না। M loop করলে M′-ও একই পথে loop করে। তাই M′ থামে ⇔ M গ্রহণ করে। f(⟨M, w⟩) = ⟨M′, w⟩ (অবৈধ string-কে একটি নির্দিষ্ট “কখনো না থামা” instance-এ পাঠান), যা একটি সরল, computable রূপান্তর। Scratch-এ একটি ছোট M (“ab” থাকলে accept, “bb” দিয়ে শুরু হলে loop, বাকিতে reject) নিয়ে {a, b}-এর দৈর্ঘ্য ০–৬-এর ১২৭টি string-এ শর্তটি মিলেছে।
-
প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “ADFA = {⟨B, w⟩ : DFA B w গ্রহণ করে} decidable. প্রতিটি DFA-কে একটি TM হিসেবে লেখা যায়, তাই ADFA-কে ATM-এ reduce করা যায়। অতএব ATM-ও decidable. ∎” কোথায় ভুল?
Reduction-এর দিক উল্টো পড়া হয়েছে। ADFA-কে ATM-এ reduce করা মানে: “ATM-এর decider থাকলে ADFA-এর decider থাকত”। নিয়ম অনুযায়ী এর থেকে আসে, ATM decidable হলে ADFA decidable, অথবা ADFA undecidable হলে ATM undecidable. ADFA decidable হওয়া থেকে ডানের সমস্যা ATM সম্পর্কে কিছুই আসে না। Reduction সহজতা বাঁ দিকে বয়ে আনে, কঠোরতা ডান দিকে। সঠিক তথ্য: ADFA decidable (পর্ব ২০) আর ATM undecidable (theorem ৩.১), তাই সিদ্ধান্তটি মিথ্যাও।
-
Trace: চারটি যন্ত্রের জন্য ধরে নেওয়া decider H-এর টেবিল দেওয়া আছে; ঘর (i, j) = H(⟨Mi, ⟨Mj⟩⟩)। সারি M1: acc, rej, acc, acc. সারি M2: rej, rej, acc, rej. সারি M3: acc, acc, rej, rej. সারি M4: rej, acc, acc, acc. (ক) D-এর সারি লিখুন। (খ) D কোন কোন কলামে M3 থেকে আলাদা? (গ) D কি M2 হতে পারে?
(ক) কর্ণ: acc, rej, rej, acc. উল্টে D-এর সারি: rej, acc, acc, rej. (খ) M3-এর সারি acc, acc, rej, rej; D-এর সঙ্গে তুলনায় কলাম ১ (acc বনাম rej) আর কলাম ৩ (rej বনাম acc)-এ আলাদা। কলাম ৩ হলো কর্ণ, যেখানে পার্থক্য নিশ্চিত। (গ) না: M2-এর সারি rej, rej, acc, rej, আর কলাম ২-এ M2 rej, D acc. শুধু এক জায়গায় আলাদা, কিন্তু সেটুকুই যথেষ্ট, আর সেটি ঠিক কর্ণের ঘর।
-
শ্রেণিবিভাগ: প্রতিটি language-কে “decidable”, “recognizable কিন্তু decidable নয়” বা “co-recognizable কিন্তু decidable নয়”-এ ভাগ করুন, এক লাইনের কারণসহ: (ক) {⟨M, w⟩ : M w-এ ১,০০০ ধাপের মধ্যে থামে}; (খ) HALTTM; (গ) {⟨M, w⟩ : M w-এ কখনো থামে না}; (ঘ) ADFA; (ঙ) {⟨M⟩ : M input ε-এ থামে}।
(ক) Decidable: ১,০০০ ধাপ নকল করুন, তারপর থামুন; সীমা নির্দিষ্ট বলে সবসময় শেষ হয়। (খ) Recognizable, decidable নয়: নকল করুন, থামলে গ্রহণ (theorem ৬.১)। (গ) Co-recognizable, decidable নয়: এটি HALTTM-এর complement (অবৈধ string বাদে, যা decidable ভাবে আলাদা করা যায়); এটি recognizable হলে HALTTM decidable হতো। (ঘ) Decidable: DFA সবসময় |w| ধাপে থামে (পর্ব ২০)। (ঙ) Recognizable, decidable নয়: ε-এ নকল করে থামলে গ্রহণ করা যায়; আর ⟨M, w⟩ থেকে “input মুছে w লিখে M চালানো” ধরনের যন্ত্র বানিয়ে HALTTM থেকে reduction হয়, যা পর্ব ৫২-এর বিষয়।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমATM undecidable-এর প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- ধরে নেওয়া: H একটি decider, যা ATM decide করে
- H দিয়ে D বানানো: input ⟨M⟩-এ H(⟨M, ⟨M⟩⟩)-এর উল্টো উত্তর
- D সবসময় থামে, কারণ H সবসময় থামে
- D-কে নিজের বর্ণনা ⟨D⟩ দেওয়া
- D ⟨D⟩ গ্রহণ করে ⇔ D ⟨D⟩ গ্রহণ করে না: স্ববিরোধ
- সিদ্ধান্ত: H থাকতে পারে না
ATM = {⟨M, w⟩ : M w গ্রহণ করে} সম্পর্কে কোন বক্তব্য সঠিক?
- ATM recognizable নয়
- ATM decidable, তবে খুব ধীর
- ATM recognizable কিন্তু decidable নয়
- ATM co-recognizable কিন্তু recognizable নয়
একটি language L আর তার complement L̄ দুটিই Turing-recognizable. L সম্পর্কে কী বলা যায়?
- L undecidable হতে পারে
- L decidable
- L অবশ্যই regular
- L অবশ্যই সসীম
ATM undecidable জানা আছে। HALTTM undecidable প্রমাণ করতে কী দেখানো দরকার?
- HALTTM-এর একটি decider থাকলে ATM-এর একটি decider বানানো যেত
- ATM-এর একটি decider থাকলে HALTTM-এর একটি decider বানানো যেত
- HALTTM recognizable
- কয়েকটি program-এর থামা কেউ প্রমাণ করতে পারেনি
“সব Turing machine-এর set countable আর {0, 1}-এর ওপর সব language-এর set uncountable” থেকে সরাসরি কী আসে?
- ATM undecidable
- প্রতিটি decidable language-এর decider খুব ধীর
- বেশিরভাগ language recognizable
- এমন language আছে যা কোনো TM recognize করে না, যদিও যুক্তিটি কোনটি তা বলে না
একটি “halting checker” প্রতিটি program 109 ধাপ চালায়; থামলে “থামে”, না থামলে “থামে না” বলে। এর মূল সমস্যা কী?
- Checker নিজে কখনো কখনো থামে না
- “থামে” উত্তরগুলো ভুল হতে পারে
- কিছু program ঠিক 109 ধাপের পরে থামে, সেগুলোকে ভুলভাবে “থামে না” বলে
- সীমা 1012 করলেই checker নিখুঁত হবে
নিচের কোনটি halting problem-এর undecidability থেকে আসে না?
- কোনো নির্দিষ্ট program-এর থামা কখনো প্রমাণ করা যায় না
- সব program-এ সবসময় থেমে ঠিক উত্তর দেওয়া কোনো checker নেই
- HALTTM-এর complement Turing-recognizable নয়
- Python, C বা অন্য কোনো ভাষাতেই এমন সার্বিক checker লেখা যায় না
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Turing machine countable, language uncountable; তাই recognizable নয় এমন language আছে, কিন্তু গোনার যুক্তি কোনো নির্দিষ্ট দরকারি সমস্যার নাম দেয় না।
- ATM undecidable: decider H ধরে D বানান, যা ⟨M⟩-এ H(⟨M, ⟨M⟩⟩)-এর উল্টো করে; D(⟨D⟩) গ্রহণ করে ⇔ গ্রহণ করে না। স্ববিরোধ H-এর বিরুদ্ধে।
- ATM recognizable (U দিয়ে) কিন্তু co-recognizable নয়; কারণ L decidable ⇔ L আর L̄ দুটিই recognizable.
- HALTTM undecidable: তার decider থেকে ATM-এর decider বানানো যেত। দিক সবসময় এক: জানা undecidable সমস্যা থেকে নতুনটিতে।
- মানে কী নয়: নির্দিষ্ট program বিশ্লেষণ সম্ভব, দুর্বল মডেলে প্রশ্নটি decidable, timeout অন্য প্রশ্নের উত্তর দেয়, আর বাস্তব tool “জানি না”-সহ আনুমানিক উত্তর দেয়।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ০২ · প্রয়োজনীয় গণিত — set, relation, function, graph আর countabilityপটভূমিΣ∗ countable আর Cantor-এর theorem: অংশ ২-এর গোনার যুক্তির ভিত্তি।
- পর্ব ০৪ · Theory of Computation-এর প্রমাণ — string-এর ওপর induction, construction আর diagonalizationফিরে দেখুনDiagonalization আর reduction-এর প্রথম পরিচয়।
- পর্ব ৪৮ · Universal Turing machine — program-ই dataপটভূমি⟨M⟩ encoding আর ATM কেন recognizable.
- পর্ব ৪৭ · Church–Turing thesis — algorithm-এর সংজ্ঞাইতিহাসHilbert-এর প্রশ্ন থেকে ১৯৩৬, আর “কোনো TM নেই” থেকে “কোনো algorithm নেই”।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৫২ reduction দিয়ে undecidability.
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ১৮ — Cardinalityপাশের ট্র্যাকCountable, uncountable আর Cantor-এর diagonal argument, গণিতের দিক থেকে।
- Software Testing · পর্ব ০৬ — Static testing আর static analysisবাস্তবেProgram না চালিয়ে বিশ্লেষণ: undecidability-র মুখে tool কীভাবে কাজ করে।