১৯৩৬ সালে মাত্র চব্বিশ বছর বয়সী ব্রিটিশ গণিতবিদ অ্যালান ম্যাথিসন টুরিং ডেভিড হিলবার্টের সর্বশেষ স্বপ্ন—এন্টশাইডুংসপ্রবলেম (Entscheidungsproblem বা সিদ্ধান্ত গ্রহণ সমস্যা)—সমাধানে ব্রতী হন। কোনো গাণিতিক উক্তি সত্য নাকি মিথ্যা তা নির্ণয় করার কোনো সার্বজনীন অ্যালগরিদম আছে কিনা, তা জানতে হলে প্রথমে “যান্ত্রিক গণনা” কাকে বলে তার একটি সার্বজনীন সংজ্ঞা প্রয়োজন ছিল। এর ফলে জন্ম নিল তাত্ত্বিক কম্পিউটার বিজ্ঞানের আদি ভিত্তি: টুরিং মেশিন (Turing Machine), চার্চ-টুরিং অনুসিদ্ধান্ত, এবং গণনার ইতিহাসে সবচেয়ে বিখ্যাত অমীমাংসিত সত্য: হল্টিং প্রবলেম (The Halting Problem)।
১. টুরিং মেশিনের আনুষ্ঠানিক গঠন
টুরিং একজন গণনাকারী মানুষের কার্যক্রমকে একটি বিমূর্ত যন্ত্রে রূপান্তর করেন। একটি ডিটারমিনিস্টিক টুরিং মেশিন হলো একটি ৭-টিউপল:
[
M = langle Q, Sigma, Gamma, delta, q_0, q_{text{accept}}, q_{text{reject}} rangle
]
- $Q$: অভ্যন্তরীণ অবস্থার সসীম সেট (States)।
- $Sigma$: ইনপুট বর্ণমালা।
- $Gamma$: টেপ বর্ণমালা ($Sigma$ এবং শূন্য প্রতীক $sqcup$-এর সমন্বয়)।
- $delta$: ট্রানজিশন ফাংশন: $Q times Gamma to Q times Gamma times {L, R}$। বর্তমান অবস্থা ও প্রতীক দেখে যন্ত্রটি কী লিখবে, কোন নতুন অবস্থায় যাবে এবং হেডটি বামে ($L$) নাকি ডানে ($R$) সরবে তা নির্ধারণ করে।
- টেপটি হলো সীমাহীন স্মৃতির ভাণ্ডার (Unbounded Memory)।
২. চার্চ-টুরিং অনুসিদ্ধান্ত (Church-Turing Thesis)
১৯৩৪ থেকে ১৯৩৬ সালের মধ্যে কার্যকর গণনার তিনটি সম্পূর্ণ স্বাধীন মডেল উদ্ভাবিত হয়:
- গোডেল ও ক্লিনের জেনারেল রিকার্সিভ ফাংশন
- আলোনজো চার্চের ল্যাম্বডা ক্যালকুলাস ($lambda$-calculus)
- অ্যালান টুরিংয়ের টুরিং মেশিন
টুরিং এবং চার্চ প্রমাণ করেন যে এই তিনটি মডেল পরস্পর গাণিতিকভাবে সম্পূর্ণ অভিন্ন! এর ওপর ভিত্তি করে গড়ে ওঠে চার্চ-টুরিং থিসিস: যেকোনো হিসাব বা অ্যালগরিদম যা কোনো মানুষ বা প্রাকৃতিক পদার্থবিজ্ঞানের যন্ত্র দিয়ে কার্যকরভাবে করা সম্ভব, তা একটি টুরিং মেশিন দিয়েও করা সম্ভব।
৩. ডিসাইডেবিলিটি বনাম রেকগনাইজেবিলিটি
- টুরিং ডিসাইডেবল (Recursive, $mathcal{R}$): এমন সমস্যা যার জন্য একটি অ্যালগরিদম আছে যা সব ইনপুটের জন্যই নিশ্চিতভাবে নির্দিষ্ট সময়ে থেমে সঠিক হ্যাঁ/না উত্তর দিতে পারে।
- টুরিং রেকগনাইজেবল (Recursively Enumerable, $mathcal{RE}$): উত্তর ‘হ্যাঁ’ হলে মেশিনটি থেমে যাবে, কিন্তু উত্তর ‘না’ হলে মেশিনটি সারাজীবন অসীম লুপে ঘুরতে পারে।
৪. হল্টিং প্রবলেম ও ক্যান্টরের ডায়াগোনালাইজেশন
হল্টিং প্রবলেম: কোনো টুরিং মেশিনের কোড $langle M rangle$ এবং একটি ইনপুট $w$ দিলে, এমন কোনো মাস্টার প্রোগ্রাম তৈরি করা সম্ভব যা নিশ্চিত করে বলে দেবে মেশিনটি কি একসময় থামবে নাকি চিরকাল চলতে থাকবে?
টুরিংয়ের উপপাদ্য: হল্টিং প্রবলেম সমাধানযোগ্য নয়
হল্টিং সমস্যা সমাধানকারী কোনো সাধারণ অ্যালগরিদম সৃষ্টি করা মহাবিশ্বের কোনো যন্ত্রের পক্ষেই সম্ভব নয় ($H_{text{TM}} notin mathcal{R}$)।
প্রমাণ (ডায়াগোনালাইজেশন):
- ধরা যাক এমন একটি অলৌকিক প্রোগ্রাম $H(langle M, w rangle)$ আছে যা $M$ থামবে কিনা তা নির্ভুল বলতে পারে।
- এবার আমরা একটি নতুন শয়তানি যন্ত্র $D$ তৈরি করি যা যেকোনো মেশিনের কোড ইনপুট হিসেবে নেয়:
- $D$ প্রথমে $H$-কে দিয়ে পরীক্ষা করায় মেশিনটি নিজের কোডের ওপর চালালে থামবে কিনা।
- যদি $H$ বলে “থামবে”, তবে $D$ ইচ্ছাকৃতভাবে একটি অসীম লুপে (Infinite Loop) ঢুকে পড়ে!
- যদি $H$ বলে “থামবে না (লুপ করবে)”, তবে $D$ সাথে সাথে থেমে যায় (Halt)!
- এবার এই অদ্ভুত যন্ত্র $D$-এর ভেতরে তার নিজের কোড $langle D rangle$ ইনপুট দেওয়া হলে কী ঘটবে?
- সংজ্ঞানুসারে:
[
D(langle D rangle) text{ থামবে} iff D(langle D rangle) text{ অনন্তকাল লুপে ঘুরবে!}
] - এক চরম যৌক্তিক অসম্ভবতা! একটি প্রোগ্রাম একই সাথে থামতে এবং না-থামতে পারে না।
- অতএব আমাদের প্রাথমিক অনুমানটিই ভুল ছিল। সার্বজনীন হল্টিং অ্যালগরিদম তৈরি করা অসম্ভব! $blacksquare$
৫. হিলবার্টের এন্টশাইডুংসপ্রবলেমের চিরন্তন সমাপ্তি
টুরিং প্রমাণ করেন যে ফার্স্ট-অর্ডার লজিকের বৈধতা পরীক্ষা করা এবং হল্টিং প্রবলেম সমাধান করা একই কথা। যেহেতু হল্টিং সমস্যা সমাধানহীন, তাই গণিতের সমস্ত উক্তি যান্ত্রিকভাবে সত্য-মিথ্যা প্রমাণ করার কোনো অ্যালগরিদম কখনোই বানানো সম্ভব নয়। যুক্তি ও গণনার এই প্রাকৃতিক সীমানা আবিষ্কারের মাধ্যমে আধুনিক কম্পিউটার বিজ্ঞানের সোনালী যুগের সূচনা হয়।
