১৯২৮ সালে প্রখ্যাত জার্মান গণিতবিদ ডেভিড হিলবার্ট সমগ্র বিশ্বের বিজ্ঞানীদের সামনে একটি মহাবৈপ্লবিক চ্যালেঞ্জ উপস্থাপন করেন: এন্টশাইডুংসপ্রবলেম (Entscheidungsproblem বা সিদ্ধান্ত সমস্যা)। এমন কোনো সাধারণ যান্ত্রিক নিয়ম বা অ্যালগরিদম কি তৈরি করা সম্ভব, যা যেকোনো গাণিতিক প্রস্তাবনার সত্যতা বা মিথ্যাত্ব স্বয়ংক্রিয়ভাবে প্রমাণ করে দিতে পারে? দীর্ঘ আট বছর গণিতবিদরা এমন এক সর্বজ্ঞানী প্রুফ-মেশিনের স্বপ্ন দেখেছিলেন। অবশেষে ১৯৩৬ সালের গ্রীষ্মে কেমব্রিজের ২৪ বছর বয়সী গণিতবিদ অ্যালান টুরিং সেই স্বপ্নের সমাপ্তি ঘটান। কাগজের টেপ ও রিড-রাইট হেডের সমন্বয়ে একটি কাল্পনিক যন্ত্রের নকশা করে—যা আজকের সমস্ত আধুনিক কম্পিউটারের মূল ব্লুপ্রিন্ট—টুরিং অকাট্যভাবে প্রমাণ করেন যে গণিতের এমন কিছু মৌলিক প্রশ্ন রয়েছে যা কোনো কম্পিউটার কখনোই গণনা করতে পারবে না: হল্টিং প্রবলেম (The Halting Problem)। এটি কম্পিউটেশনের চিরন্তন সীমানা নির্ধারণ করে দেয়।

১. সমীকরণের পরিচয়: অনির্ণেয়তার গাণিতিক রূপ

হল্টিং সমস্যা জানতে চায়: এমন কোনো অ্যালগরিদম $text{HALT}(M, w)$ কি সম্ভব যা যেকোনো প্রোগ্রাম $M$ এবং ইনপুট $w$ বিশ্লেষণ করে বলে দেবে প্রোগ্রামটি কি সসীম সময়ে থেমে যাবে নাকি অনন্ত লুপে আটকে থাকবে?

$$text{HALT}(M, w) = begin{cases} 1 & text{যদি প্রোগ্রামটি সসীম ধাপে থেমে যায় (Halts)} \ 0 & text{যদি প্রোগ্রামটি অনন্ত লুপে চলতে থাকে (Infinite Loop)} end{cases}$$

টুরিংয়ের ঐতিহাসিক উপপাদ্য ঘোষণা করে:

$$text{HALT}(M, w) text{ চরমভাবে অনির্ণেয় (Undecidable বা Non-Computable)}$$

এর সাথে ঘনিষ্ঠভাবে যুক্ত হলো কলমোগোরভ জটিলতা (Kolmogorov Complexity) $K(x)$—কোনো স্ট্রিং $x$ তৈরি করার জন্য সংক্ষিপ্ততম প্রোগ্রামের দৈর্ঘ্য:

$$K(x) = min_p { |p| : U(p) = x }$$

কলমোগোরভ জটিলতাও অনির্ণেয়: কোনো নির্দিষ্ট প্রোগ্রামই যে কোনো উপাত্তের সবচেয়ে নিখুঁত ও সংক্ষিপ্ততম রূপ, তা কোনো অ্যালগরিদম দ্বারা প্রমাণ করা অসম্ভব।

২. টুরিংয়ের ডায়াগোনালাইজেশন প্রমাণ

টুরিংয়ের প্রমাণের সৌন্দর্য হলো স্ব-বিরোধাভাসমূলক যুক্তি (Proof by Contradiction)।

ধরা যাক এমন একটি কাল্পনিক প্রোগ্রাম $text{Halt}(M, w)$ বিদ্যমান যা নির্ভুল ভবিষ্যৎবাণী করতে পারে। এখন আমরা একটি বৈরী প্রোগ্রাম $D$ তৈরি করি যা $text{Halt}$-এর বিপরীত আচরণ করবে:

begin{aligned} &textbf{অ্যালগরিদম } D(langle M rangle): \ &quad textbf{যদি } text{Halt}(M, langle M rangle) == 1 textbf{ হয়}: \ &quadquad textbf{অনন্ত লুপে ঢুকে যাও} quad text{(কখনোই থামবে না)} \ &quad textbf{নতুবা}: \ &quadquad textbf{থেমে যাও} quad text{(তৎক্ষণাৎ সমাপ্ত হবে)} end{aligned}

এখন প্রোগ্রাম $D$-এর ভেতরে ইনপুট হিসেবে যদি তার নিজের কোডই দেওয়া হয় ($D(langle D rangle)$), তবে কী ঘটবে?

  • যদি $text{Halt}$ বলে $D$ থামবে, তবে কোডের শর্তানুসারে $D$ অনন্ত লুপে আটকে গিয়ে কখনোই থামবে না। চরম স্ব-বিরোধাভাস!
  • যদি $text{Halt}$ বলে $D$ অনন্ত লুপে চলবে, তবে কোডের শর্তানুসারে $D$ তৎক্ষণাৎ থেমে যাবে। চরম স্ব-বিরোধাভাস!

উভয় ক্ষেত্রেই যুক্তি এক অসম্ভব দ্বন্দ্বে নিপতিত হয়: $D$ থামবে ঠিক তখনই যখন সে থামবে না। অতএব, এমন কোনো সর্বজনীন হল্টিং অ্যালগরিদম তৈরি করা গণিত ও মহাবিশ্বের কোনো কম্পিউটারের পক্ষেই সম্ভব নয়।

৩. পরিণতি: আধুনিক কম্পিউটারের জন্ম ও রাইসের উপপাদ্য

এই অসম্ভবকে প্রমাণ করতে গিয়েই অ্যালান টুরিং সার্বজনীন টুরিং মেশিনের নকশা করেন—যেখানে একই মেমরিতে ডেটা এবং প্রোগ্রাম সংরক্ষিত থাকে, যার ওপর ভিত্তি করে জন ভন নিউম্যান আজকের আধুনিক কম্পিউটারের স্থাপত্য গড়ে তোলেন। ১৯৫৩ সালে রাইসের উপপাদ্য প্রমাণ করে যে কোনো প্রোগ্রামের নন-ট্রিভিয়াল আচরণ (যেমন এটি কি ক্র্যাশ করবে, ভাইরাস মুক্ত কি না) স্বয়ংক্রিয়ভাবে ১০০% নির্ভুলভাবে যাচাই করা গাণিতিকভাবে অসম্ভব।

Tagged with: #অ্যালান-টুরিং #কম্পিউটার বিজ্ঞান #কম্পিউটেবিলিটি #কোয়ান্টাম বলবিদ্যা #ক্যালকুলাস #গণিত #জ্ঞান বদলে দেওয়া সমীকরণসমূহ #পদার্থবিজ্ঞান #বাংলা বিজ্ঞান ব্লগ #বিজ্ঞান #বিজ্ঞানের ইতিহাস #যুক্তিবিদ্যা #শাকিল মাহমুদ সজল #হল্টিং সমস্যা
শাকিল মাহমুদ সজল

শাকিল মাহমুদ সজল

সফটওয়্যার প্রকৌশলী ও লেখক, ঢাকা, বাংলাদেশ। কম্পিউটার বিজ্ঞান, পদার্থবিজ্ঞান, ইতিহাস ও ভাবনার সমন্বয়ে ব্যক্তিগত নোট ও প্রবন্ধ সংকলন।