কম্পিউটিং ও এআইয়ের ইতিহাস (পর্ব ৪): গণনযোগ্যতার তাত্ত্বিক ভিত্তি — বুলিয়ান অ্যালজেব্রা, গ্যোডেলের অসম্পূর্ণতা এবং টুরিং মেশিন

বাস্তব পৃথিবীতে প্রথম ইলেকট্রনিক ডিজিটাল কম্পিউটার তৈরি হওয়ার অনেক আগেই তার তাত্ত্বিক রূপরেখা নিখুঁত গাণিতিক যুক্তির মাধ্যমে প্রমাণিত হয়েছিল। ১৯৩৬ সালে কেমব্রিজ বিশ্ববিদ্যালয়ের চব্বিশ বছর বয়সী এক তরুণ গণিতবিদ অ্যালান টুরিং বসেছিলেন গণিতবিজ্ঞানী ডেভিড হিলবার্টের একটি মৌলিক প্রশ্নের উত্তর খুঁজতে: পৃথিবীর সমস্ত গাণিতিক সত্য কি কোনো অন্ধ যান্ত্রিক নিয়মে সমাধান করা সম্ভব? এই প্রশ্নের উত্তরে “না” বলতে গিয়ে টুরিং উদ্ভাবন করেন তাঁর কালজয়ী ইউনিভার্সাল মেশিন—যা ভবিষ্যতের সমস্ত কম্পিউটার, কম্পাইলার এবং কৃত্রিম বুদ্ধিমত্তার ব্লুপ্রিন্ট হিসেবে প্রতিষ্ঠা লাভ করে।

১. জর্জ বুল এবং যুক্তির বীজগণিত

অ্যারিস্টটলের সময় থেকে প্রায় দুই হাজার বছর ধরে মানব যুক্তি কেবল ভাষার ব্যাকরণে সীমাবদ্ধ ছিল। ১৮৫৪ সালে ব্রিটিশ গণিতবিদ জর্জ বুল প্রকাশ করেন তাঁর যুগান্তকারী গ্রন্থ দ্য লজ অব থট (The Laws of Thought)। বুলের প্রধান বৈপ্লবিক অন্তর্দৃষ্টি ছিল: যুক্তিকে ভাষার জটিলতা থেকে মুক্ত করে বিশুদ্ধ বীজগণিতের সূত্রের মতো প্রকাশ করা সম্ভব।

বুল সমস্ত যৌক্তিক অবস্থাকে দুটি বাইনারি মানে সংজ্ঞায়িত করেন $\mathbb{B} = \{০, ১\}$—যেখানে ১ হলো সত্য (True) এবং ০ হলো মিথ্যা (False)। তিনি তিনটি মৌলিক অপারেশন সূত্রবদ্ধ করেন:

• কনজাংশন (AND / $\wedge$): গুণাত্মক সত্য $x \cdot y$
• ডিসজাংশন (OR / $\vee$): যোগাত্মক সত্য $x + y – x \cdot y$
• নেগেশন (NOT / $\neg$): পরিপূরক সত্য $১ – x$

বুল দেখান যে সাধারণ যুক্তির তর্কগুলোকে বীজগণিতীয় সমীকরণের মতো সমাধান করা যায়। ৮৩ বছর পর ক্লড শ্যানন প্রমাণ করেন যে এই বুলিয়ান বীজগণিত হুবহু ইলেকট্রিক্যাল সুইচের অন-অফ সার্কিটের সাথে মিলে যায়—যা আধুনিক ডিজিটাল লজিক গেটের মূল ভিত্তি।

২. হিলবার্টের স্বপ্ন এবং গ্যোডেলের ভূমিকম্প

বিংশ শতাব্দীর শুরুতে জার্মান গণিতের পুরোধা ডেভিড হিলবার্ট এক মহান স্বপ্ন দেখেছিলেন: পৃথিবীর সমস্ত গণিতকে কতগুলো স্বতঃসিদ্ধ বা সূত্রের ওপর এমনভাবে দাঁড় করাতে হবে, যাতে গণিতে কোনো দ্বন্দ্ব বা অসম্পূর্ণতা না থাকে। ১৯২৮ সালে তিনি তিনটি মৌলিক প্রশ্ন তোলেন:

1. গণিত কি সম্পূর্ণ (Complete)? প্রতিটি সত্য গাণিতিক বিবৃতি কি সূত্রের মাধ্যমে প্রমাণ করা সম্ভব?
2. গণিত কি সুসংগত (Consistent)? এটি কি নিশ্চিত যে গণিতে কখনো কোনো আত্মবিরোধী ফলাফল ($০ = ১$) তৈরি হবে না?
3. গণিত কি নির্ণয়যোগ্য (Decidable)? এন্টশাইডুংসপ্রবলেম (Entscheidungsproblem / Decision Problem): এমন কোনো যান্ত্রিক অ্যালগরিদম কি সম্ভব, যা যেকোনো গাণিতিক প্রস্তাবনা দিলে সীমিত সংখ্যক ধাপে বলে দিতে পারবে তা সত্য না মিথ্যা?

১৯৩১ সালে অস্ট্রিয়ান গণিতবিদ কুর্ট গ্যোডেল তাঁর বিখ্যাত ইনকমপ্লিটনেস থিওরেম (Incompleteness Theorems) দিয়ে হিলবার্টের প্রথম দুটি স্বপ্ন চুরমার করে দেন। গ্যোডেল প্রমাণ করেন যে পাটিগণিতের নিয়ম মেনে চলা যেকোনো সংগত গাণিতিক ব্যবস্থায় এমন কিছু সত্য বিবৃতি থাকবেই, যা ওই ব্যবস্থার ভেতরে থেকে কখনোই প্রমাণ করা যাবে না। কিন্তু তৃতীয় প্রশ্নটি—অর্থাৎ কোনো অ্যালগরিদমের সাহায্যে সিদ্ধান্ত নেওয়া সম্ভব কিনা—তখনো অমীমাংসিত ছিল।

৩. অ্যালান টুরিংয়ের ১৯৩৬ সালের পেপার: ইউনিভার্সাল মেশিন

হিলবার্টের নির্ণয়যোগ্যতা সমস্যার উত্তর দিতে হলে প্রথমে আনুষ্ঠানিকভাবে সংজ্ঞায়িত করতে হতো “যান্ত্রিক প্রক্রিয়া” বা অ্যালগরিদম বলতে আসলে কী বোঝায়। ১৯৩৬ সালে প্রকাশিত তাঁর অমর গবেষণাপত্র On Computable Numbers, with an Application to the Entscheidungsproblem-এ অ্যালান টুরিং খাতা-কলমে হিসাব করা একজন মানুষের কার্যপদ্ধতিকে পদার্থবিজ্ঞানের সর্বনিম্ন মৌলিক উপাদানে নামিয়ে আনেন।

টুরিং কল্পনা করেন এক তাত্ত্বিক যন্ত্র—আজকের বিখ্যাত টুরিং মেশিন (Turing Machine)—যার চারটি মূল উপাদান রয়েছে:

• একটি অসীম দৈর্ঘ্যের এক-মাত্রিক টেপ (Tape), যা ছোট ছোট ঘরে বিভক্ত এবং প্রতিটি ঘরে কোনো প্রতীক বা খালি জায়গা ($b$) থাকতে পারে।
• একটি রিড/রাইট হেড (Read/Write Head), যা টেপের ওপর অবস্থান করে প্রতীক পড়তে পারে, নতুন প্রতীক লিখতে পারে এবং এক ঘর ডানে ($R$) বা বাঁয়ে ($L$) সরতে পারে।
• একটি স্টেট কন্ট্রোল ইউনিট, যা যন্ত্রের বর্তমান অবস্থা ধারণ করে ($Q = \{q_0, q_1, \dots, q_m\}$)।
• একটি গাণিতিক ট্রানজিশন ফাংশন ($\delta$), যা বর্তমান অবস্থা এবং পঠিত প্রতীকের ওপর ভিত্তি করে পরবর্তী কাজ নির্ধারণ করে:

$$\delta: Q \times \Sigma \to Q \times \Sigma \times \{L, R\}$$

ইউনিভার্সাল টুরিং মেশিন (UTM)

টুরিংয়ের সবচেয়ে বৈপ্লবিক অন্তর্দৃষ্টি ছিল: যেকোনো টুরিং মেশিনের কাজের নিয়ম বা ট্রানজিশন টেবিল ($\delta$) নিজেও আসলে কতগুলো প্রতীক বা সংখ্যার সমষ্টি $\langle M \rangle$।

এর ওপর ভিত্তি করে টুরিং প্রস্তাব করেন ইউনিভার্সাল টুরিং মেশিন ($U$)। এই যন্ত্রটির টেপে যেকোনো মেশিনের নকশা $\langle M \rangle$ এবং তার ইনপুট $w$ লিখে দিলে, ইউনিভার্সাল মেশিনটি হুবহু সেই মূল মেশিনের কাজের অনুকরণ (Simulation) করতে পারে:

$$U(\langle M \rangle, w) = M(w)$$

এটিই হলো আজকের স্টোরড-প্রোগ্রাম কম্পিউটারের (Stored-Program Computer) তাত্ত্বিক জন্ম। টুরিংয়ের আগে যেকোনো যন্ত্র কেবল একটি নির্দিষ্ট কাজের জন্যই তৈরি হতো (যেমন পাস্কালিন কেবল যোগ করত)। কিন্তু টুরিং প্রমাণ করলেন যে একটিমাত্র স্থায়ী হার্ডওয়্যার তৈরি করলেই যথেষ্ট—ইনপুট টেপে সফটওয়্যারের নির্দেশ পরিবর্তন করে সেই একই যন্ত্র দিয়ে মহাবিশ্বের যেকোনো অ্যালগরিদম চালানো সম্ভব!

৪. হল্টিং প্রবলেম এবং যুক্তির সীমারেখা

কম্পিউটিংয়ের তাত্ত্বিক ভিত্তি স্থাপনের পর টুরিং হিলবার্টের এন্টশাইডুংসপ্রবলেম-এর মুখোমুখি হন। তিনি উত্থাপন করেন বিখ্যাত হল্টিং প্রবলেম (Halting Problem): এমন কোনো সার্বজনীন অ্যালগরিদম $H$ কি তৈরি করা সম্ভব, যা যেকোনো প্রোগ্রাম $\langle M \rangle$ এবং ইনপুট $w$ বিশ্লেষণ করে সীমিত সময়ের মধ্যে বলে দিতে পারবে প্রোগ্রামটি কি কোনো এক সময় কাজ শেষ করে থামবে (Halt), নাকি অনন্তকাল লুপে ঘুরতে থাকবে?

ক্যান্টরের ডায়াগোনালাইজেশন মেথড ব্যবহার করে টুরিং প্রমাণ করেন যে এমন কোনো অ্যালগরিদম তৈরি করা যৌক্তিকভাবে অসম্ভব! ধরা যাক এমন একটি অ্যালগরিদম $H$ সত্যি বিদ্যমান। তাহলে আমরা এমন একটি শত্রুভাবাপন্ন প্রোগ্রাম $D$ তৈরি করতে পারি, যা নিজের কোডকেই ইনপুট হিসেবে গ্রহণ করবে:

“` Algorithm: Adversarial Program D Input: Program description function D(): if H(, ) == 1: while True: pass // H যদি বলে থামবে, তবে এটি অনন্ত লুপে ঢুকবে else: return True // H যদি বলে থামবে না, তবে এটি সাথে সাথে থেমে যাবে “`

এখন প্রোগ্রাম $D$-এর মধ্যে যদি তার নিজের কোড ইনপুট দেওয়া হয়—অর্থাৎ $D(\langle D \rangle)$ চালানো হয়, তবে কী ঘটবে?

• যদি $D$ থেমে যায়, তবে $H$-এর নিয়ম অনুযায়ী এটি অনন্ত লুপে আটকে যাবে (স্ববিরোধিতা!)।
• যদি $D$ অনন্তকাল লুপে ঘুরতে থাকে, তবে অ্যালগরিদম অনুযায়ী এটি সাথে সাথে থেমে যাবে (স্ববিরোধিতা!)।

উভয় ক্ষেত্রেই এক অনিবার্য আত্মবিরোধী প্যারাডক্স তৈরি হয় ($H \iff \neg H$)। সুতরাং, এই ধরনের কোনো অ্যালগরিদম কখনোই অস্তিত্বশীল হতে পারে না। হল্টিং প্রবলেম হলো অনির্ণয়যোগ্য (Undecidable)। হিলবার্টের স্বপ্ন ভেঙে দিয়ে টুরিং প্রমাণ করলেন: গণিতকে কোনোদিন অন্ধ যন্ত্রের মাধ্যমে সর্বজ্ঞ করে তোলা যাবে না। প্রকৃতিতে এমন সত্য রয়েছে, যা কোনো অ্যালগরিদম কখনোই গণনা করতে পারবে না।

---