কম্পিউটার বিজ্ঞান পরিগণনীয়তা তত্ত্ব

পরিগণনীয়তা তত্ত্ব ও পরিগণনামূলক জটিলতা তত্ত্ব পরস্পর সম্পর্কযুক্ত কিন্তু আলাদা এই অর্থে যে পরিগণনামূলক জটিলতা তত্ত্বে কোন সমস্যা কত দক্ষভাবে সমাধান করা যায় তা নিয়ে গবেষণা করা হয়, সমস্যাটা আদৌ সমাধানযোগ্য কি না, তা নিয়ে নয়।

পরিগণনীয়তা তত্ত্ব মূলত যেসব প্রশ্নের উত্তর দেয় তা হল:

• স্বাভাবিক সংখ্যার অপেক্ষক (গণিত) এর জন্য গণনযোগ্য হওয়া বলতে কি বোঝায়?
• অগণনযোগ্য অপেক্ষকগুলোকে তাদের অগণনযোগ্যতার ভিত্তিতে কীভাবে শ্রেণিবদ্ধ করা যায়?

যদিও জ্ঞান ও প্রয়োগের ক্ষেত্রে সীমানা খুব কম, তা সত্ত্বেও গাণিতিক পরিগণনীয়তা তাত্ত্বিকরা আপেক্ষিক পরিগণনীয়তা তত্ত্ব, হ্রাসযোগ্যতা ধারণাসমূহ এবং মাত্রা গঠন নিয়ে পড়াশুনা করা থাকেন; যারা কম্পিউটার বিজ্ঞান শাখায় আছেন তারা পরিগণনামূলক জটিলতা তত্ত্ব, আনুষ্ঠানিক প্রক্রিয়া ও আনুষ্ঠানিক ভাষার উপর মনোযোগ দিয়ে থাকেন।

পরিগণনীয়তা তত্ত্বের উদ্ভব হয় ১৯৩০ এর দশকে, কুর্ট গ্যোডেল, আলোন্‌জো চার্চ, রোজসা পিটার, অ্যালান টুরিং, স্টেফেন ক্লিন ও এমিল পোস্টের কাজের মাধ্যমে।

গবেষকরা যেসব মৌলিক ফলাফল অর্জন করেছেন সেগুলোই টুরিং গণনীয়তাকে অনানুষ্ঠানিক কার্যকর গণনাপদ্ধতির অনানুষ্ঠানিক সংস্করণকে সঠিকভাবে বিধিবদ্ধ করেছে। এসব ফলাফল থেকেই স্টেফেন ক্লিন ১৯৫২ সালে দুটি শব্দ যোগ করেছেন "চার্চের থিসিস"(১৯৫২ঃ৩০০) ও "টুরিং থিসিস" (১৯৫২ঃ৩৭৬) নামে। বর্তমানে তাদেরকে প্রায়ই একসাথেই ডাকা হয় চার্চ- টুরিং থিসিস নামে, যেটা বলে যে কোন ফাংশন যদি অ্যালগরিদম দ্বারা গণনযোগ্য হয় তাহলে সেটা গণনযোগ্য ফাংশন বা অপেক্ষক। প্রথমে সংশয়ে থাকলেও ১৯৪৬ সালে গোডেন এই নিবন্ধের পক্ষে বিতর্ক করেন

টারস্কি তার ভাষণে গুরুত্ব দিয়েছেন