Halting Problem

HALT = {⟨M, w⟩ : M input w-তে থামে}। প্রমাণ diagonalization দিয়ে — একটা কাল্পনিক decider H ধরে নিয়ে, H-কে subroutine হিসেবে ব্যবহার করে একটা self-referential মেশিন D বানানো, যেখানে D(⟨D⟩)-এর যেকোনো সম্ভাব্য আচরণ H-এর predict-এর সরাসরি বিপরীত — দ্বন্দ্ব, তাই H থাকতে পারে না।

HALT Turing-recognizable (চালিয়ে দেখে “থামে” বলা যায়) কিন্তু decidable নয় (“থামে না” নিশ্চিতভাবে বলার কোনো উপায় নেই — অপেক্ষা চিরকাল চলতে পারে)।

ব্যবহারিক পরিণতি — কোনো antivirus নিখুঁতভাবে malware চিনতে পারে না, কোনো compiler নিখুঁতভাবে infinite loop ধরতে পারে না। পরের লেসনগুলোর সব undecidability প্রমাণ (reduction, Rice’s theorem) এই একটা ফলাফলের উপর দাঁড়িয়ে।