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

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

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

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

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

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

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

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

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

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

তথ্যসূত্র

↑ Bauer-Mengelberg, Stefan (১৯৬৬-০৯-০২)। "Martin Davis. On formally undecidable propositions of the Principia Mathematica and related systems. I. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, p. 4. - Kurt Gödel. On formally undecidable propositions of Principia Mathematica and related systems I. English translation of 4183 by Elliott Mendelson. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, pp. 5–38. - Martin Davis. On undecidable propositions of formal mathematical systems. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, pp. 39–40. - Kurt Gödel. On undecidable propositions of formal mathematical systems. A revised reprint of 41814. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, pp. 41–71. (See corrigenda, p. 74.) - Kurt Gödel. Postscriptum. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, pp. 71–73. - Kurt Gödel. On intuitionistic arithmetic and number theory. English translation of 41811 by Martin Davis. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, pp. 75–81. - Kurt Gödel. On the length of proofs. English translation of I 116 by Martin Davis. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, pp. 82–83. - Kurt Gödel. Remarks before the Princeton Bicentennial Conference on Problems in Mathematics — 1946. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, pp. 84–88. [Cf. XII 89(2).] - Martin Davis. An unsolvable problem of elementary number theory. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, p. 88. - Alonzo Church. An unsolvable problem of elementary number theory. A reprint of I 73. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, pp. 89–107."। Journal of Symbolic Logic। 31 (3): 484–494। আইএসএসএন 0022-4812। ডিওআই:10.2307/2270465। সংগ্রহের তারিখ ১৮ মার্চ ২০২২।
↑ Soare, Robert I. (2016)। Defining Computability। Berlin, Heidelberg: Springer Berlin Heidelberg। পৃষ্ঠা 3–22। আইএসবিএন 978-3-642-31932-7। এখানে তারিখের মান পরীক্ষা করুন: |year= / |date= mismatch (সাহায্য)
↑ Lyne, Patricia (1994-06)। "The importance of measurement"। Nurse Researcher। 1 (4): 13–25। আইএসএসএন 1351-5578। ডিওআই:10.7748/nr.1.4.13.s3। সংগ্রহের তারিখ ১৮/৩/২০২২। এখানে তারিখের মান পরীক্ষা করুন: |তারিখ=, |সংগ্রহের-তারিখ= (সাহায্য)

[1] Bauer-Mengelberg, Stefan (১৯৬৬-০৯-০২)। "Martin Davis. On formally undecidable propositions of the Principia Mathematica and related systems. I. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, p. 4. - Kurt Gödel. On formally undecidable propositions of Principia Mathematica and related systems I. English translation of 4183 by Elliott Mendelson. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, pp. 5–38. - Martin Davis. On undecidable propositions of formal mathematical systems. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, pp. 39–40. - Kurt Gödel. On undecidable propositions of formal mathematical systems. A revised reprint of 41814. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, pp. 41–71. (See corrigenda, p. 74.) - Kurt Gödel. Postscriptum. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, pp. 71–73. - Kurt Gödel. On intuitionistic arithmetic and number theory. English translation of 41811 by Martin Davis. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, pp. 75–81. - Kurt Gödel. On the length of proofs. English translation of I 116 by Martin Davis. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, pp. 82–83. - Kurt Gödel. Remarks before the Princeton Bicentennial Conference on Problems in Mathematics — 1946. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, pp. 84–88. [Cf. XII 89(2).] - Martin Davis. An unsolvable problem of elementary number theory. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, p. 88. - Alonzo Church. An unsolvable problem of elementary number theory. A reprint of I 73. The undecidable, Basic papers on undecidable propositions, unsolvable problems and computable functions, edited by Martin Davis, Raven Press, Hewlett, New York, 1965, pp. 89–107."। Journal of Symbolic Logic। 31 (3): 484–494। আইএসএসএন 0022-4812। ডিওআই:10.2307/2270465। সংগ্রহের তারিখ ১৮ মার্চ ২০২২।

[2] Soare, Robert I. (2016)। Defining Computability। Berlin, Heidelberg: Springer Berlin Heidelberg। পৃষ্ঠা 3–22। আইএসবিএন 978-3-642-31932-7। এখানে তারিখের মান পরীক্ষা করুন: |year= / |date= mismatch (সাহায্য)

[3] Lyne, Patricia (1994-06)। "The importance of measurement"। Nurse Researcher। 1 (4): 13–25। আইএসএসএন 1351-5578। ডিওআই:10.7748/nr.1.4.13.s3। সংগ্রহের তারিখ ১৮/৩/২০২২। এখানে তারিখের মান পরীক্ষা করুন: |তারিখ=, |সংগ্রহের-তারিখ= (সাহায্য)

[১]

[২]

[৩]