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

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

গণনা সংক্রান্ত একটি পাঠ্যপুস্তক

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

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

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

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

গণনীয় ও অগণনীয় সেটসমূহ

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

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

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