पुनरावर्ती फलन और रजिस्टर मशीनें
पुनरावर्ती फलन सिद्धांत कुछ बुनियादी संक्रियाओं से संगणनीय फलनों का निर्माण करता है, जबकि रजिस्टर मशीनें रजिस्टरों में संग्रहीत पूर्ण संख्याओं के साथ संगणना करती हैं। ये दो मॉडल ट्यूरिंग मशीन को घेरते हैं और संगणनीयता की सुदृढ़ता की पुष्टि करते हैं।
Definition
सामान्य पुनरावर्ती फलन वे हैं जो स्थिरांकों, अनुवर्ती (successor) और प्रक्षेपों (projections) से संयोजन, आदिम पुनरावर्तन और असीमित न्यूनीकरण द्वारा निर्मित होते हैं; रजिस्टर मशीनें अमूर्त उपकरण हैं जो प्राकृतिक संख्याओं को धारण करने वाले रजिस्टरों के एक सीमित सेट की सामग्री को बढ़ाने, घटाने और परीक्षण करके संगणना करते हैं।
Scope
इस विषय में आदिम पुनरावर्ती फलन, सामान्य पुनरावर्ती फलनों को प्राप्त करने के लिए असीमित न्यूनीकरण का समावेश, एक संगणनीय फलन के रूप में एकरमैन फलन जो आदिम पुनरावर्ती नहीं है, रजिस्टर और काउंटर मशीनें तथा उनकी सार्वभौमिकता, और इन सभी मॉडलों की ट्यूरिंग संगणनीयता के साथ समतुल्यता शामिल है।
Core questions
- संगणनीय फलनों को बिना किसी मशीन के अंकगणितीय रूप से कैसे परिभाषित किया जा सकता है?
- आदिम पुनरावर्तन से परे असीमित न्यूनीकरण की आवश्यकता क्यों है?
- सरल रजिस्टर मशीनें संगणना की पूरी शक्ति कैसे प्राप्त करती हैं?
- ये अंकगणितीय और मशीन मॉडल ट्यूरिंग मशीनों के साथ क्यों मेल खाते हैं?
Key theories
- ट्यूरिंग संगणनीयता के साथ समतुल्यता
- सामान्य पुनरावर्ती फलन और रजिस्टर मशीनों द्वारा संगणित फलन ठीक ट्यूरिंग-संगणनीय फलन हैं, जो विशुद्ध रूप से अंकगणितीय और प्राथमिक मशीन शर्तों में परिभाषित मॉडलों के माध्यम से चर्च-ट्यूरिंग थीसिस को सुदृढ़ करते हैं।
- आदिम पुनरावर्तन से परे
- एकरमैन फलन कुल और संगणनीय है फिर भी आदिम पुनरावर्ती होने के लिए बहुत तेजी से बढ़ता है, यह दर्शाता है कि असीमित खोज आवश्यक है और आदिम पुनरावर्ती फलन संगणनीय फलनों का एक उचित उपवर्ग हैं।
- रजिस्टर मशीनों की सार्वभौमिकता
- मिंस्की ने दिखाया कि केवल दो काउंटरों और वृद्धि, कमी और शून्य-परीक्षण के संचालन वाली एक मशीन पहले से ही ट्यूरिंग-पूर्ण है, यह एक चरम प्रदर्शन है कि पूर्ण संगणना के लिए कितनी कम संरचना की आवश्यकता होती है।
Clinical relevance
रजिस्टर मशीनें वास्तविक प्रोसेसरों के पूर्णांक अंकगणित को टेप की तुलना में अधिक सीधे मॉडल करती हैं, आदिम पुनरावर्तन उन प्रोग्रामों के अनुरूप है जो हमेशा समाप्त होते हैं और कुल कार्यात्मक भाषाओं और समाप्ति विश्लेषण का आधार हैं, और पुनरावर्ती-फलन दृष्टिकोण संगणना को गणित की नींव से जोड़ता है।
History
गोडेल और हरब्रांड ने 1930 के दशक की शुरुआत में सामान्य पुनरावर्ती फलनों को परिभाषित किया, और क्लीने ने न्यूनीकरण की भूमिका सहित सिद्धांत विकसित किया। एकरमैन ने पहले अपने तेजी से बढ़ने वाले फलन का प्रदर्शन किया था, और मिंस्की ने 1960 के दशक में रजिस्टर और काउंटर मशीनों की शुरुआत की, यहां तक कि दो-काउंटर मशीनों को भी सार्वभौमिक साबित किया।
Key figures
- Kurt Gödel
- Stephen Kleene
- Wilhelm Ackermann
- Marvin Minsky
Related topics
Seminal works
- cutland1980
- minsky1967
Frequently asked questions
- आदिम पुनरावर्ती और सामान्य पुनरावर्ती फलनों में क्या अंतर है?
- आदिम पुनरावर्ती फलन परिबद्ध लूपों का उपयोग करके निर्मित होते हैं और हमेशा समाप्त होते हैं, लेकिन वे हर संगणनीय फलन को कैप्चर नहीं करते हैं। असीमित न्यूनीकरण को जोड़ने से, एक खोज जो अनिश्चित काल तक चल सकती है, सामान्य पुनरावर्ती फलन प्राप्त होते हैं, जो ठीक ट्यूरिंग-संगणनीय फलनों के साथ मेल खाते हैं।
- केवल दो काउंटरों वाली मशीन कंप्यूटर जितनी शक्तिशाली कैसे हो सकती है?
- मिंस्की ने दिखाया कि प्राकृतिक संख्याओं को धारण करने वाले दो रजिस्टर, केवल वृद्धि, कमी और शून्य-परीक्षण के साथ, अपने टेप को रजिस्टरों में एन्कोड करके एक ट्यूरिंग मशीन का अनुकरण कर सकते हैं। यह निर्माण अत्यधिक अक्षम है, लेकिन यह साबित करता है कि न्यूनतम हार्डवेयर पहले से ही संगणना की पूरी शक्ति तक पहुंच जाता है।