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

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

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

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

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

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

n	2	3	4	5	6	7	...
S(n))	4	6	13	4098?	> 3.5×10¹⁸²⁶⁷	> 10^{10101018705353}	?
ব্যস্ত বিভার ফাংশন Σ(n) যে কোনও গণনাযোগ্য ফাংশনের চেয়ে দ্রুত বৃদ্ধি পায়। অতএব, এটি গণনাযোগ্য নয়; কেবল মাত্র কয়েকটি মান জানা যায়।

কম্পিউটেবিলিটি থিওরি 1930 এর দশকে উদ্ভূত হয়েছিল, যার কাজ ছিল কার্ট গোডেল, অ্যালোনজো চার্চ, রোজসা পিটার, অ্যালান টুরিং, স্টিফেন ক্লিন এবং এমিল পোস্ট।

গবেষকরা প্রাপ্ত মৌলিক ফলাফলগুলি প্রতিষ্ঠিত হয়েছে কার্যকর গণনার অনানুষ্ঠানিক ধারণার সঠিক আনুষ্ঠানিকতা হিসাবে টুরিং কম্পিউটেবিলিটি। 1952 সালে, এই ফলাফলগুলি ক্লেইনকে "চার্চের থিসিস"এবং "টুরিংয়ের থিসিস" দুটি নাম তৈরি করতে পরিচালিত করেছিল। এগুলি প্রায়শই একটি একক হাইপোথিসিস হিসাবে বিবেচিত হয়, চার্চ-টুরিং থিসিস, যা বলে যে কোনও ফাংশন যা অ্যালগরিদম দ্বারা গণনাযোগ্য তা একটি গণনাযোগ্য ফাংশন। যদিও প্রাথমিকভাবে সন্দেহজনক, 376 সালের মধ্যে গোডেল এই থিসিসের পক্ষে যুক্তি দিয়েছিলেন:

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

কার্যকর গণনার সংজ্ঞার সাথে প্রথম প্রমাণ এসেছিল যে গণিতে এমন সমস্যা রয়েছে যা হতে পারে না কার্যকরভাবে সিদ্ধান্ত নেওয়া হয়েছে। 1936 সালে, চার্চ এবং টুরিং তার অসম্পূর্ণতা উপপাদ্যগুলি প্রমাণ করার জন্য গোডেল দ্বারা ব্যবহৃত কৌশলগুলি দ্বারা অনুপ্রাণিত হয়েছিল - 1931 সালে, গোডেল স্বাধীনভাবে প্রমাণ করেছিলেন যে এন্টশেইডুংস সমস্যাটি কার্যকরভাবে সিদ্ধান্ত গ্রহণযোগ্য নয়। এই ফলাফলটি দেখায় যে এমন কোনও অ্যালগরিদমিক পদ্ধতি নেই যা সঠিকভাবে সিদ্ধান্ত নিতে পারে যে ইচ্ছাকৃত গাণিতিক প্রস্তাবগুলি সত্য বা মিথ্যা কিনা।

অনেক সমস্যা এই প্রাথমিক উদাহরণগুলি প্রতিষ্ঠিত হওয়ার পরে গণিতকে সিদ্ধান্তহীন হিসাবে দেখানো হয়েছে। 1947 সালে, মার্কভ এবং পোস্ট স্বতন্ত্র কাগজপত্র প্রকাশ করেছিল যা দেখায় যে সেমিগ্রুপগুলির জন্য সমস্যা শব্দটি কার্যকরভাবে সিদ্ধান্ত নেওয়া যায় না। এই ফলাফলটি প্রসারিত করে, পিওতর নোভিকভ এবং উইলিয়াম বুন 1950 এর দশকে স্বাধীনভাবে দেখিয়েছিলেন যে গোষ্ঠীগুলির জন্য সমস্যা শব্দটি কার্যকরভাবে সমাধানযোগ্য নয়: এমন কোনও কার্যকর পদ্ধতি নেই যা সীমিতভাবে উপস্থাপিত গোষ্ঠীতে একটি শব্দ দেওয়া হলে, শব্দদ্বারা উপস্থাপিত উপাদানটি গোষ্ঠীর পরিচয় উপাদান কিনা তা নির্ধারণ করবে। 1970 সালে, ইউরি মাতিয়াসেভিচ (জুলিয়া রবিনসনের ফলাফল ব্যবহার করে) মাতিয়াসেভিচের উপপাদ্যটি প্রমাণ করেছিলেন, যা বোঝায় যে হিলবের্টের দশম সমস্যার কোনও কার্যকর সমাধান নেই; এই সমস্যাটি জিজ্ঞাসা করেছিল যে পূর্ণসংখ্যার উপর একটি ডায়োফ্যানটিন সমীকরণের পূর্ণসংখ্যাগুলিতে সমাধান রয়েছে কিনা তা নির্ধারণের জন্য কোনও কার্যকর পদ্ধতি রয়েছে কিনা। সিদ্ধান্তহীন সমস্যার তালিকা কোনও গণনাযোগ্য সমাধান ছাড়াই সমস্যার অতিরিক্ত উদাহরণ দেয়।

গাণিতিক নির্মাণগুলি কার্যকরভাবে সম্পাদন করা যেতে পারে এমন অধ্যয়নকে কখনও কখনও বলা হয় পুনরাবৃত্তিমূলক গণিত; পুনরাবৃত্ত গণিতের হ্যান্ডবুক এই ক্ষেত্রের অনেকগুলি পরিচিত ফলাফল কভার করে।

টুরিং কম্পিউটেবিলিটি

কম্পিউটেবিলিটি তত্ত্বে অধ্যয়ন করা কম্পিউটেবিলিটির প্রধান ফর্মটি 1936 সালে টুরিং দ্বারা প্রবর্তিত হয়েছিল। প্রাকৃতিক সংখ্যার একটি সেটকে গণনাযোগ্য সেট বলা হয় (যাকে সিদ্ধান্তগ্রহণযোগ্য, পুনরাবৃত্ত বা টুরিং কম্পিউটেবল সেটও বলা হয়) যদি একটি টুরিং মেশিন থাকে যা একটি সংখ্যা এন দেওয়া হলে আউটপুট ১ দিয়ে থেমে যায় যদি এন সেটের মধ্যে থাকে এবং এন সেটটিতে না থাকলে আউটপুট ০ দিয়ে থামে। প্রাকৃতিক সংখ্যা থেকে প্রাকৃতিক সংখ্যায় একটি ফাংশন এফ একটি (টুরিং) গণনাযোগ্য, বা পুনরাবৃত্ত ফাংশন যদি কোনও টুরিং মেশিন থাকে যা ইনপুট এন-এ আউটপুট এফ (এন) থামিয়ে দেয় এবং ফেরত দেয়। এখানে টুরিং মেশিনের ব্যবহার প্রয়োজনীয় নয়; গণনার আরও অনেক গুলি মডেল রয়েছে যা টুরিং মেশিনের মতো একই কম্পিউটিং শক্তি রয়েছে; উদাহরণস্বরূপ, আদিম পুনরাবৃত্তি থেকে প্রাপ্ত μ-পুনরাবৃত্ত ফাংশন এবং μ অপারেটর।

কম্পিউটেবল ফাংশন এবং সেটগুলির জন্য পরিভাষাটি সম্পূর্ণরূপে মানসম্মত নয়। μ-পুনরাবৃত্ত ফাংশনগুলির সংজ্ঞার পাশাপাশি গোডেল কর্তৃক রেকুরসিভ ফাংশনগুলির একটি ভিন্ন সংজ্ঞা টুরিং মেশিন দ্বারা গণনাযোগ্য সেট এবং ফাংশনগুলির জন্য প্রচলিত নামটি পুনরাবৃত্তির দিকে পরিচালিত করে। সিদ্ধান্তযোগ্য শব্দটি জার্মান শব্দ এন্টশেইডুংস সমস্যা থেকে উদ্ভূত হয়েছে যা টুরিং এবং অন্যান্যদের মূল কাগজগুলিতে ব্যবহৃত হয়েছিল। সমসাময়িক ব্যবহারে, "কম্পিউটেবল ফাংশন" শব্দটির বিভিন্ন সংজ্ঞা রয়েছে: নাইজেল জে কাটল্যান্ডের মতে, এটি একটি আংশিক পুনরাবৃত্ত ফাংশন (যা কিছু ইনপুটগুলির জন্য অসংজ্ঞায়িত হতে পারে), যখন রবার্ট আই সোয়ারের মতে এটি একটি সম্পূর্ণ পুনরাবৃত্ত (সমতুল্য, সাধারণ পুনরাবৃত্ত) ফাংশন। এই নিবন্ধটি এই কনভেনশনগুলির দ্বিতীয়টি অনুসরণ করে। 1996 সালে, পরিভাষা সম্পর্কে অতিরিক্ত মন্তব্য করেছিলেন।

প্রাকৃতিক সংখ্যার প্রতিটি সেট গণনাযোগ্য নয়। থেমে যাওয়া সমস্যা, যা ইনপুট 0 এ থেমে থাকা টুরিং মেশিনগুলির (বিবরণ) সেট, একটি অগণনাযোগ্য সেটের একটি সুপরিচিত উদাহরণ। অনেকগণনাযোগ্য সেটের অস্তিত্ব এই তথ্য থেকে অনুসরণ করা হয় যে কেবলমাত্র অনেকগুলি টুরিং মেশিন রয়েছে এবং এইভাবে কেবল মাত্র অনেকগুলি গণনাযোগ্য সেট রয়েছে, তবে ক্যান্টরের উপপাদ্য অনুসারে, প্রাকৃতিক সংখ্যার অগণিত অনেকগুলি সেট রয়েছে।

যদিও থামানোর সমস্যাটি গণনাযোগ্য নয়, প্রোগ্রাম সম্পাদন অনুকরণ করা এবং থেমে থাকা প্রোগ্রামগুলির একটি অসীম তালিকা তৈরি করা সম্ভব। সুতরাং থেমে যাওয়া সমস্যাটি একটি গণনাযোগ্য গণনাযোগ্য (যেমন) সেটের একটি উদাহরণ, যা একটি সেট যা একটি টুরিং মেশিন দ্বারা গণনা করা যেতে পারে (গণনাযোগ্য গণনার জন্য অন্যান্য পদগুলির মধ্যে পুনরাবৃত্তভাবে গণনাযোগ্য এবং আধা-সিদ্ধান্তযোগ্য অন্তর্ভুক্ত রয়েছে)। সমতুল্যভাবে, একটি সেট যদি এবং কেবল মাত্র যদি এটি কিছু গণনাযোগ্য ফাংশনের পরিসীমা হয়। সিই সেটগুলি, যদিও সাধারণভাবে সিদ্ধান্তগ্রহণযোগ্য নয়, কম্পিউটেবিলিটি তত্ত্বে বিস্তারিতভাবে অধ্যয়ন করা হয়েছে।

গবেষণার ক্ষেত্রসমূহ

উপরে বর্ণিত কম্পিউটেবল সেট এবং ফাংশনগুলির তত্ত্ব দিয়ে শুরু করে, কম্পিউটেবিলিটি তত্ত্বের ক্ষেত্রটি অনেক ঘনিষ্ঠভাবে সম্পর্কিত বিষয়গুলির অধ্যয়ন কে অন্তর্ভুক্ত করে। এগুলি গবেষণার স্বতন্ত্র ক্ষেত্র নয়: এই ক্ষেত্রগুলির প্রতিটি অন্যদের কাছ থেকে ধারণা এবং ফলাফল গুলি আঁকে এবং বেশিরভাগ কম্পিউটেবিলিটি তাত্ত্বিকরা তাদের বেশিরভাগের সাথে পরিচিত।

আপেক্ষিক কম্পিউটেবিলিটি এবং টুরিং ডিগ্রী

গাণিতিক যুক্তিবিজ্ঞানে কম্পিউটেবিলিটি তত্ত্ব ঐতিহ্যগতভাবে আপেক্ষিক কম্পিউটেবিলিটির উপর দৃষ্টি নিবদ্ধ করেছে, ওরাকল টুরিং মেশিন ব্যবহার করে সংজ্ঞায়িত টুরিং কম্পিউটেবিলিটির একটি সাধারণীকরণ, যা 1939 সালে টুরিং দ্বারা প্রবর্তিত হয়েছিল। ওরাকল টুরিং মেশিন একটি কাল্পনিক ডিভাইস যা নিয়মিত টুরিং মেশিনের ক্রিয়াসম্পাদন করার পাশাপাশি একটি ওরাকলের প্রশ্ন জিজ্ঞাসা করতে সক্ষম, যা প্রাকৃতিক সংখ্যার একটি নির্দিষ্ট সেট। ওরাকল মেশিন শুধুমাত্র "এন কি ওরাকল সেটে আছে?" ফর্মের প্রশ্ন জিজ্ঞাসা করতে পারে। প্রতিটি প্রশ্নের অবিলম্বে সঠিকভাবে উত্তর দেওয়া হবে, এমনকি ওরাকল সেটটি গণনাযোগ্য না হলেও। সুতরাং একটি অগণনাযোগ্য ওরাকল সহ একটি ওরাকল মেশিন সেটগুলি গণনা করতে সক্ষম হবে যা ওরাকল ছাড়া একটি টুরিং মেশিন করতে পারে না।

অনানুষ্ঠানিকভাবে, প্রাকৃতিক সংখ্যা A এর একটি সেট একটি সেট B-এর সাথে তুলনা করা হয় যদি একটি ওরাকল মেশিন থাকে যা সঠিকভাবে বলে যে ওরাকল সেট হিসাবে B-এর সাথে চলার সময় সংখ্যাগুলি A-তে রয়েছে কিনা (এই ক্ষেত্রে, সেট A কে B থেকে (তুলনামূলকভাবে) গণনাযোগ্য এবং B-এ পুনরাবৃত্ত বলা হয়)। যদি একটি সেট এ একটি সেট বি এর সাথে টুরিং রিডুসিবল হয় এবং বি টিউরিংকে এ-এর সাথে পুনরায় সংযুক্ত করা হয় তবে সেটগুলির একই টুরিং ডিগ্রি রয়েছে (যাকে অসমাধানযোগ্যতার ডিগ্রিও বলা হয়)। একটি সেটের টুরিং ডিগ্রি সেটটি কতটা গণনাযোগ্য তার একটি সুনির্দিষ্ট পরিমাপ দেয়।

গণনাযোগ্য নয় এমন সেটগুলির প্রাকৃতিক উদাহরণগুলির মধ্যে অনেকগুলি বিভিন্ন সেট রয়েছে যা থামানো সমস্যার রূপগুলিকে এনকোড করে, দুটি সাধারণ বৈশিষ্ট্য রয়েছে:

এগুলি গণনাযোগ্যভাবে গণনাযোগ্য, এবং
প্রতিটি কে একাধিক হ্রাসের মাধ্যমে অন্য যে কোনও ভাষায় অনুবাদ করা যেতে পারে। অর্থাৎ, এই ধরনের সেট A এবং B দেওয়া হলে, একটি মোট গণনাযোগ্য ফাংশন f রয়েছে যেমন A = {x : f(x) ∈ B}। এই সেটগুলিকে একাধিক-এক সমতুল্য (বা এম-সমতুল্য) বলা হয়।

টুরিং হ্রাসের তুলনায় অনেক-এক হ্রাস "শক্তিশালী" হয়: যদি একটি সেট এ একটি সেট বি-এর সাথে একাধিক-এক রিডুসিবল হয়, তবে এ হ'ল টুরিং কে বি-এর সাথে তুলনা করা যায়, তবে বিপরীতটি সর্বদা ধরে রাখে না। যদিও অগণনাযোগ্য সেটগুলির প্রাকৃতিক উদাহরণগুলি অনেকগুলি-এক সমতুল্য, তবে গণনাযোগ্যভাবে গণনাযোগ্য সেট এ এবং বি তৈরি করা সম্ভব যাতে এ টিউরিং কে বি-এর সাথে তুলনা করা যায় তবে অনেকগুলি বি-এর সাথে তুলনা করা যায় না। এটি দেখানো যেতে পারে যে প্রতিটি গণনাযোগ্য গণনাযোগ্য সেটটি থামানোর সমস্যার সাথে অনেক-এক-এক সম্পর্কিত, এবং এইভাবে থেমে যাওয়া সমস্যাটি বহু-এক পুনরুত্পাদনযোগ্যতা এবং টুরিং রিডুসিবিলিটির ক্ষেত্রে সবচেয়ে জটিল গণনাযোগ্য সেট। 1944 সালে, পোস্ট জিজ্ঞাসা করেছিলেন যে প্রতিটি গণনাযোগ্য গণনাযোগ্য সেটটি থামানোর সমস্যার সমতুল্য বা টুরিং সমতুল্য কিনা, অর্থাৎ, এই দুটির মধ্যে টুরিং ডিগ্রি ইন্টারমিডিয়েট সহ কোনও গণনাযোগ্য গণনাযোগ্য সেট নেই কিনা।

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

অগণিত অনেক গুলি সেট রয়েছে যা গণনাযোগ্যভাবে গণনাযোগ্য নয়, এবং সমস্ত সেটের টুরিং ডিগ্রিগুলির তদন্ত গণনাযোগ্য গণনাযোগ্য টুরিং ডিগ্রিগুলির তদন্তের মতোই কম্পিউটেবিলিটি তত্ত্বে কেন্দ্রীয়। বিশেষ বৈশিষ্ট্যযুক্ত অনেকগুলি ডিগ্রি নির্মিত হয়েছিল: হাইপারইমিউন-মুক্ত ডিগ্রী যেখানে সেই ডিগ্রির তুলনায় গণনাযোগ্য প্রতিটি ফাংশন একটি (অসম্পর্কিত) গণনাযোগ্য ফাংশন দ্বারা প্রধানকরা হয়; উচ্চ ডিগ্রী যার তুলনায় কেউ একটি ফাংশন এফ গণনা করতে পারে যা প্রতিটি গণনাযোগ্য ফাংশন জিকে এই অর্থে প্রভাবিত করে যে জি এর উপর নির্ভর করে একটি ধ্রুবক সি রয়েছে যেমন সমস্ত এক্স > সি এর জন্য জি (এক্স) < এফ (এক্স); অ্যালগরিদমগতভাবে এলোমেলো সেট ধারণকারী এলোমেলো ডিগ্রী; 1-জেনেরিক সেটগুলির 1-জেনেরিক ডিগ্রি; এবং সীমা-গণনাযোগ্য সেটগুলির থামানোর সমস্যার নীচের ডিগ্রী।

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

টুরিং ডিগ্রীর উপর সাম্প্রতিক গবেষণায় টুরিং ডিগ্রীর সেটের সামগ্রিক কাঠামো এবং টুরিং ডিগ্রীর সেটের উপর দৃষ্টি নিবদ্ধ করা হয়েছে যার মধ্যে গণনাযোগ্য সেট রয়েছে। শোর এবং স্ল্যামানের একটি গভীর উপপাদ্য বলে যে ফাংশনটি টুরিং ডিগ্রীর আংশিক ক্রমঅনুসারে একটি ডিগ্রী এক্স থেকে তার টুরিং জাম্পের ডিগ্রী পর্যন্ত ম্যাপিং করা যায়। অ্যাম্বোস-স্পাইস এবং ফেজারের একটি জরিপ এই গবেষণা এবং এর ঐতিহাসিক অগ্রগতির একটি সংক্ষিপ্ত বিবরণ দেয়।

অন্যান্য পুনরুদ্ধার

কম্পিউটেবিলিটি থিওরিতে গবেষণার একটি চলমান ক্ষেত্র টুরিং রিডুসিবিলিটি ব্যতীত অন্যান্য পুনরুত্পাদনশীলতা সম্পর্ক অধ্যয়ন করে। পোস্ট বেশ কয়েকটি শক্তিশালী পুনরুদ্ধার প্রবর্তন করেছে, তাই নামকরণ করা হয়েছে কারণ তারা সত্য-সারণী পুনরুদ্ধারযোগ্যতা বোঝায়। একটি শক্তিশালী রিডুসিবিলিটি বাস্তবায়নকারী একটি টুরিং মেশিন এটি কোন ওরাকলের সাথে উপস্থাপিত হয় তা নির্বিশেষে একটি মোট ফাংশন গণনা করবে। দুর্বল পুনরুদ্ধারগুলি হ'ল যেখানে সমস্ত ওরাকলগুলির জন্য হ্রাস প্রক্রিয়া শেষ নাও হতে পারে; টুরিং রিডুসিবিলিটি একটি উদাহরণ।

শক্তিশালী পুনরুদ্ধারের মধ্যে রয়েছে:

এক-এক পুনরুদ্ধারযোগ্যতা: যদি মোট গণনাযোগ্য ইনজেকটিভ ফাংশন এফ থাকে তবে A হল B-এর এক-এক রিডুসিবল (বা 1-রিডুসিবল) যদি প্রতিটি n A-এ থাকে যদি f(n) B-এ থাকে।

বহু-এক পুনরুদ্ধারযোগ্যতা: এটি মূলত ইনজেকটিভ হওয়ার সীমাবদ্ধতা ছাড়াই এক-এক পুনরুদ্ধারযোগ্যতা। যদি একটি মোট গণনাযোগ্য ফাংশন এফ থাকে যেমন প্রতিটি n যদি A-এ থাকে এবং কেবলমাত্র যদি f(n) B-এ থাকে তবে A-কে B-এর সাথে একাধিক-একরূপে (বা এম-রিডুসিবল) বলা হয়।

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

আরও পুনরুদ্ধার (ইতিবাচক, বিভাজনমূলক, কনজেক্টিভ, রৈখিক এবং তাদের দুর্বল এবং সীমাবদ্ধ সংস্করণ) নিবন্ধ হ্রাস (কম্পিউটেবিলিটি তত্ত্ব) এ আলোচনা করা হয়েছে।

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

টুরিং রিডুসিবিলিটির চেয়ে দুর্বল রিডুসিবিলিটি (অর্থাৎ, টুরিং রিডুসিবিলিটি দ্বারা নির্দেশিত রিডুসিবিলিটি) এছাড়াও অধ্যয়ন করা হয়েছে। সর্বাধিক সুপরিচিত হ'ল গাণিতিক পুনরুদ্ধারযোগ্যতা এবং হাইপারারিদ্মেটিক রিডুসিবিলিটি। এই পুনরুদ্ধারগুলি গাণিতিক স্ট্যান্ডার্ড মডেলের উপর নিষ্ক্রিয়তার সাথে ঘনিষ্ঠভাবে সংযুক্ত।

রাইসের উপপাদ্য এবং গাণিতিক শ্রেণিবিন্যাস

রাইস দেখিয়েছেন যে প্রতিটি ন্যূনতম শ্রেণী সি এর জন্য (যার মধ্যে কিছু কিন্তু সমস্ত সি ই সেট নেই) ইনডেক্স সেট ই = {e: eth c.e. সেট W_e C}-এ রয়েছে} এর বৈশিষ্ট্য হল যে থেমে যাওয়া সমস্যা বা এর পরিপূরকটি E-এর সাথে একাধিক-এক হ্রাস ব্যবহার করে ম্যাপ করা যেতে পারে (রাইসের উপপাদ্য দেখুন)। আরও বিস্তারিত জানার জন্য)। তবে, এই সূচক সেটগুলির মধ্যে অনেকগুলি থামানোর সমস্যার চেয়েও জটিল। এই ধরণের সেটগুলি গাণিতিক শ্রেণিবিন্যাস ব্যবহার করে শ্রেণিবদ্ধ করা যেতে পারে। উদাহরণস্বরূপ, সমস্ত সীমিত সেটের শ্রেণীর ইনডেক্স সেট এফআইএন 2 স্তরে_{রয়েছে, সমস্ত} পুনরাবৃত্ত সেটের শ্রেণীর সূচক সেট আরইসি₃ স্তরে রয়েছে, সমস্ত কোফিন সেটের সূচক সেট কোফিনও 3 স্তরে_{রয়েছে এবং} সূচক সেট সিওপি সমস্ত টুরিং-সম্পূর্ণ সেটগুলির শ্রেণীর সিএমপি₄। এই শ্রেণিবিন্যাস স্তরগুলি ইনডাকটিভভাবে সংজ্ঞায়িত করা হয়, Σ_{n + 1} এ কেবল মাত্র সমস্ত সেট রয়েছে যা Σ_n এর তুলনায় গণনাযোগ্য; Σ_1-এ গণনাযোগ্য গণনাযোগ্য সেট রয়েছে। এখানে প্রদত্ত ইনডেক্স সেটগুলি এমনকি তাদের স্তরের জন্য সম্পূর্ণ, অর্থাৎ, এই স্তরের সমস্ত সেটগুলি প্রদত্ত সূচক সেটগুলিতে অনেকগুলি হ্রাস করা যেতে পারে।

বিপরীত গণিত

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

সংখ্যা

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

অগ্রাধিকার পদ্ধতি

অগ্রাধিকার পদ্ধতি নামে একটি পদ্ধতি দিয়ে পোস্টের সমস্যার সমাধান করা হয়েছিল; এই পদ্ধতিটি ব্যবহার করে একটি প্রমাণকে অগ্রাধিকার যুক্তি বলা হয়। এই পদ্ধতিটি প্রাথমিকভাবে নির্দিষ্ট বৈশিষ্ট্যগুলির সাথে গণনাযোগ্য সেট গুলি তৈরি করতে ব্যবহৃত হয়। এই পদ্ধতিটি ব্যবহার করার জন্য, নির্মিত সেটের পছন্দসই বৈশিষ্ট্যগুলি লক্ষ্যগুলির একটি অসীম তালিকায় বিভক্ত করা হয়, যা প্রয়োজনীয়তা হিসাবে পরিচিত, যাতে সমস্ত প্রয়োজনীয়তা পূরণ ের ফলে নির্মিত সেটটিতে কাঙ্ক্ষিত বৈশিষ্ট্য থাকে। প্রতিটি প্রয়োজনীয়তা প্রয়োজনীয়তার অগ্রাধিকারের প্রতিনিধিত্বকারী একটি প্রাকৃতিক সংখ্যাকে বরাদ্দ করা হয়; সুতরাং 0 কে সবচেয়ে গুরুত্বপূর্ণ অগ্রাধিকার দেওয়া হয়, 1 কে দ্বিতীয় সর্বাধিক গুরুত্বপূর্ণ অগ্রাধিকার দেওয়া হয়, ইত্যাদি। তারপরে সেটটি পর্যায়ক্রমে নির্মিত হয়, প্রতিটি পর্যায় সেটটিতে সংখ্যা যুক্ত করে বা সেট থেকে সংখ্যাগুলি নিষিদ্ধ করে আরও প্রয়োজনীয়তাগুলির মধ্যে একটি পূরণ করার চেষ্টা করে যাতে চূড়ান্ত সেটটি প্রয়োজনীয়তা পূরণ করে। এটি ঘটতে পারে যে একটি প্রয়োজনীয়তা পূরণ করা অন্যটি অসন্তুষ্ট হওয়ার কারণ হবে; অগ্রাধিকার আদেশটি এই জাতীয় ইভেন্টে কী করতে হবে তা সিদ্ধান্ত নিতে ব্যবহৃত হয়।

কম্পিউটেবিলিটি তত্ত্বের অনেক গুলি সমস্যা সমাধানের জন্য অগ্রাধিকারযুক্তিগুলি নিযুক্ত করা হয়েছে এবং তাদের জটিলতার উপর ভিত্তি করে শ্রেণিবিন্যাসে শ্রেণিবদ্ধ করা হয়েছে। যেহেতু জটিল অগ্রাধিকার যুক্তিগুলি প্রযুক্তিগত এবং অনুসরণ করা কঠিন হতে পারে, তাই ঐতিহ্যগতভাবে অগ্রাধিকার যুক্তি ছাড়াই ফলাফল প্রমাণ করা বা অগ্রাধিকারযুক্তি দিয়ে প্রমাণিত ফলাফলগুলি তাদের ছাড়াই প্রমাণিত হতে পারে কিনা তা দেখা বাঞ্ছনীয় বলে বিবেচিত হয়েছে। উদাহরণস্বরূপ, কুমার অগ্রাধিকার পদ্ধতি ব্যবহার না করে ফ্রাইডবার্গ নম্বরিংয়ের অস্তিত্বের প্রমাণের উপর একটি গবেষণাপত্র প্রকাশ করেছিলেন।

গণনাযোগ্য সেটগুলির জালি

পোস্ট যখন একটি সাধারণ সেটের ধারণাটিকে অসীম পরিপূরক সহ একটি সিই সেট হিসাবে সংজ্ঞায়িত করেছিলেন যা কোনও অসীম সিই সেট ধারণ করে না, তখন তিনি অন্তর্ভুক্তির অধীনে গণনাযোগ্য গণনাযোগ্য সেটগুলির কাঠামো অধ্যয়ন শুরু করেছিলেন। এই জালিটি একটি ভাল ভাবে অধ্যয়ন করা কাঠামো হয়ে ওঠে। কম্পিউটেবল সেটগুলি এই কাঠামোতে মৌলিক ফলাফল দ্বারা সংজ্ঞায়িত করা যেতে পারে যে কোনও সেট গণনাযোগ্য হয় যদি এবং কেবল মাত্র যদি সেট এবং তার পরিপূরক উভয়ই গণনাযোগ্য হয়। অসীম সি.ই. সেটগুলিতে সর্বদা অসীম গণনাযোগ্য সাবসেট থাকে; তবে অন্যদিকে, সাধারণ সেটগুলি বিদ্যমান তবে সর্বদা একটি কয়েনফিমিটেবল সুপারসেট থাকে না। পোস্ট ইতিমধ্যে হাইপারসিম্পল এবং হাইপারহাইপারসিম্পল সেট চালু করেছে; পরবর্তীতে সর্বাধিক সেট গুলি তৈরি করা হয়েছিল যা সিই সেটগুলি এমন যে প্রতিটি সিই সুপারসেট হয় প্রদত্ত সর্বাধিক সেটের একটি সীমিত রূপ বা সহ-সীমাবদ্ধ। এই জালির অধ্যয়নে পোস্টের মূল অনুপ্রেরণা ছিল এমন একটি কাঠামোগত ধারণা খুঁজে বের করা যাতে এই বৈশিষ্ট্যটি সন্তুষ্ট করে এমন প্রতিটি সেট গণনাযোগ্য সেটের টুরিং ডিগ্রিতে বা থামানো সমস্যার টুরিং ডিগ্রিতে নেই। পোস্ট এই জাতীয় সম্পত্তি খুঁজে পায়নি এবং তার সমস্যার সমাধান পরিবর্তে অগ্রাধিকার পদ্ধতি প্রয়োগ করেছিল; 1991 সালে, হ্যারিংটন এবং অবশেষে এই জাতীয় সম্পত্তি খুঁজে পেয়েছিলেন।

অটোমরফিজম সমস্যা

আরেকটি গুরুত্বপূর্ণ প্রশ্ন হ'ল কম্পিউটেবিলিটি-তাত্ত্বিক কাঠামোতে অটোমরফিজমের অস্তিত্ব। এই কাঠামোগুলির মধ্যে একটি হ'ল অন্তর্ভুক্তি মোডুলো সীমিত পার্থক্যের অধীনে গণনাযোগ্য সেটগুলির মধ্যে একটি; এই কাঠামোতে, A B এর নীচে থাকে যদি এবং শুধুমাত্র যদি সেট পার্থক্য B − A সীমাবদ্ধ হয়। সর্বাধিক সেটগুলির (পূর্ববর্তী অনুচ্ছেদে সংজ্ঞায়িত হিসাবে) বৈশিষ্ট্য রয়েছে যে তারা অ-সর্বাধিক সেটগুলিতে অটোমরফিক হতে পারে না, অর্থাৎ, যদি কেবল উল্লিখিত কাঠামোর অধীনে গণনাযোগ্য গণনাযোগ্য সেটগুলির অটোমরফিজম থাকে তবে প্রতিটি সর্বাধিক সেটটি অন্য সর্বাধিক সেটটিতে ম্যাপ করা হয়। 1974 সালে, দেখিয়েছিলেন যে বিপরীতটিও ধরে রাখে, অর্থাৎ, প্রতি দুটি সর্বাধিক সেট অটোমরফিক। সুতরাং সর্বাধিক সেটগুলি একটি কক্ষপথ গঠন করে, অর্থাৎ, প্রতিটি অটোমরফিজম সর্বাধিকতা সংরক্ষণ করে এবং যে কোনও দুটি সর্বাধিক সেট কিছু অটোমরফিজম দ্বারা একে অপরের মধ্যে রূপান্তরিত হয়। হ্যারিংটন একটি অটোমর্ফিক সম্পত্তির আরও একটি উদাহরণ দিয়েছিলেন: সৃজনশীল সেটগুলির, সেটগুলি যা থামানোর সমস্যার সমতুল্য।

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

কলমোগোরভ জটিলতা

কোলমোগোরভ জটিলতা এবং অ্যালগরিদমিক এলোমেলোতার ক্ষেত্রটি 1960 এবং 1970 এর দশকে চৈটিন, কলমোগোরভ, লেভিন, মার্টিন-লোফ এবং সলোমনফ দ্বারা বিকশিত হয়েছিল (নামগুলি এখানে বর্ণানুক্রমিক ক্রমে দেওয়া হয়েছে; বেশিরভাগ গবেষণা স্বাধীন ছিল, এবং এলোমেলোতার ধারণার ঐক্য তখন বোঝা যায়নি)। মূল ধারণাটি হ'ল একটি সার্বজনীন টুরিং মেশিন ইউ বিবেচনা করা এবং একটি সংখ্যা (বা স্ট্রিং) এক্সের জটিলতাকে সংক্ষিপ্ততম ইনপুট পি এর দৈর্ঘ্য হিসাবে পরিমাপ করা যেমন ইউ (পি) আউটপুট এক্স। এই পদ্ধতিটি সীমাবদ্ধ বস্তুর জন্য এলোমেলোতার ধারণাটি প্রয়োগ করে একটি অসীম ক্রম (সমতুল্য, প্রাকৃতিক সংখ্যার একটি উপসেটের বৈশিষ্ট্যগত ফাংশন) এলোমেলো কিনা তা নির্ধারণের পূর্ববর্তী উপায়গুলিতে বিপ্লব ঘটিয়েছিল। কোলমোগোরভ জটিলতা কেবল স্বাধীন অধ্যয়নের বিষয় হয়ে ওঠেনি তবে প্রমাণ প্রাপ্তির সরঞ্জাম হিসাবে অন্যান্য বিষয়গুলিতেও প্রয়োগ করা হয়। এই অঞ্চলে এখনও অনেক উন্মুক্ত সমস্যা রয়েছে। এই কারণে, এই অঞ্চলে একটি সাম্প্রতিক গবেষণা সম্মেলন জানুয়ারী 2007 এ অনুষ্ঠিত হয়েছিল এবং উন্মুক্ত সমস্যার একটি তালিকা জোসেফ মিলার এবং আন্দ্রে নাইস দ্বারা রক্ষণাবেক্ষণ করা হয়।

ফ্রিকোয়েন্সি গণনা

কম্পিউটেবিলিটি তত্ত্বের এই শাখাটি নিম্নলিখিত প্রশ্নটি বিশ্লেষণ করেছে: 0 < মি < এন সহ স্থির এম এবং এন এর জন্য, যার জন্য ফাংশন A যে কোনও ভিন্ন এন ইনপুট x₁, x₂, ..., x_n এর জন্য গণনা করা সম্ভব। x_k) = y_k সত্য। এই ধরনের সেটগুলি (এম, এন) -পুনরাবৃত্ত সেট হিসাবে পরিচিত। কম্পিউটেবিলিটি তত্ত্বের এই শাখার প্রথম প্রধান ফলাফল হ'ল ট্র্যাকটেনব্রোটের ফলাফল যে একটি সেট গণনাযোগ্য হয় যদি এটি কিছু এম, এন এবং1 মি > এন এর জন্য পুনরাবৃত্ত হয়। অন্যদিকে, জোকুশের আধা-পুনরাবৃত্তিমূলক সেটগুলি (যা জোকুশ 2 সালে চালু করার আগে অনানুষ্ঠানিকভাবে পরিচিত ছিল) এমন একটি সেটের উদাহরণ যা (এম, এন) -পুনরাবৃত্ত হয় যদি এবং কেবল মাত্র যদি 2মি < এন + 1968 হয়। এই সেটগুলির মধ্যে অগণিত অনেকগুলি রয়েছে এবং এই ধরণের কিছু গণনাযোগ্য তবে অগণনাযোগ্য সেটও রয়েছে। পরে, ডেগটেভ গণনাযোগ্য গণনাযোগ্য সেটগুলির একটি শ্রেণিবিন্যাস প্রতিষ্ঠা করেছিলেন যা (2, এন + 1) -পুনরাবৃত্ত কিন্তু (1, এন) -পুনরাবৃত্ত নয়। রাশিয়ান বিজ্ঞানীদের দীর্ঘ গবেষণার পরে, এই বিষয়টি পশ্চিমে সীমাবদ্ধ প্রশ্নগুলির উপর বেইগেলের থিসিস দ্বারা পুনরায় জনপ্রিয় হয়ে ওঠে, যা ফ্রিকোয়েন্সি গণনাকে উপরে উল্লিখিত সীমাবদ্ধ পুনরুদ্ধার এবং অন্যান্য সম্পর্কিত ধারণার সাথে যুক্ত করে। এর অন্যতম প্রধান ফলাফল ছিল কুমার'স কার্ডিনালিটি থিওরি, যেখানে বলা হয়েছে যে একটি সেট এ গণনাযোগ্য হয় যদি একটি এন থাকে এবং যদি কিছু অ্যালগরিদম বিভিন্ন সংখ্যার প্রতিটি টুপলের জন্য বিভিন্ন সংখ্যার জন্য গণনা করে এবং এ-এর সাথে সংযুক্ত এন সংখ্যার এই সেটের কার্ডিনালিটির অনেকগুলি সম্ভাব্য পছন্দ পর্যন্ত গণনা করে; এই পছন্দগুলিতে অবশ্যই সত্যিকারের কার্ডিনালিটি থাকতে হবে তবে কমপক্ষে একটি মিথ্যা বাদ দিতে হবে।

ইনডাকটিভ অনুমান

এটি লার্নিং থিওরির কম্পিউটেবিলিটি-তাত্ত্বিক শাখা। এটি 1967 সাল থেকে ই মার্ক গোল্ডের সীমার মধ্যে শেখার মডেলের উপর ভিত্তি করে এবং তখন থেকে শেখার আরও বেশি মডেল বিকাশ করেছে। সাধারণ দৃশ্যটি নিম্নলিখিত: গণনাযোগ্য ফাংশনগুলির একটি শ্রেণি এস দেওয়া হলে, এমন কোনও শিক্ষার্থী (অর্থাৎ, গণনাযোগ্য কার্যকরী) রয়েছে যা ফর্মের যে কোনও ইনপুটের জন্য আউটপুট দেয় (এফ (0), এফ (1), ..., এফ (এন)) একটি হাইপোথিসিস। একজন শিক্ষার্থী এম একটি ফাংশন এফ শিখে যদি প্রায় সমস্ত অনুমান গুলি সমস্ত গণনাযোগ্য ফাংশনগুলির গ্রহণযোগ্য সংখ্যার ক্ষেত্রে পূর্বে সম্মত হয়; M S শিখবে যদি M S-এর প্রতিটি f শিখবে। মৌলিক ফলাফলগুলি হ'ল ফাংশনগুলির সমস্ত গণনাযোগ্য শ্রেণিগুলি শেখা যায় যখন সমস্ত গণনাযোগ্য ফাংশনগুলির ক্লাস আরইসি শেখার যোগ্য নয়। অনেক সম্পর্কিত মডেল বিবেচনা করা হয়েছে এবং ইতিবাচক ডেটা থেকে গণনাযোগ্য গণনাযোগ্য সেটগুলির ক্লাস শেখা একটি বিষয় যা 1967 সাল থেকে গোল্ডের অগ্রণী গবেষণাপত্র থেকে অধ্যয়ন করা হয়েছে।

টুরিং কম্পিউটেবিলিটির সাধারণীকরণ

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

ক্রমাগত কম্পিউটেবিলিটি তত্ত্ব

ডিজিটাল গণনার জন্য কম্পিউটেবিলিটি তত্ত্বটি ভালভাবে বিকশিত হয়েছে। এনালগ কম্পিউটার, এনালগ সিগন্যাল প্রসেসিং, এনালগ ইলেকট্রনিক্স, নিউরাল নেটওয়ার্ক এবং ক্রমাগত-সময় নিয়ন্ত্রণ তত্ত্বে ঘটে এমন অ্যানালগ গণনার জন্য কম্পিউটেবিলিটি তত্ত্বটি কম উন্নত, যা ডিফারেনশিয়াল সমীকরণ এবং ক্রমাগত গতিশীল সিস্টেমদ্বারা মডেল করা হয়। উদাহরণস্বরূপ, ব্লুম-শুব-স্মেল মেশিন মডেলের মতো গণনার মডেলগুলি বাস্তবের উপর গণনাকে আনুষ্ঠানিককরেছে।

ডিফিনিবিলিটি, প্রমাণ এবং কম্পিউটেবিলিটির মধ্যে সম্পর্ক

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

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

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

নাম

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

1967 সালে, রজার্স দিয়েছেন যে কম্পিউটেবিলিটি তত্ত্বের একটি মূল বৈশিষ্ট্য হ'ল এর ফলাফল এবং কাঠামোগুলি প্রাকৃতিক সংখ্যার উপর গণনাযোগ্য বিজেকশনের অধীনে অপরিবর্তনীয় হওয়া উচিত (এই পরামর্শটি জ্যামিতিতে এরলাঙ্গেন প্রোগ্রামের ধারণাগুলির উপর ভিত্তি করে তৈরি করা হয়েছে)। ধারণাটি হ'ল একটি গণনাযোগ্য বিজেকশন সেটের কোনও কাঠামো নির্দেশ করার পরিবর্তে কেবল একটি সেটের সংখ্যার নাম পরিবর্তন করে, যেমন ইউক্লিডীয় সমতলের ঘূর্ণন তার উপর আঁকা রেখাগুলির কোনও জ্যামিতিক দিক পরিবর্তন করে না। যেহেতু যে কোনও দুটি অসীম গণনাযোগ্য সেট একটি গণনাযোগ্য বিজেকশন দ্বারা সংযুক্ত থাকে, এই প্রস্তাবটি সমস্ত অসীম গণনাযোগ্য সেটগুলি সনাক্ত করে (সীমাবদ্ধ গণনাযোগ্য সেটগুলি তুচ্ছ হিসাবে দেখা হয়)। রজার্স এর মতে, কম্পিউটেবিলিটি থিওরিতে আগ্রহের সেটগুলি হ'ল অগণনাযোগ্য সেট, যা প্রাকৃতিক সংখ্যার গণনাযোগ্য বিজেকশন দ্বারা সমতুল্য শ্রেণিতে বিভক্ত।

পেশাদার সংগঠন

কম্পিউটেবিলিটি তত্ত্বের জন্য প্রধান পেশাদার সংগঠন হ'ল অ্যাসোসিয়েশন ফর সিম্বোলিক লজিক, যা প্রতি বছর বেশ কয়েকটি গবেষণা সম্মেলন করে। ইন্টারডিসিপ্লিনারি রিসার্চ অ্যাসোসিয়েশন কম্পিউটেবিলিটি ইন ইউরোপ (সিআইই) বার্ষিক সম্মেলনের একটি সিরিজও আয়োজন করে।

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

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

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

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

তথ্যসূত্র

↑ 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। সংগ্রহের তারিখ ১৮/৩/২০২২। এখানে তারিখের মান পরীক্ষা করুন: |তারিখ=, |সংগ্রহের-তারিখ= (সাহায্য)

[১]

[২]

[৩]