एकरमैन फलन

From Vigyanwiki
Revision as of 10:02, 29 December 2022 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

संगणनीयता सिद्धांत में, विल्हेम एकरमैन के नाम पर एकरमैन फलन, जो सबसे सरल फलन में से एक है[1] और सबसे पहले खोजे गए पूर्ण संगणनीय फलन का उदाहरण है जो कि मूल पुनरावर्ती फलन नहीं हैं। सभी मूल पुनरावर्ती फलन पूर्ण और संगणनीय हैं, लेकिन एकरमैन फलन यह दर्शाता है कि सभी पूर्ण संगणनीय फलन मूल फलन की पुनरावर्ती नहीं हैं। एकरमैन के प्रकाशन के बाद[2] उनके फलन के (जिसमें तीन ऋणोतर पूर्णांक प्राचर थे), कई लेखकों ने इसे विभिन्न उद्देश्यों के अनुरूप संशोधित किया, ताकि एकरमैन फलन मूल फलन के कई रूपों में से किसी को भी संदर्भित कर सके। एक सामान्य संस्करण, दो-प्राचर एकरमैन-पीटर फलन को ऋणोतर पूर्णांक m और n के लिए निम्नानुसार परिभाषित किया गया है:

छोटे आगम के लिए भी इसका मान तेजी से बढ़ता है। उदाहरण के लिए, A(4, 2) 19,729 दशमलव अंकों का पूर्णांक है[3] ( 265536−3 के बराबर, अथवा 22222−3).

इतिहास

1920 के दशक के अंत में, गणितज्ञ गेब्रियल सूडान और विल्हेम एकरमैन, डेविड हिल्बर्ट के छात्र, संगणना की नींव का अध्ययन कर रहे थे। सूडान और एकरमैन दोनों को पूर्ण संगणनीय फलन की खोज के लिए श्रेय दिया जाता है[4] (जिसे कुछ संदर्भों में केवल "पुनरावर्ती" कहा जाता है) जो मूल पुनरावर्ती फलन नहीं हैं। सूडान ने कम प्रसिद्ध सूडान फलन प्रकाशित किया, फिर कुछ ही समय बाद और स्वतंत्र रूप से, 1928 में, एकरमैन ने अपना फलन (ग्रीक अक्षर फ़ाई) प्रकाशित किया। एकरमैन का तीन-प्राचर फलन, , को इस तरह से परिभाषित किया गया है कि यह जैसे , के लिए और यह योग, गुणन और घातांक के बुनियादी परिचालनों का पुनरावृत्त करता है।

और P > 2 के लिए यह इस तरह के बुनियादी परिचालनों को बढ़ाता है जिसकी तुलना अतिसंचालन से की जा सकती है:

( इसकी ऐतिहासिक भूमिका के अलावा यह कुल-गणना योग्य-लेकिन-मूल-पुनरावर्ती फलन के रूप में नहीं, एकरमैन के मूल फलन को घातांक से परे बुनियादी अंकगणितीय संचालन का विस्तार करने के लिए देखा जाता है, हालांकि एकरमैन फलन के रूपांतरों के समान नहीं है जो विशेष रूप से डिज़ाइन किए गए हैं। जैसे कि - रूबेन गुडस्टीन का अतिसंचालन अनुक्रम।)

डेविड हिल्बर्ट ने परिकल्पना की कि एकरमैन फलन अनंत पर,[5] मूल पुनरावर्ती नहीं था, लेकिन यह एकरमैन, हिल्बर्ट के निजी सचिव और पूर्व छात्र थे, जिन्होंने वास्तव में अपने कागज में वास्तविक संख्या के निर्माण पर परिकल्पना को सिद्ध किया था।[2][6]

पीटर रोजसा[7] और राफेल रॉबिन्सन[8] ने बाद में एकरमैन फलन का एक दो-चर संस्करण को विकसित किया जो बाद में लगभग सभी लेखकों द्वारा पसंद किया गया।

सामान्यीकृत अतिसंचालन, उदाहरण - , एकरमैन फलन का भी एक संस्करण है।[9]

1963 में आर.सी. बक अतिसंचालन सीक्वेंस पर एक सहज ज्ञान युक्त दो-चर [n 1]वेरिएंट पर आधारित है:[10][11]

अधिकांश अन्य संस्करणों की तुलना में बक के फलन में कोई अनावश्यक ऑफ़सेट नहीं है:

एकरमैन फलन के कई अन्य संस्करणों का अन्वेषण भी किया गया है।[12]

परिभाषा

परिभाषा: एम-सरणी फलन के रूप में

एकरमैन का मूल तीन-प्राचर फलन ऋणोतर पूर्णांकों तथा के लिए निम्नानुसार पुनरावर्तन परिभाषित किया गया है :

विभिन्न दो-प्राचर संस्करणों में से, पेटर और रॉबिन्सन द्वारा विकसित एक (जिसे अधिकांश लेखकों द्वारा एकरमैन फलन कहा जाता है) को ऋणोतर पूर्णांकों तथा के लिए निम्नलिखित अनुसार परिभाषित किया गया है :

एकरमेन फलन को अतिसंचालन अनुक्रम के संबंध में भी व्यक्त किया गया है:[13][14]

या, नुथ के उच्च-तीर संकेतन में लिखा गया है (पूर्णांक सूचकांक में बढ़ाया गया ):
या, समतुल्य रूप से, बक के फलन F के संदर्भ में:[10]
परिभाषा: पुनरावृत्त 1-सरणी फलन के रूप में परिभाषित करना

के n-वें पुनरावृति के रूप में :

पुनरावृत्त फलन एक निश्चित संख्या में स्वयं के साथ एक फलन बनाने की प्रक्रिया है। फलन रचना एक साहचर्य संक्रिया है, इसलिए .

एकरमैन फलन को एकल फलन के अनुक्रम के रूप में समझा जा सकता है ,यदि हम यह स्थापित कर सके कि .

तब फलन एक एकल [n 2] फलन का अनुक्रम ,होगा जिसे हम पुनरावृत्त फलन से पारिभाषित कर सकते है :


संगणना

एकरमैन फ़ंक्शन की पुनरावर्ती परिभाषा को स्वाभाविक रूप से एक शब्द पुनर्लेखन प्रणाली (टीआरएस) में स्थानांतरित किया जा सकता है।

टीआरएस, 2-सरणी फलन पर आधारित है

2-सरणी एकरमैन फलन की परिभाषा स्पष्ट कटौती नियम की ओर ले जाती है [15][16]

उदाहरण

गणना करने पर

कमी अनुक्रम है [n 3]

बाएँ सबसे बाहरी (एक कदम) नीतिबद्ध:             बांयी ओर-अंतरतम (एक-चरणीय) नीतिबद्ध:
         
         
         
         
         
         

गणना करना कोई स्टैक (अमूर्त डेटा प्रकार) का उपयोग कर सकता है, जिसमें प्रारंभ में तत्व होते हैं .

फिर बार-बार दो शीर्ष तत्वों को नियमों के अनुसार बदल दिया जाता है[n 4]

योजनाबद्ध रूप से, से शुरू :

WHILE stackLength <> 1
{
   POP 2 elements;
   PUSH 1 or 2 or 3 elements, applying the rules r1, r2, r3
}

स्यूडोकोड प्रकाशित हो चुकी है। ग्रॉसमैन & जेटमन (1988).

उदाहरण के लिए, आगम पर ,

स्टैक का विन्यास     कमी को दर्शाना [n 5]
         
         
         
         
         
         
         
         
         
         
         
         
         
         

टिप्पणियां

  • रोसेटा कोड पर 225 कंप्यूटर भाषाओं में सबसे बांयी ओर-अंतरतम नीति लागू की गई है।
  • सभी की गणना के लिए फलन कदम से अधिक नहीं लेता है[17]
  • ग्रॉसमैन & जेटमन (1988) बताया कि स्टैक की गणना में अधिकतम लंबाई , है जब कि .
उनका अपना कलन विधि, स्वाभाविक रूप से पुनरावृत्त, गणना करता है अंदर समय और भीतर स्थान ।
टीआरएस, पुनरावृत्त 1-सरणी फलन पर आधारित है

पुनरावृत्त 1-सरणी एकरमैन फलन की परिभाषा विभिन्न कमी नियमों की ओर ले जाती है

जैसा कि फलन रचना साहचर्य है, नियम r6 के बजाय परिभाषित किया जा सकता है

पिछले खंड की तरह की गणना स्टैक के साथ लागू किया जा सकता है।

प्रारंभ में स्टैक में तीन तत्व होते हैं .

फिर बार-बार तीन शीर्ष तत्वों को नियमों के अनुसार बदल दिया जाता है[n 4]:

योजनाबद्ध रूप से, से शुरू :

WHILE stackLength <> 1
{
   POP 3 elements;
   PUSH 1 or 3 or 5 elements, applying the rules r4, r5, r6;
}

उदाहरण

आगम पर क्रमिक स्टैक विन्यास हैं

संगत समानताएं हैं

जब नियम r6 के बजाय कमी नियम r7 का उपयोग किया जाता है, तो स्टैक में प्रतिस्थापन का पालन किया जाएगा

क्रमिक स्टैक कॉन्फ़िगरेशन तब होगा

संगत समानताएं हैं

टिप्पणियां

  • किसी दिए गए आगम पर अब तक प्रस्तुत टीआरएस ने अभी तक चरणों की एक ही संख्या में एकजुट किया है। वे समान कटौती नियमों का भी उपयोग करते हैं (इस तुलना में नियमों r1, r2, r3 को क्रमशः नियम r4, r5, r6/r7 के समान माना जाता है)। उदाहरण के लिए, एक की कटौती 14 चरणों में अभिसरित होता है: 6 × r1, 3 × r2, 5 × r3। की कमी समान 14 चरणों में अभिसरित होता है: 6 × r4, 3 × r5, 5 × r6/r7। टीआरएस उस क्रम में भिन्न होते हैं जिसमें कमी के नियम लागू होते हैं।
  • कब नियमों का पालन करते हुए {r4, r5, r6} गणना की जाती है, स्टैक की अधिकतम लंबाई के नीचे रहती है जब कमी नियम r6 के स्थान पर कमी नियम r7 का उपयोग किया जाता है, तो स्टैक की अधिकतम लंबाई केवल होती है। स्टैक की लंबाई पुनरावर्ती गहराई को दर्शाती है। नियमों के अनुसार कमी के रूप में {r4, r5, r7} में पुनरावर्तन की एक छोटी अधिकतम गहराई शामिल है,[n 6] यह गणना उस संबंध में अधिक कुशल है।

टीआरएस, हाइपरऑपरेटरों पर आधारित

जैसा सुंदब्लाड (1971) - या पोर्टो & माटोस (1980) - स्पष्ट रूप से दिखाया गया है, एकरमेन फलन अतिसंचालन अनुक्रम के संदर्भ में व्यक्त किया जा सकता है:

या, बक के फलन के संदर्भ में, पैरामीटर सूची से निरंतर 2 को हटाने के बाद

बक का फलन ,[10] एकरमैन फलन का एक भिन्न रूप, जिसकी गणना निम्न कमी नियमों के साथ की जा सकती है:

नियम b6 के स्थान पर नियम को परिभाषित किया जा सकता है

एकरमैन फलन की गणना करने के लिए तीन कटौती नियमों को जोड़ना पर्याप्त है

ये नियम बेस केस A (0, n), संरेखण (n + 3) और फज (-3) का ख्याल रखते हैं।

उदाहरण

गणना करना

कमी नियम के उपयोग से :[n 5]     कमी नियम के उपयोग से :[n 5]
         
         
         
         
         
         
                   
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         

मिलान करने वाली समानताएं हैं

  • जब टीआरएस कटौती नियम के साथ लागू की गई है: