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

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

গণিত বা কম্পিউটার বিজ্ঞানের সব সমস্যাই কি সমাধানযোগ্য? আমরা জানি NP ক্যাটাগরির সমস্যাগুলোকে পলিনোমিয়াল সময়ে সমাধান করার সম্ভব নাকি সেটা জানা এখন পর্যন্ত সম্ভব হয় নি, কিন্তু ইনপুটের আকার যথেষ্ট ছোট হলে অথবা তোমার হাতে অসীম সময় এবং মেমরি থাকলে NP সমস্যাও এক্সপোনেনশিয়াল সময়ে সমাধান করা সম্ভব। কিন্তু এমন কিছু সমস্যা আছে যেটা তোমার হাতে যত বড় সুপার কম্পিউটারই থাকুক সমাধান করা সম্ভব না। এখানে আমি ধরে নিচ্ছি আমাদের কম্পিউটারগুলো টুরিং মেশিন কম্পিউটেবল। (টুরিং মেশিন কি মনে না থাকলে আগে আমার এই লেখাটা পড়ো) হাল্টিং প্রবলেম (Halting Problem) এমনই একটা সমস্যা যার কোনো সমাধান নেই। তোমাকে একট...
Read More