হল্টিং প্রবলেম

১ · HALT ভাষার সংজ্ঞা

L37-এর এনকোডিং নোটেশন $\langle \cdot \rangle$ ব্যবহার করে, ফরমালি —

$$HALT = \{\langle M, w \rangle : M \text{ একটি টুরিং মেশিন এবং } M \text{ ইনপুট } w\text{-এর উপর হল্ট করে}\}$$

এটি কম্পিউটার সায়েন্সের সবচেয়ে বিখ্যাত আনডিসাইডেবিলিটিUndecidabilityএমন একটি প্রশ্ন যা কোনো অ্যালগরিদম দিয়েই সবসময় সঠিকভাবে উত্তর দেওয়া সম্ভব নয় ফলাফল। থিওরেম বলছে — কোনো TM-ই প্রতিটি সম্ভাব্য $(M, w)$ জোড়ার জন্য নির্ভুলভাবে "হল্ট করে" বা "চিরকাল লুপ করে" নির্ধারণ করতে পারে না।

২ · প্রমাণ — ডায়াগোনালাইজেশন ও কনট্রাডিকশন

এই প্রমাণটি সঠিকভাবে বোঝা সত্যিই গুরুত্বপূর্ণ — এটি এই কোর্সের সবচেয়ে বিখ্যাত, উদযাপিত যুক্তি। ধাপে ধাপে —

1. ধরে নিন (contradiction-এর জন্য): HALT-এর একটি decider $H$ আছে — $H(\langle M, w \rangle)$ সবসময় হল্ট করে, এবং সঠিকভাবে "হল্ট করে" বা "চিরকাল লুপ করে" আউটপুট দেয়।
2. একটি নতুন মেশিন $D$ বানান — ইনপুট $\langle M \rangle$ (একটি TM-এর নিজের বর্ণনা, স্ব-নির্দেশনামূলকভাবে) নিয়ে, $D$ চালায় $H(\langle M, M \rangle)$ — অর্থাৎ প্রশ্ন করে "$M$ কি নিজের নিজের বর্ণনার উপর হল্ট করে?" — যদি $H$ বলে "হল্ট করে," তাহলে $D$ ইচ্ছাকৃতভাবে চিরকাল লুপ করে; যদি $H$ বলে "চিরকাল লুপ করে," তাহলে $D$ ইচ্ছাকৃতভাবে হল্ট করে (accept করে) — অর্থাৎ, $D$-কে ঠিক $H$-এর predict-এর বিপরীত করার জন্য নির্মাণ করা হয়েছে।
3. এখন জিজ্ঞাসা করুন — $D$ নিজের বর্ণনা $\langle D \rangle$-এর উপর কী করে?
   • যদি $D$, $\langle D \rangle$-এর উপর হল্ট করে — তাহলে $D$-এর নির্মাণ অনুযায়ী, $H(\langle D, D \rangle)$ অবশ্যই "চিরকাল লুপ করে" বলেছিল — কিন্তু $D$ তো হল্টই করল — $H$ ভুল ছিল।
   • যদি $D$, $\langle D \rangle$-এর উপর চিরকাল লুপ করে — তাহলে $D$-এর নির্মাণ অনুযায়ী, $H(\langle D, D \rangle)$ অবশ্যই "হল্ট করে" বলেছিল — কিন্তু $D$ তো লুপই করল — $H$ আবারও ভুল।
4. উভয় ক্ষেত্রেই — $H$ ভুল উত্তর দেয় — এটি $H$ একটি সঠিক decider, এই অনুমানের সাথে সরাসরি কনট্রাডিকশন। তাই এমন কোনো $H$ থাকতে পারে না — HALT আনডিসাইডেবল। ∎

৩ · Cantor-এর ডায়াগোনাল আর্গুমেন্টের সাথে সংযোগ

L02-এ উল্লেখ করা হয়েছিল যে একটি অ্যালফাবেটের উপর সম্ভাব্য ল্যাঙ্গুয়েজের সংখ্যা অগণনীয় (uncountable), যদিও সম্ভাব্য প্রোগ্রামের সংখ্যা গণনীয় (countable) — Cantor-এর ডায়াগোনাল আর্গুমেন্ট ব্যবহার করে। এই প্রমাণটির গঠন সেই একই আর্গুমেন্টের সাথে গঠনগতভাবে অভিন্ন — $D$ বিশেষভাবে নির্মিত হয়েছে যাতে সে $H$-এর predict থেকে ঠিক ততটাই "ডিফার" করে, ঠিক যেভাবে Cantor-এর নির্মিত সেটটি তালিকার প্রতিটি সেট থেকে অন্তত একটি উপাদানে "ডিফার" করে (তার নিজের, "diagonal" এন্ট্রিতে) — দুটোই "নিজের বিপরীত এমন কিছু বানাও, যা যেকোনো প্রস্তাবিত সমাধানকে ব্যর্থ করে দেয়" — এই একই কৌশলের প্রয়োগ।

৪ · কোড সেল — ডায়াগোনালাইজেশনের যুক্তি-কাঠামো কংক্রিটভাবে দেখা

একটি স্পষ্টীকরণ জরুরি — নিচের কোড সেলে কোনো সত্যিকারের সাধারণ-উদ্দেশ্যে হল্ট-চেকার নেই (এমন কিছু বানানো অসম্ভব, এটাই তো এই প্রমাণের সিদ্ধান্ত)। বরং, hypothetical_halt_checker একটি ইচ্ছাকৃতভাবে স্টাব/ফেক ফাংশন — যা শুধু একটি hypothetical prediction ফেরত দেয়, যাতে diagonal_machine-এর স্ব-বৈসাদৃশ্যমূলক নির্মাণটা কংক্রিটভাবে চালিয়ে দেখানো যায়। কোড সেলটি উভয় সম্ভাব্য prediction-এর জন্যই (H "halts" বলুক বা "loops_forever" বলুক) দেখায় যে D-এর প্রকৃত আচরণ predict-কে মিথ্যা প্রমাণ করে — একটি সম্পূর্ণ, exhaustive contradiction।

# H-এর অস্তিত্ব ধরে নিলে কী হয় তা কংক্রিটভাবে দেখানোর জন্য একটি স্টাব/ফেক checker।
# বাস্তবে এমন কোনো সত্যিকারের general-purpose H থাকতে পারে না -- এটাই এই প্রমাণের সিদ্ধান্ত।

def hypothetical_halt_checker(predicted_verdict, program_description, input_description):
    """(STUB, ফেক) -- হাইপোথেটিক্যালি ধরে নেওয়া H(<program_description>, <input_description>)
    -- ইলাস্ট্রেশনের জন্য predicted_verdict-ই ('halts' অথবা 'loops_forever') সরাসরি ফেরত
    দেয়, যাতে diagonalization-এর স্ব-বৈসাদৃশ্য কংক্রিটভাবে ধরা যায়।"""
    return predicted_verdict


def diagonal_machine(predicted_verdict, description_of_self):
    """D-এর নির্মাণ (এই পাঠের মূল কৌশল): H(⟨M⟩,⟨M⟩) 'halts' predict করলে D ইচ্ছাকৃতভাবে
    চিরকাল লুপ করে; 'loops_forever' predict করলে D ইচ্ছাকৃতভাবে হল্ট করে (accept)।"""
    checker_says = hypothetical_halt_checker(predicted_verdict, description_of_self, description_of_self)
    if checker_says == 'halts':
        return 'D চিরকাল লুপ করে (deliberately, D-এর নির্মাণ অনুযায়ী)'
    else:  # checker_says == 'loops_forever'
        return 'D হল্ট করে ও accept করে (deliberately, D-এর নির্মাণ অনুযায়ী)'


# --- এবার D-কে নিজের বর্ণনার উপর চালাই -- H যা-ই predict করুক না কেন ---
D_description = "⟨D⟩"  # D নিজের বর্ণনা ইনপুট হিসেবে নিচ্ছে -- স্ব-নির্দেশনা (self-reference)

print("প্রশ্ন: H(⟨D⟩, ⟨D⟩) কী predict করে -- এবং D আসলে কী করে?\n")

for hypothetical_prediction in ['halts', 'loops_forever']:
    actual_behavior = diagonal_machine(hypothetical_prediction, D_description)
    if hypothetical_prediction == 'halts':
        contradiction = "H বলেছিল D হল্ট করবে -- কিন্তু D-এর নির্মাণ অনুযায়ী D আসলে চিরকাল লুপ করে -- H ভুল!"
    else:
        contradiction = "H বলেছিল D লুপ করবে -- কিন্তু D-এর নির্মাণ অনুযায়ী D আসলে হল্ট করে (accept) -- H ভুল!"
    print(f"যদি H(⟨D⟩,⟨D⟩) predict করে '{hypothetical_prediction}':")
    print(f"  D-এর প্রকৃত আচরণ: {actual_behavior}")
    print(f"  ফলাফল: {contradiction}\n")

print("H যা-ই predict করুক -- 'halts' বা 'loops_forever' -- উভয় ক্ষেত্রেই ভুল প্রমাণিত হয়।")
print("তাই এমন কোনো সঠিক, সাধারণ-উদ্দেশ্যে H থাকতে পারে না -- HALT আনডিসাইডেবল। ∎")