प्रेस्बर्गर अंकगणित: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(3 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Decidable first-order theory of the natural numbers with addition}}
{{Short description|Decidable first-order theory of the natural numbers with addition}}
प्रेस्बर्गर अंकगणित [[प्रथम-क्रम विधेय कलन]] है|जोड़ के साथ [[प्राकृतिक संख्या]]ओं का प्रथम-क्रम सिद्धांत, जिसका नाम मोजेज़ प्रेस्बर्गर के सम्मान में रखा गया है, जिन्होंने इसे 1929 में पेश किया था। प्रेस्बर्गर अंकगणित के [[हस्ताक्षर (गणितीय तर्क)]] में केवल जोड़ संचालन और समानता शामिल है (गणित), गुणन संक्रिया को पूरी तरह से छोड़ दिया गया है। स्वयंसिद्धों में [[गणितीय प्रेरण]] की योजना शामिल है।
'''प्रेस्बर्गर अंकगणित''' मुख्य रूप से [[प्रथम-क्रम विधेय]] का ऐसा कलन है। जिसमें संयोजन के साथ [[प्राकृतिक संख्या|प्राकृतिक संख्याओं]] का प्रथम-क्रम सिद्धांत, जिसका नाम मोजेज़ प्रेस्बर्गर के सम्मान में रखा गया है, जिन्होंने इसे 1929 में प्रस्तुत किया था। प्रेस्बर्गर के आधार पर अंकगणित के [[हस्ताक्षर (गणितीय तर्क)|हस्ताक्षर गणितीय तर्क]] में केवल संयोजन संचालन और समानता सम्मिलित है, इस प्रकार [[गुणन संक्रिया]] को पूर्ण रूप से छोड़ दिया गया है। जिसके कारण स्वयंसिद्धों में [[गणितीय प्रेरण]] की योजना को सम्मिलित किया गया है।


प्रेस्बर्गर अंकगणित [[पीनो अंकगणित]] की तुलना में बहुत कमजोर है, जिसमें जोड़ और [[गुणा]] दोनों ऑपरेशन शामिल हैं। पीनो अंकगणित के विपरीत, प्रेस्बर्गर अंकगणित निर्णायकता (तर्क) है। इसका मतलब यह है कि प्रेस्बर्गर अंकगणित की भाषा में किसी भी वाक्य के लिए एल्गोरिदमिक रूप से यह निर्धारित करना संभव है कि क्या वह वाक्य प्रेस्बर्गर अंकगणित के सिद्धांतों से साबित करने योग्य है। हालाँकि, इस एल्गोरिथ्म के एल्गोरिदम का एसिम्प्टोटिक रनिंग-टाइम विश्लेषण कम से कम [[दोहरा घातीय कार्य]] है, जैसा कि दिखाया गया है {{harvtxt|Fischer|Rabin|1974}}.
प्रेस्बर्गर अंकगणित के आधार पर [[पीनो अंकगणित]] की तुलना में बहुत कमजोर है, जिसमें जोड़ और [[गुणा]] दोनों प्रक्रियाएँ सम्मिलित की गई हैं। इस प्रकार पीनो अंकगणित के विपरीत, प्रेस्बर्गर अंकगणित निर्णायकता तार्किक है। इसका अर्थ यह है कि प्रेस्बर्गर अंकगणित की भाषा में किसी भी वाक्य के लिए कलनिक रूप से यह निर्धारित करना संभव है कि क्या वह वाक्य प्रेस्बर्गर अंकगणित के सिद्धांतों से प्रमाणित करने योग्य है। चूंकि, इस कलन विधि के कलन का एसिम्प्टोटिक रनिंग टाइम विश्लेषण कम से कम [[दोहरा घातीय कार्य]] है, जैसा कि {{harvtxt|फिश्चर|रेबिन|1974}} में दिखाया गया है।


==अवलोकन==
==अवलोकन==
प्रेस्बर्गर अंकगणित की भाषा में स्थिरांक 0 और 1 और बाइनरी फ़ंक्शन + शामिल है, जिसे जोड़ के रूप में व्याख्या किया गया है।
प्रेस्बर्गर अंकगणित की भाषा में स्थिरांक 0 और 1 और बाइनरी फ़ंक्शन + सम्मिलित है, जिसकी मुख्यतः जोड़ के रूप में व्याख्या किया गया है।


इस भाषा में, प्रेस्बर्गर अंकगणित के स्वयंसिद्ध निम्नलिखित के [[सार्वभौमिक समापन]] हैं:
इस भाषा में, प्रेस्बर्गर अंकगणित के स्वयंसिद्ध निम्नलिखित के [[सार्वभौमिक समापन]] इस प्रकार हैं:
# ¬(0 = x + 1)
# ¬(0 = x + 1)
# x + 1 = y + 1 → x = y
# x + 1 = y + 1 → x = y
# एक्स + 0 = एक्स
# x + 0 = x
# x + (y + 1) = (x + y) + 1
# x + (y + 1) = (x + y) + 1
# मान लीजिए P(x) मुक्त चर x (और संभवतः अन्य मुक्त चर) के साथ प्रेस्बर्गर अंकगणित की भाषा में [[प्रथम-क्रम तर्क]]|प्रथम-क्रम सूत्र है। फिर निम्नलिखित सूत्र स्वयंसिद्ध है: (P(0) ∧ ∀x(P(x) → P(x + 1))) → ∀y P(y).
# मान लीजिए P(x) मुक्त चर x और संभवतः अन्य मुक्त चर हैं, जिसके साथ प्रेस्बर्गर अंकगणित की भाषा में [[प्रथम-क्रम तर्क]] या प्रथम-क्रम सूत्र है। फिर निम्नलिखित सूत्र स्वयंसिद्ध है:  
#(P(0) ∧ ∀x(P(x) → P(x + 1))) → ∀y P(y)


(5) [[गणितीय प्रेरण]] की स्वयंसिद्ध स्कीमा है, जो अनंत रूप से कई स्वयंसिद्धों का प्रतिनिधित्व करती है। इन्हें किसी भी सीमित संख्या में स्वयंसिद्धों द्वारा प्रतिस्थापित नहीं किया जा सकता है, अर्थात, प्रेस्बर्गर अंकगणित प्रथम-क्रम तर्क में अंतिम रूप से स्वयंसिद्ध नहीं है।{{sfn|Zoethout|2015|p=8|loc=Theorem 1.2.4.}}
(5) [[गणितीय प्रेरण]] की स्वयंसिद्ध स्कीमा को प्रदर्शित करता है, जो अनंत रूप से कई स्वयंसिद्धों का प्रतिनिधित्व करती है। इन्हें किसी भी सीमित संख्या में स्वयंसिद्धों द्वारा प्रतिस्थापित नहीं किया जा सकता है, अर्थात, प्रेस्बर्गर अंकगणित प्रथम-क्रम तर्क में अंतिम रूप से स्वयंसिद्ध नहीं है।{{sfn|Zoethout|2015|p=8|loc=Theorem 1.2.4.}}


प्रेस्बर्गर अंकगणित को प्रथम-क्रम तर्क#प्रथम-क्रम सिद्धांत, मॉडल और प्राथमिक वर्ग|प्रथम-क्रम सिद्धांत के रूप में देखा जा सकता है, जिसमें समानता के साथ उपरोक्त सिद्धांतों के सभी परिणाम शामिल हैं। वैकल्पिक रूप से, इसे उन वाक्यों के सेट के रूप में परिभाषित किया जा सकता है जो व्याख्या (तर्क)#इच्छित व्याख्याओं में सत्य हैं: स्थिरांक 0, 1 के साथ गैर-नकारात्मक पूर्णांकों की संरचना और गैर-नकारात्मक पूर्णांकों का योग।
प्रेस्बर्गर अंकगणित को प्रथम-क्रम तर्क मुख्य रूप से प्रथम-क्रम सिद्धांत, प्रारूप और प्राथमिक वर्ग या प्रथम-क्रम सिद्धांत के रूप में देखा जा सकता है, जिसमें समानता के साथ उपरोक्त सिद्धांतों के सभी परिणाम सम्मिलित हैं। इस प्रकार वैकल्पिक रूप से इसे उन वाक्यों के समुच्चय के रूप में परिभाषित किया जा सकता है जो तार्किक व्याख्या के आधार पर इच्छित व्याख्याओं में सत्य मान को प्रदर्शित करते हैं: इसके लिए स्थिरांक 0, 1 के साथ गैर-ऋणात्मक पूर्णांकों की संरचना और गैर-ऋणात्मक पूर्णांकों का योग भी सम्मिलित किया जाता हैं।


प्रेस्बर्गर अंकगणित को पूर्ण और निर्णय लेने योग्य बनाया गया है। इसलिए, यह विभाज्यता या मौलिकता, या, अधिक सामान्यतः, चर के गुणन की ओर ले जाने वाली किसी भी संख्या अवधारणा जैसी अवधारणाओं को औपचारिक रूप नहीं दे सकता है। हालाँकि, यह विभाज्यता के व्यक्तिगत उदाहरण तैयार कर सकता है; उदाहरण के लिए, यह सभी x के लिए साबित होता है, y मौजूद है: (y + y = x) ∨ (y + y + 1 = x)यह बताता है कि प्रत्येक संख्या या तो सम या विषम है।
प्रेस्बर्गर अंकगणित को पूर्ण और निर्णय लेने योग्य बनाया गया है। इसलिए यह विभाज्यता या मौलिकता इसके लिए अधिक सामान्य रूप से चर के गुणन की ओर ले जाने वाली किसी भी संख्या अवधारणा को प्रदर्शित करता हैं, इस प्रकार की अवधारणाओं को औपचारिक रूप से नहीं देखा जा सकता है। चूंकि यह विभाज्यता के व्यक्तिगत उदाहरण तैयार कर सकता है, उदाहरण के लिए यह सभी x के लिए प्रमाणित होता है, यहाँ पर y मुख्यतः (y + y = x) ∨ (y + y + 1 = x) रूप में उपस्थित है। यह बताता है कि प्रत्येक संख्या या तो सम या विषम है।


==गुण==
==गुण==
Line 25: Line 26:
* [[संगति प्रमाण]]: प्रेस्बर्गर अंकगणित में ऐसा कोई कथन नहीं है जिसे स्वयंसिद्धों से इस प्रकार निकाला जा सके कि उसका निषेध भी निकाला जा सके।
* [[संगति प्रमाण]]: प्रेस्बर्गर अंकगणित में ऐसा कोई कथन नहीं है जिसे स्वयंसिद्धों से इस प्रकार निकाला जा सके कि उसका निषेध भी निकाला जा सके।
* [[पूर्णता (तर्क)]]: प्रेस्बर्गर अंकगणित की भाषा में प्रत्येक कथन के लिए, या तो इसे स्वयंसिद्धों से निकालना संभव है या इसका निषेध निकालना संभव है।
* [[पूर्णता (तर्क)]]: प्रेस्बर्गर अंकगणित की भाषा में प्रत्येक कथन के लिए, या तो इसे स्वयंसिद्धों से निकालना संभव है या इसका निषेध निकालना संभव है।
* निर्णयशीलता (तर्क): [[कलन विधि]] मौजूद है जो यह तय करता है कि प्रेस्बर्गर अंकगणित में दिया गया कोई भी कथन प्रमेय है या गैर-प्रमेय है।
* निर्णयशीलता (तर्क): [[कलन विधि]] उपस्थित है जो यह तय करता है कि प्रेस्बर्गर अंकगणित में दिया गया कोई भी कथन प्रमेय है या गैर-प्रमेय है।


प्रेस्बर्गर अंकगणित की निर्णायकता को अंकगणितीय सर्वांगसमता के बारे में तर्क द्वारा पूरक, क्वांटिफायर उन्मूलन का उपयोग करके दिखाया जा सकता है।{{sfn|Presburger|1929}}{{sfn|Monk|2012|p=240}}{{sfn|Nipkow|2010}}{{sfn|Enderton|2001|p=188}} क्वांटिफ़ायर एलिमिनेशन एल्गोरिदम को उचित ठहराने के लिए उपयोग किए जाने वाले चरणों का उपयोग पुनरावर्ती स्वयंसिद्धीकरणों को परिभाषित करने के लिए किया जा सकता है जिनमें आवश्यक रूप से प्रेरण की स्वयंसिद्ध स्कीमा शामिल नहीं होती है।{{sfn|Presburger|1929}}{{sfn|Stansifer|1984}}
प्रेस्बर्गर अंकगणित की निर्णायकता को अंकगणितीय सर्वांगसमता के बारे में तर्क द्वारा पूरक, क्वांटिफायर उन्मूलन का उपयोग करके दिखाया जा सकता है।{{sfn|Presburger|1929}}{{sfn|Monk|2012|p=240}}{{sfn|Nipkow|2010}}{{sfn|Enderton|2001|p=188}} इस प्रकार यहाँ पर क्वांटिफ़ायर एलिमिनेशन कलन को उचित ठहराने के लिए उपयोग किए जाने वाले चरणों का उपयोग पुनरावर्ती स्वयंसिद्धीकरणों को परिभाषित करने के लिए किया जा सकता है, जिनमें आवश्यक रूप से प्रेरण की स्वयंसिद्ध स्कीमा सम्मिलित नहीं होती है।{{sfn|Presburger|1929}}{{sfn|Stansifer|1984}}


इसके विपरीत, पीनो अंकगणित, जो कि गुणन के साथ संवर्धित प्रेस्बर्गर अंकगणित है, [[निर्णय समस्या]] के नकारात्मक उत्तर के परिणामस्वरूप निर्णय लेने योग्य नहीं है। गोडेल की अपूर्णता प्रमेय के अनुसार, पीनो अंकगणित अधूरा है और इसकी स्थिरता आंतरिक रूप से सिद्ध करने योग्य नहीं है (लेकिन जेंटज़ेन की स्थिरता प्रमाण देखें)।
इसके विपरीत, पीनो अंकगणित, जो कि गुणन के साथ संवर्धित प्रेस्बर्गर अंकगणित है, [[निर्णय समस्या]] के ऋणात्मक उत्तर के परिणामस्वरूप निर्णय लेने योग्य नहीं है। इस प्रकार गोडेल की अपूर्णता प्रमेय के अनुसार, पीनो अंकगणित अधूरा है और इसकी स्थिरता आंतरिक रूप से सिद्ध करने योग्य नहीं है, अपितु जेंटज़ेन की स्थिरता प्रमाण देखें।


=== कम्प्यूटेशनल जटिलता ===
=== कम्प्यूटरीकृत जटिलता ===
प्रेस्बर्गर अंकगणित के लिए निर्णय समस्या [[कम्प्यूटेशनल जटिलता सिद्धांत]] और [[गणना]] में दिलचस्प उदाहरण है। मान लीजिए कि प्रेस्बर्गर अंकगणित में कथन की लंबाई n है। तब {{harvtxt|Fischer|Rabin|1974}} साबित हुआ कि, सबसे खराब स्थिति में, पहले क्रम के तर्क में कथन के प्रमाण की लंबाई कम से कम होती है <math>2^{2^{cn}}</math>, कुछ स्थिरांक c>0 के लिए। इसलिए, प्रेस्बर्गर अंकगणित के लिए उनके निर्णय एल्गोरिदम का रनटाइम कम से कम घातीय है। फिशर और राबिन ने यह भी साबित किया कि किसी भी उचित स्वयंसिद्धीकरण (उनके पेपर में सटीक रूप से परिभाषित) के लिए, लंबाई n के प्रमेय मौजूद हैं जिनमें दोहरे घातीय फ़ंक्शन लंबाई प्रमाण हैं। सहज रूप से, इससे पता चलता है कि कंप्यूटर प्रोग्राम द्वारा क्या सिद्ध किया जा सकता है, इसकी कम्प्यूटेशनल सीमाएँ हैं। फिशर और राबिन के काम का यह भी तात्पर्य है कि प्रेस्बर्गर अंकगणित का उपयोग उन सूत्रों को परिभाषित करने के लिए किया जा सकता है जो किसी भी एल्गोरिदम की सही गणना करते हैं जब तक कि इनपुट अपेक्षाकृत बड़ी सीमा से कम न हो। सीमाएँ बढ़ाई जा सकती हैं, लेकिन केवल नए फ़ार्मुलों का उपयोग करके। दूसरी ओर, प्रेस्बर्गर अंकगणित के लिए निर्णय प्रक्रिया पर त्रिगुण घातीय ऊपरी सीमा किसके द्वारा सिद्ध की गई थी? {{harvtxt|Oppen|1978}}.
प्रेस्बर्गर अंकगणित के लिए निर्णय समस्या [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटरीकृत जटिलता सिद्धांत]] और [[गणना]] में उत्तम उदाहरण है। मान लीजिए कि प्रेस्बर्गर अंकगणित में कथन की लंबाई n है। इसके आधार पर {{harvtxt|फिश्चर|रेबिन|1974}} द्वारा प्रमाणित हुआ कि, इसकी सबसे बुरी स्थिति में पहले क्रम के तर्क में कथन के प्रमाण की लंबाई कम से कम <math>2^{2^{cn}}</math> होती है, इसके आधार पर कुछ स्थिरांक c>0 के लिए इसका मान दिया गया हैं। इसलिए प्रेस्बर्गर अंकगणित के लिए उनके निर्णय कलन का रनटाइम कम से कम घातीय है। फिशर और राबिन ने यह भी प्रमाणित किया कि किसी भी उचित स्वयंसिद्धीकरण को उनके पेपर में सटीक रूप से परिभाषित करने के लिए, लंबाई n के प्रमेय उपस्थित हैं जिनमें दोहरे घातीय फ़ंक्शन लंबाई प्रमाण हैं। इस प्रकार सहजता से इससे पता चलता है कि कंप्यूटर प्रोग्राम द्वारा क्या सिद्ध किया जा सकता है, इसकी कम्प्यूटरीकृत सीमाएँ हैं। इस प्रकार फिशर और राबिन के काम का यह भी तात्पर्य है कि प्रेस्बर्गर अंकगणित का उपयोग उन सूत्रों को परिभाषित करने के लिए किया जा सकता है जो किसी भी कलन की सही गणना करते हैं जब तक कि इनपुट अपेक्षाकृत बड़ी सीमा से कम न हो। इस प्रकार इसकी सीमाएँ बढ़ाई जा सकती हैं, अपितु इसके लिए उपयुक्त सूत्र का उपयोग किया जाता हैं। दूसरी ओर प्रेस्बर्गर अंकगणित के लिए निर्णय प्रक्रिया पर त्रिगुण घातीय ऊपरी सीमा {{harvtxt|ओपेन्न|1978}} द्वारा सिद्ध की गई थी।


वैकल्पिक जटिलता वर्गों का उपयोग करके अधिक सख्त जटिलता सीमा दिखाई गई थी {{harvtxt|Berman|1980}}. प्रेस्बर्गर अंकगणित (पीए) में सत्य कथनों का सेट [[ वैकल्पिक ट्यूरिंग मशीन |वैकल्पिक ट्यूरिंग मशीन]] (2) के लिए पूरा दिखाया गया है<sup>2<sup>n<sup>O(1)</sup></sup></sup>, n). इस प्रकार, इसकी जटिलता दोहरे घातीय गैर-नियतात्मक समय (2-NEXP) और दोहरे घातीय स्थान (2-EXPSPACE) के बीच है। पूर्णता बहुपद समय अनेक-से-एक कटौती के अंतर्गत है। (यह भी ध्यान दें कि प्रेस्बर्गर अंकगणित को आमतौर पर पीए के रूप में संक्षिप्त किया जाता है, गणित में सामान्य तौर पर पीए का मतलब आमतौर पर पीनो अंकगणित होता है।)
वैकल्पिक जटिलता वर्गों का उपयोग करके अधिक सख्त जटिलता सीमा दिखाई गई थी {{harvtxt|Berman|1980}}. प्रेस्बर्गर अंकगणित (पीए) में सत्य कथनों का समुच्चय [[ वैकल्पिक ट्यूरिंग मशीन |वैकल्पिक ट्यूरिंग मशीन]] (2)<sup>2<sup>n</sup>O(1), n)</sup> के लिए पूरा दिखाया गया है, इस प्रकार इसकी जटिलता दोहरे घातीय गैर-नियतात्मक समय (2-NEXP) और दोहरे घातीय स्थान (2-एक्सस्पेस) के बीच है। इसके पूर्ण बहुपद समय पर इसके अनेक एक से एक कटौतियों के अंतर्गत प्रदर्शित होते है। यह भी ध्यान दें कि प्रेस्बर्गर अंकगणित को सामान्यतः पीए के रूप में संक्षिप्त किया जाता है, गणित में सामान्य तौर पर पीए का अर्थ सामान्यतः पीनो अंकगणित होता है।


अधिक सुक्ष्म परिणाम के लिए, मान लें कि PA(i) सत्य Σ का समुच्चय है<sub>i</sub> PA कथन, और PA(i, j) सत्य Σ का समुच्चय<sub>i</sub> प्रत्येक क्वांटिफायर ब्लॉक के साथ पीए स्टेटमेंट जे वेरिएबल्स तक सीमित हैं। '<' को क्वांटिफायर-मुक्त माना जाता है; यहां, परिबद्ध परिमाणकों को परिमाणकों के रूप में गिना जाता है।<br/>
अधिक सुक्ष्म परिणाम के लिए, मान लें कि PA(i) सत्य Σ<sub>i</sub> का समुच्चय है, यहाँ पर PA कथन, और PA(i, j) सत्य Σ<sub>i</sub> का समुच्चय प्रत्येक क्वांटिफायर ब्लॉक के साथ पीए स्टेटमेंट जे वेरिएबल्स तक सीमित हैं। इस प्रकार '<' को क्वांटिफायर-मुक्त माना जाता है, यहां, परिबद्ध परिमाणकों को परिमाणकों के रूप में गिना जाता है।<br/>PA(1, j) P में है, जबकि PA(1) NP-पूर्ण है।{{sfn|Nguyen Luu|2018|loc=chapter 3}}<br/>i > 0 और j > 2 के लिए, PA(i + 1, j) बहुपद_पदानुक्रम|Σ है<sub>i</sub><sup>PA</sup>-पूर्ण हैं। इस प्रकार अंतिम क्वांटिफायर ब्लॉक में कठोरता परिणाम के लिए केवल j>2 (j=1 के विपरीत) की आवश्यकता होती है।<br/>i>0 के लिए, PA(i+1) घातीय_पदानुक्रम या Σ<sub>i</sub><sup>EXP</sup>-पूर्ण (और समय परिवर्तन(2) है<sup>n<sup>O(i)</sup></sup>, i)-पूर्ण) है।{{sfn|Haase|2014|pp=47:1-47:10}}
PA(1, j) P में है, जबकि PA(1) NP-पूर्ण है।{{sfn|Nguyen Luu|2018|loc=chapter 3}}<br/>
i > 0 और j > 2 के लिए, PA(i + 1, j) बहुपद_पदानुक्रम|Σ है<sub>i</sub><sup></sup>-पूर्ण। अंतिम क्वांटिफायर ब्लॉक में कठोरता परिणाम के लिए केवल j>2 (j=1 के विपरीत) की आवश्यकता होती है।<br/>
i>0 के लिए, PA(i+1) घातीय_पदानुक्रम|Σ है<sub>i</sub><sup>EXP</sup>-पूर्ण (और समय परिवर्तन(2) है<sup>n<sup>O(i)</sup></sup>, i)-पूर्ण).{{sfn|Haase|2014|pp=47:1-47:10}}


छोटा <math>\Sigma_n</math> प्रेस्बर्गर अंकगणित (<math>n>2</math>) है <math>\Sigma_{n-2}^P</math> पूर्ण (और इस प्रकार एनपी पूर्ण के लिए <math>n=3</math>). यहां, 'शॉर्ट' के लिए बाउंडेड (यानी) की आवश्यकता होती है। <math>O(1)</math>) वाक्य का आकार, सिवाय इसके कि पूर्णांक स्थिरांक असीमित हैं (लेकिन बाइनरी में उनकी बिट्स की संख्या इनपुट आकार के विरुद्ध गिना जाता है)। भी, <math>\Sigma_2</math> दो परिवर्तनीय पीए ('संक्षिप्त' होने के प्रतिबंध के बिना) एनपी-पूर्ण है।{{sfn|Nguyen|Pak|2017}} छोटा <math>\Pi_2</math> (और इस तरह <math>\Sigma_2</math>) पीए पी में है, और यह निश्चित-आयामी पैरामीट्रिक पूर्णांक रैखिक प्रोग्रामिंग तक विस्तारित है।{{sfn|Eisenbrand|Shmonin|2008}}
छोटा <math>\Sigma_n</math> प्रेस्बर्गर अंकगणित (<math>n>2</math>) है <math>\Sigma_{n-2}^P</math> पूर्ण (और इस प्रकार एनपी पूर्ण के लिए <math>n=3</math>) हैं। यहां पर 'शॉर्ट' के लिए बाउंडेड (यानी) की आवश्यकता होती है। <math>O(1)</math>) वाक्य का आकार इसके अतिरिक्त इस पूर्णांक के लिए यह स्थिरांक असीमित हैं, अपितु बाइनरी में उनकी बिट्स की संख्या इनपुट आकार के विरुद्ध गिना जाता हैॉ। इसके आधार पर <math>\Sigma_2</math> दो परिवर्तनीय पीए 'संक्षिप्त' होने के प्रतिबंध के बिना एनपी-पूर्ण है।{{sfn|Nguyen|Pak|2017}} इसका मान कम से कम <math>\Pi_2</math> (और इस प्रकार <math>\Sigma_2</math>) PA में है, और यह निश्चित-आयामी पैरामीट्रिक पूर्णांक रैखिक प्रोग्रामिंग तक विस्तारित है।{{sfn|Eisenbrand|Shmonin|2008}}


==अनुप्रयोग==
==अनुप्रयोग==
क्योंकि प्रेस्बर्गर अंकगणित निर्णायक है, प्रेस्बर्गर अंकगणित के लिए स्वचालित प्रमेय सिद्धकर्ता मौजूद हैं। उदाहरण के लिए, [[कॉक]] प्रूफ सहायक प्रणाली में प्रेस्बर्गर अंकगणित के लिए रणनीति ओमेगा की सुविधा है और इसाबेल (प्रूफ सहायक) में सत्यापित क्वांटिफायर उन्मूलन प्रक्रिया शामिल है {{harvtxt|Nipkow|2010}}. सिद्धांत की दोहरी घातीय जटिलता जटिल सूत्रों पर प्रमेय कहावतों का उपयोग करना असंभव बनाती है, लेकिन यह व्यवहार केवल नेस्टेड क्वांटिफायर की उपस्थिति में होता है: {{harvtxt|Nelson|Oppen|1978}} स्वचालित प्रमेय कहावत का वर्णन करें जो क्वांटिफायर-मुक्त प्रेस्बर्गर अंकगणित सूत्रों के कुछ उदाहरणों को साबित करने के लिए नेस्टेड क्वांटिफायर के बिना विस्तारित प्रेस्बर्गर अंकगणित पर [[सिम्प्लेक्स एल्गोरिथ्म]] का उपयोग करता है। हालिया [[संतुष्टि मॉड्यूलो सिद्धांत]] सॉल्वर प्रेस्बर्गर अंकगणित सिद्धांत के क्वांटिफायर-मुक्त टुकड़े को संभालने के लिए पूर्ण [[पूर्णांक प्रोग्रामिंग]] तकनीकों का उपयोग करते हैं।{{sfn|King|Barrett|Tinelli|2014}}
क्योंकि प्रेस्बर्गर अंकगणित निर्णायक है, प्रेस्बर्गर अंकगणित के लिए स्वचालित प्रमेय सिद्धकर्ता उपस्थित हैं। उदाहरण के लिए, [[कॉक]] प्रूफ सहायक प्रणाली में प्रेस्बर्गर अंकगणित के लिए रणनीति ओमेगा की सुविधा है और इसाबेल (प्रूफ सहायक) में {{harvtxt|निपकोव|2010}} द्वारा सत्यापित क्वांटिफायर उन्मूलन प्रक्रिया सम्मिलित है। इसके सिद्धांत की दोहरी घातीय जटिलता जटिल सूत्रों पर प्रमेय कहावतों का उपयोग करना असंभव बनाती है, अपितु यह व्यवहार केवल नेस्टेड क्वांटिफायर की उपस्थिति में होता है: {{harvtxt|नेल्सेन|ओपेन्न|1978}} स्वचालित प्रमेय कहावत का वर्णन करें जो क्वांटिफायर-मुक्त प्रेस्बर्गर अंकगणित सूत्रों के कुछ उदाहरणों को प्रमाणित करने के लिए नेस्टेड क्वांटिफायर के बिना विस्तारित प्रेस्बर्गर अंकगणित पर [[सिम्प्लेक्स एल्गोरिथ्म|सिम्प्लेक्स कलन विधि]] का उपयोग करता है। वर्तमान समय में [[संतुष्टि मॉड्यूलो सिद्धांत]] सॉल्वर प्रेस्बर्गर अंकगणित सिद्धांत के क्वांटिफायर-मुक्त भाग को संभालने के लिए पूर्ण [[पूर्णांक प्रोग्रामिंग]] तकनीकों का उपयोग करते हैं।{{sfn|King|Barrett|Tinelli|2014}}


प्रेस्बर्गर अंकगणित को स्थिरांक द्वारा गुणन को शामिल करने के लिए बढ़ाया जा सकता है, क्योंकि गुणन बार-बार जोड़ा जाता है। अधिकांश सरणी सबस्क्रिप्ट गणनाएँ निर्णय योग्य समस्याओं के क्षेत्र में आती हैं।<ref>For example, in the [[C (programming language)|C programming language]], if <code>a</code> is an array of 4 bytes element size, the expression <code>a[i]</code> can be translated to <code>a<sub>baseadr</sub>+i+i+i+i</code> which fits the restrictions of Presburger arithmetic.</ref> यह दृष्टिकोण [[कंप्यूटर प्रोग्राम]]ों के लिए कम से कम पांच प्रूफ-ऑफ-करेक्टनेस (कंप्यूटर विज्ञान) प्रणालियों का आधार है, जो 1970 के दशक के अंत में [[ स्टैनफोर्ड पास्कल सत्यापनकर्ता |स्टैनफोर्ड पास्कल सत्यापनकर्ता]] से शुरू हुआ और 2005 के माइक्रोसॉफ्ट के स्पेक # सिस्टम तक जारी रहा।
प्रेस्बर्गर अंकगणित को स्थिरांक द्वारा गुणन को सम्मिलित करने के लिए बढ़ाया जा सकता है, क्योंकि गुणन बार-बार जोड़ा जाता है। अधिकांश सरणी सबस्क्रिप्ट गणनाएँ निर्णय योग्य समस्याओं के क्षेत्र में आती हैं।<ref>For example, in the [[C (programming language)|C programming language]], if <code>a</code> is an array of 4 bytes element size, the expression <code>a[i]</code> can be translated to <code>a<sub>baseadr</sub>+i+i+i+i</code> which fits the restrictions of Presburger arithmetic.</ref> यह दृष्टिकोण [[कंप्यूटर प्रोग्राम|कंप्यूटर प्रोग्रामों]] के लिए कम से कम पांच प्रूफ-ऑफ-करेक्टनेस (कंप्यूटर विज्ञान) प्रणालियों का आधार है, जो 1970 के दशक के अंत में [[ स्टैनफोर्ड पास्कल सत्यापनकर्ता |स्टैनफोर्ड पास्कल सत्यापनकर्ता]] से शुरू हुआ और 2005 के माइक्रोसॉफ्ट के स्पेक सिस्टम तक प्रस्तुत किया हैं।


==प्रेस्बर्गर-निश्चित पूर्णांक संबंध==
==प्रेस्बर्गर-निश्चित पूर्णांक संबंध==
अब प्रेस्बर्गर अंकगणित में परिभाषित पूर्णांक [[वित्तीय संबंध]] के बारे में कुछ गुण दिए गए हैं। सरलता के लिए, इस खंड में विचार किए गए सभी संबंध गैर-नकारात्मक पूर्णांकों पर हैं।
अब '''प्रेस्बर्गर अंकगणित''' में परिभाषित पूर्णांक [[वित्तीय संबंध]] के बारे में कुछ गुण दिए गए हैं। सरलता के लिए, इस खंड में विचार किए गए सभी संबंध गैर-ऋणात्मक पूर्णांकों पर हैं।


एक संबंध प्रेस्बर्गर-परिभाषित है यदि और केवल यदि यह [[अर्धरेखीय सेट]] है।{{sfn|Ginsburg|Spanier|1966|pp=285–296}}
एक संबंध प्रेस्बर्गर-परिभाषित है यदि और केवल यदि यह [[अर्धरेखीय सेट|अर्धरेखीय समुच्चय]] है।{{sfn|Ginsburg|Spanier|1966|pp=285–296}}


एक एकात्मक पूर्णांक संबंध <math>R</math>, अर्थात, गैर-नकारात्मक पूर्णांकों का सेट, प्रेस्बर्गर-परिभाषित है यदि और केवल यदि यह अंततः आवधिक है। अर्थात्, यदि कोई सीमा मौजूद है <math>t\in \N</math> और सकारात्मक अवधि <math>p\in\N^{>0}</math> ऐसा कि, सभी पूर्णांकों के लिए <math>n</math> ऐसा है कि <math>|n|\ge t</math>, <math>n\in R</math> अगर और केवल अगर <math>n+p\in R</math>.
एक एकात्मक पूर्णांक से संबंधित <math>R</math>, अर्थात, गैर-ऋणात्मक पूर्णांकों का समुच्चय, प्रेस्बर्गर-परिभाषित है, इस प्रकार यदि यह अंततः आवधिक है। अर्थात्, यदि कोई सीमा <math>t\in \N</math> उपस्थित है और धनात्मक अवधि <math>p\in\N^{>0}</math> ऐसा कि, सभी पूर्णांकों के लिए <math>n</math> ऐसा है कि <math>|n|\ge t</math>, <math>n\in R</math> यदि <math>n+p\in R</math> पर निर्भर रहता हैं।


कोबम-सेमेनोव प्रमेय के अनुसार, संबंध प्रेस्बर्गर-परिभाषित है यदि और केवल यदि यह आधार के बुची अंकगणित में निश्चित है <math>k</math> सभी के लिए <math>k\ge2</math>.{{sfn|Cobham|1969|pp=186–192}}{{sfn|Semenov|1977|pp=403–418}} आधार के बुची अंकगणित में परिभाषित संबंध <math>k</math> और <math>k'</math> के लिए <math>k</math> और <math>k'</math> गुणक स्वतंत्रता पूर्णांक होना प्रेस्बर्गर निश्चित है।
'''कोबम-सेमेनोव प्रमेय''' के अनुसार, संबंध प्रेस्बर्गर-परिभाषित है, कि यदि यह आधार के बुची अंकगणित में निश्चित है <math>k</math> सभी के लिए <math>k\ge2</math> हैं।{{sfn|Cobham|1969|pp=186–192}}{{sfn|Semenov|1977|pp=403–418}} इस प्रकार इसके आधार के बुची अंकगणित में परिभाषित संबंध <math>k</math> और <math>k'</math> के लिए <math>k</math> और <math>k'</math> गुणक स्वतंत्रता पूर्णांक होना प्रेस्बर्गर निश्चित है।


एक पूर्णांक संबंध <math>R</math> प्रेस्बर्गर-परिभाषित है यदि और केवल तभी जब पूर्णांकों के सभी सेट जो पहले क्रम के तर्क में जोड़ और के साथ परिभाषित किए जा सकते हैं <math>R</math> (अर्थात, प्रेस्बर्गर अंकगणित प्लस के लिए विधेय <math>R</math>) प्रेस्बर्गर-परिभाषित हैं।{{sfn|Michaux|Villemaire|1996|pp=251–277}} समान रूप से, प्रत्येक संबंध के लिए <math>R</math> जो कि प्रेस्बर्गर-परिभाषित नहीं है, इसमें अतिरिक्त और के साथ प्रथम-क्रम सूत्र मौजूद है <math>R</math> जो पूर्णांकों के सेट को परिभाषित करता है जिसे केवल जोड़ का उपयोग करके परिभाषित नहीं किया जा सकता है।
एक पूर्णांक संबंध <math>R</math> में प्रेस्बर्गर द्वारा परिभाषित है कि यदि जब पूर्णांकों के सभी समुच्चय जो पहले क्रम के तर्क में जोड़ और के साथ परिभाषित किए जा सकते हैं, जहाँ पर <math>R</math> (अर्थात, प्रेस्बर्गर अंकगणित प्लस के लिए विधेय <math>R</math>) प्रेस्बर्गर-परिभाषित हैं।{{sfn|Michaux|Villemaire|1996|pp=251–277}} इस प्रकार समान्य रूप से, प्रत्येक संबंध के लिए <math>R</math> जो कि प्रेस्बर्गर-परिभाषित नहीं है, इसमें अतिरिक्त और के साथ प्रथम-क्रम सूत्र उपस्थित है <math>R</math> जो पूर्णांकों के समुच्चय को परिभाषित करता है जिसे केवल जोड़ का उपयोग करके परिभाषित नहीं किया जा सकता है।


===मुचनिक का चरित्र-चित्रण===
===मुचनिक की प्रमेय===
प्रेस्बर्गर-परिभाषित संबंध और लक्षण वर्णन स्वीकार करते हैं: मुचनिक के प्रमेय द्वारा।{{sfn|Muchnik|2003|pp=1433–1444}} इसे बताना अधिक जटिल है, लेकिन इससे दो पूर्व लक्षणों का प्रमाण मिल गया। मुचनिक के प्रमेय को बताने से पहले, कुछ अतिरिक्त परिभाषाएँ पेश की जानी चाहिए।
प्रेस्बर्गर-परिभाषित संबंध और लक्षण वर्णन स्वीकार करते हैं: मुचनिक की प्रमेय द्वारा{{sfn|Muchnik|2003|pp=1433–1444}} इसको स्पष्ट करना अधिक जटिल है, अपितु इससे दो पूर्व लक्षणों का प्रमाण मिल गये हैं। इस प्रकार मुचनिक के प्रमेय को बताने से पहले, कुछ अतिरिक्त परिभाषाएँ प्रस्तुत की जानी चाहिए।


होने देना <math>R\subseteq\N^d</math> समुच्चय हो, खंड <math>x_i = j</math> का <math>R</math>, के लिए <math>i < d</math> और <math>j \in \N</math> परिभाषित किया जाता है
होने देना <math>R\subseteq\N^d</math> समुच्चय हो, खंड <math>x_i = j</math> का <math>R</math>, के लिए <math>i < d</math> और <math>j \in \N</math> परिभाषित किया जाता है।
:<math>\left \{(x_0,\ldots,x_{i-1},x_{i+1},\ldots,x_{d-1})\in\N^{d-1}\mid(x_0,\ldots,x_{i-1},j,x_{i+1},\ldots,x_{d-1})\in R \right \}.</math>
:<math>\left \{(x_0,\ldots,x_{i-1},x_{i+1},\ldots,x_{d-1})\in\N^{d-1}\mid(x_0,\ldots,x_{i-1},j,x_{i+1},\ldots,x_{d-1})\in R \right \}.</math>
दो सेट दिए गए <math>R,S\subseteq\N^d</math> और {{nowrap|<math>d</math>-tuple}} पूर्णांकों का <math>(p_0,\ldots,p_{d-1})\in\N^d</math>, सेट <math>R</math> कहा जाता है <math>(p_0,\dots,p_{d-1})</math>-आवधिक में <math>S</math> यदि, सभी के लिए <math>(x_0, \dots, x_{d-1}) \in S</math> ऐसा है कि <math>(x_0+p_0,\dots,x_{d-1}+p_{d-1})\in S,</math> तब <math>(x_0,\ldots,x_{d-1})\in R</math> अगर और केवल अगर <math>(x_0+p_0,\dots,x_{d-1}+p_{d-1})\in R</math>. के लिए <math>s\in\N</math>, सेट <math>R</math> बताया गया {{nowrap|<math>s</math>-periodic}} में <math>S</math> अगर यह है {{nowrap|<math>(p_0,\ldots,p_{d-1})</math>-periodic}} कुछ के लिए <math>(p_0,\dots,p_{d-1})\in\Z^d</math> ऐसा है कि
इस प्रकार यहाँ पर दो समुच्चय <math>R,S\subseteq\N^d</math> और A {{nowrap|<math>d</math>-tuple}} दिए गए हैं। इसके लिए इन पूर्णांकों का <math>(p_0,\ldots,p_{d-1})\in\N^d</math>, समुच्चय <math>R</math> कहा जाता है, जिसके आधार पर <math>(p_0,\dots,p_{d-1})</math>-आवधिक में <math>S</math> यदि, सभी के लिए <math>(x_0, \dots, x_{d-1}) \in S</math> ऐसा है कि <math>(x_0+p_0,\dots,x_{d-1}+p_{d-1})\in S,</math> तब <math>(x_0,\ldots,x_{d-1})\in R</math> को इस प्रकार प्रदर्शित करते हैं यदि <math>(x_0+p_0,\dots,x_{d-1}+p_{d-1})\in R</math>. के लिए <math>s\in\N</math>, समुच्चय <math>R</math> बताया गया {{nowrap|<math>s</math>-periodic}} में <math>S</math> यदि इस प्रकार है कि {{nowrap|<math>(p_0,\ldots,p_{d-1})</math>-periodic}} होने पर इसके कुछ मान <math>(p_0,\dots,p_{d-1})\in\Z^d</math> होने पर उपयुक्त मान प्राप्त होता हैं-


:<math>\sum_{i=0}^{d-1}|p_i| < s.</math>
:<math>\sum_{i=0}^{d-1}|p_i| < s.</math>
अंत में, के लिए <math>k,x_0,\dots,x_{d-1}\in\N</math> होने देना
अंत में, के लिए <math>k,x_0,\dots,x_{d-1}\in\N</math> मान प्राप्त होता हैं।
:<math>C(k,(x_0,\ldots,x_{d-1}))= \left \{(x_0+c_0,\dots,x_{d-1}+c_{d-1})\mid 0 \leq c_i < k \right \}</math> आकार के घन को निरूपित करें <math>k</math> जिसका निचला कोना है <math>(x_0,\dots,x_{d-1})</math>.
:<math>C(k,(x_0,\ldots,x_{d-1}))= \left \{(x_0+c_0,\dots,x_{d-1}+c_{d-1})\mid 0 \leq c_i < k \right \}</math> आकार के घन <math>k</math> को निरूपित करते हैं, जिसका निचला कोना <math>(x_0,\dots,x_{d-1})</math> है।


{{math theorem|name=Muchnik's Theorem|math_statement= <math>R\subseteq\N^d</math> is Presburger-definable if and only if:
{{math theorem|name=Muchnik's Theorem|math_statement= <math>R\subseteq\N^d</math> प्रेस्बर्गर-परिभाषित है यदि और केवल यदि:
* if <math>d > 1</math> then  all sections of <math>R</math> are Presburger-definable and
* if <math>d > 1</math> फिर सभी अनुभाग <math>R</math> प्रेस्बर्गर-परिभाषित हैं और
* there exists <math>s\in\N</math> such that, for every <math>k\in\N</math>, there exists <math>t\in\N</math> such that for all <math>(x_0,\dots,x_{d-1})\in\N^d</math> with <math display="block">\sum_{i=0}^{d-1}x_i>t,</math> <math>R</math> is {{nowrap|<math>s</math>-periodic}} in <math>C(k,(x_0,\dots,x_{d-1}))</math>.}}
* वहां सम्मिलित होने वाले <math>s\in\N</math> ऐसा कि, हर किसी के लिए <math>k\in\N</math>, जहाँ उपस्थित हैं <math>t\in\N</math> जिसका मान सभी के लिए इस प्रकार हैं कि <math>(x_0,\dots,x_{d-1})\in\N^d</math> जिसके साथ <math display="block">\sum_{i=0}^{d-1}x_i>t,</math> <math>R</math> हैं {{nowrap|<math>s</math>-periodic}} जिसमें <math>C(k,(x_0,\dots,x_{d-1}))</math>.}}


सहज रूप से, पूर्णांक <math>s</math> पारी की लंबाई, पूर्णांक का प्रतिनिधित्व करता है <math>k</math> घनों का आकार है और <math>t</math> आवधिकता से पहले की सीमा है। यह परिणाम तब सत्य रहता है जब स्थिति
सहज रूप से, पूर्णांक <math>s</math> पारी की लंबाई, पूर्णांक का प्रतिनिधित्व करता है, यहाँ पर <math>k</math> घनों का आकार है और <math>t</math> आवधिकता से पहले की सीमा है। यह परिणाम तब सत्य रहता है, इस स्थिति के अनुसार-


:<math>\sum_{i=0}^{d-1}x_i>t</math> या तो द्वारा प्रतिस्थापित किया जाता है <math>\min(x_0,\ldots,x_{d-1})>t</math> या द्वारा <math>\max(x_0,\ldots,x_{d-1})>t</math>.
:<math>\sum_{i=0}^{d-1}x_i>t</math> या तो द्वारा प्रतिस्थापित किया जाता है।
:<math>\min(x_0,\ldots,x_{d-1})>t</math> या द्वारा <math>\max(x_0,\ldots,x_{d-1})>t</math> मान प्राप्त होता हैं।


इस लक्षण वर्णन ने प्रेस्बर्गर अंकगणित में निश्चितता के लिए तथाकथित निश्चित मानदंड को जन्म दिया, अर्थात: जोड़ और के साथ प्रथम-क्रम सूत्र मौजूद है {{nowrap|<math>d</math>-ary}} विधेय <math>R</math> जो यदि और केवल यदि को धारण करता है <math>R</math> प्रेस्बर्गर-परिभाषित संबंध द्वारा व्याख्या की गई है। मुचनिक का प्रमेय यह साबित करने की भी अनुमति देता है कि यह निर्णय लेने योग्य है कि [[स्वचालित अनुक्रम]] प्रेस्बर्गर-परिभाषित सेट को स्वीकार करता है या नहीं।
इस लक्षण वर्णन ने प्रेस्बर्गर अंकगणित में निश्चितता के लिए तथाकथित निश्चित मानदंड को जन्म दिया हैं, अर्थात जोड़ और A के साथ प्रथम-क्रम सूत्र उपस्थित है, जिसके आधार पर {{nowrap|<math>d</math>-ary}} विधेय <math>R</math> जो यदि और केवल यदि को धारण करता है, इसके आधार पर <math>R</math> प्रेस्बर्गर-परिभाषित संबंध द्वारा व्याख्या की गई है। इस प्रकार मुचनिक का प्रमेय यह प्रमाणित करने की भी अनुमति देता है कि यह निर्णय लेने योग्य है कि [[स्वचालित अनुक्रम]] प्रेस्बर्गर-परिभाषित समुच्चय को स्वीकार करता है या नहीं यह स्वीकार किया जाता हैं।


==यह भी देखें==
==यह भी देखें==
Line 436: Line 435:
==बाहरी संबंध==
==बाहरी संबंध==
*[http://www.philipp.ruemmer.org/princess.shtml A complete Theorem Prover for Presburger Arithmetic] by Philipp Rümmer
*[http://www.philipp.ruemmer.org/princess.shtml A complete Theorem Prover for Presburger Arithmetic] by Philipp Rümmer
[[Category: 1929 परिचय]] [[Category: अंकगणित के औपचारिक सिद्धांत]] [[Category: कंप्यूटर विज्ञान में तर्क]] [[Category: प्रमाण सिद्धांत]] [[Category: मॉडल सिद्धांत]]


 
[[Category:1929 परिचय]]
 
[[Category:CS1]]
[[Category: Machine Translated Page]]
[[Category:CS1 русский-language sources (ru)]]
[[Category:Created On 27/06/2023]]
[[Category:Created On 27/06/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:अंकगणित के औपचारिक सिद्धांत]]
[[Category:कंप्यूटर विज्ञान में तर्क]]
[[Category:प्रमाण सिद्धांत]]
[[Category:मॉडल सिद्धांत]]

Latest revision as of 10:51, 14 July 2023

प्रेस्बर्गर अंकगणित मुख्य रूप से प्रथम-क्रम विधेय का ऐसा कलन है। जिसमें संयोजन के साथ प्राकृतिक संख्याओं का प्रथम-क्रम सिद्धांत, जिसका नाम मोजेज़ प्रेस्बर्गर के सम्मान में रखा गया है, जिन्होंने इसे 1929 में प्रस्तुत किया था। प्रेस्बर्गर के आधार पर अंकगणित के हस्ताक्षर गणितीय तर्क में केवल संयोजन संचालन और समानता सम्मिलित है, इस प्रकार गुणन संक्रिया को पूर्ण रूप से छोड़ दिया गया है। जिसके कारण स्वयंसिद्धों में गणितीय प्रेरण की योजना को सम्मिलित किया गया है।

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

अवलोकन

प्रेस्बर्गर अंकगणित की भाषा में स्थिरांक 0 और 1 और बाइनरी फ़ंक्शन + सम्मिलित है, जिसकी मुख्यतः जोड़ के रूप में व्याख्या किया गया है।

इस भाषा में, प्रेस्बर्गर अंकगणित के स्वयंसिद्ध निम्नलिखित के सार्वभौमिक समापन इस प्रकार हैं:

  1. ¬(0 = x + 1)
  2. x + 1 = y + 1 → x = y
  3. x + 0 = x
  4. x + (y + 1) = (x + y) + 1
  5. मान लीजिए P(x) मुक्त चर x और संभवतः अन्य मुक्त चर हैं, जिसके साथ प्रेस्बर्गर अंकगणित की भाषा में प्रथम-क्रम तर्क या प्रथम-क्रम सूत्र है। फिर निम्नलिखित सूत्र स्वयंसिद्ध है:
  6. (P(0) ∧ ∀x(P(x) → P(x + 1))) → ∀y P(y)

(5) गणितीय प्रेरण की स्वयंसिद्ध स्कीमा को प्रदर्शित करता है, जो अनंत रूप से कई स्वयंसिद्धों का प्रतिनिधित्व करती है। इन्हें किसी भी सीमित संख्या में स्वयंसिद्धों द्वारा प्रतिस्थापित नहीं किया जा सकता है, अर्थात, प्रेस्बर्गर अंकगणित प्रथम-क्रम तर्क में अंतिम रूप से स्वयंसिद्ध नहीं है।[1]

प्रेस्बर्गर अंकगणित को प्रथम-क्रम तर्क मुख्य रूप से प्रथम-क्रम सिद्धांत, प्रारूप और प्राथमिक वर्ग या प्रथम-क्रम सिद्धांत के रूप में देखा जा सकता है, जिसमें समानता के साथ उपरोक्त सिद्धांतों के सभी परिणाम सम्मिलित हैं। इस प्रकार वैकल्पिक रूप से इसे उन वाक्यों के समुच्चय के रूप में परिभाषित किया जा सकता है जो तार्किक व्याख्या के आधार पर इच्छित व्याख्याओं में सत्य मान को प्रदर्शित करते हैं: इसके लिए स्थिरांक 0, 1 के साथ गैर-ऋणात्मक पूर्णांकों की संरचना और गैर-ऋणात्मक पूर्णांकों का योग भी सम्मिलित किया जाता हैं।

प्रेस्बर्गर अंकगणित को पूर्ण और निर्णय लेने योग्य बनाया गया है। इसलिए यह विभाज्यता या मौलिकता इसके लिए अधिक सामान्य रूप से चर के गुणन की ओर ले जाने वाली किसी भी संख्या अवधारणा को प्रदर्शित करता हैं, इस प्रकार की अवधारणाओं को औपचारिक रूप से नहीं देखा जा सकता है। चूंकि यह विभाज्यता के व्यक्तिगत उदाहरण तैयार कर सकता है, उदाहरण के लिए यह सभी x के लिए प्रमाणित होता है, यहाँ पर y मुख्यतः (y + y = x) ∨ (y + y + 1 = x) रूप में उपस्थित है। यह बताता है कि प्रत्येक संख्या या तो सम या विषम है।

गुण

मोजेज़ प्रेस्बर्गर ने प्रेस्बर्गर अंकगणित को सिद्ध किया:

  • संगति प्रमाण: प्रेस्बर्गर अंकगणित में ऐसा कोई कथन नहीं है जिसे स्वयंसिद्धों से इस प्रकार निकाला जा सके कि उसका निषेध भी निकाला जा सके।
  • पूर्णता (तर्क): प्रेस्बर्गर अंकगणित की भाषा में प्रत्येक कथन के लिए, या तो इसे स्वयंसिद्धों से निकालना संभव है या इसका निषेध निकालना संभव है।
  • निर्णयशीलता (तर्क): कलन विधि उपस्थित है जो यह तय करता है कि प्रेस्बर्गर अंकगणित में दिया गया कोई भी कथन प्रमेय है या गैर-प्रमेय है।

प्रेस्बर्गर अंकगणित की निर्णायकता को अंकगणितीय सर्वांगसमता के बारे में तर्क द्वारा पूरक, क्वांटिफायर उन्मूलन का उपयोग करके दिखाया जा सकता है।[2][3][4][5] इस प्रकार यहाँ पर क्वांटिफ़ायर एलिमिनेशन कलन को उचित ठहराने के लिए उपयोग किए जाने वाले चरणों का उपयोग पुनरावर्ती स्वयंसिद्धीकरणों को परिभाषित करने के लिए किया जा सकता है, जिनमें आवश्यक रूप से प्रेरण की स्वयंसिद्ध स्कीमा सम्मिलित नहीं होती है।[2][6]

इसके विपरीत, पीनो अंकगणित, जो कि गुणन के साथ संवर्धित प्रेस्बर्गर अंकगणित है, निर्णय समस्या के ऋणात्मक उत्तर के परिणामस्वरूप निर्णय लेने योग्य नहीं है। इस प्रकार गोडेल की अपूर्णता प्रमेय के अनुसार, पीनो अंकगणित अधूरा है और इसकी स्थिरता आंतरिक रूप से सिद्ध करने योग्य नहीं है, अपितु जेंटज़ेन की स्थिरता प्रमाण देखें।

कम्प्यूटरीकृत जटिलता

प्रेस्बर्गर अंकगणित के लिए निर्णय समस्या कम्प्यूटरीकृत जटिलता सिद्धांत और गणना में उत्तम उदाहरण है। मान लीजिए कि प्रेस्बर्गर अंकगणित में कथन की लंबाई n है। इसके आधार पर फिश्चर & रेबिन (1974) द्वारा प्रमाणित हुआ कि, इसकी सबसे बुरी स्थिति में पहले क्रम के तर्क में कथन के प्रमाण की लंबाई कम से कम होती है, इसके आधार पर कुछ स्थिरांक c>0 के लिए इसका मान दिया गया हैं। इसलिए प्रेस्बर्गर अंकगणित के लिए उनके निर्णय कलन का रनटाइम कम से कम घातीय है। फिशर और राबिन ने यह भी प्रमाणित किया कि किसी भी उचित स्वयंसिद्धीकरण को उनके पेपर में सटीक रूप से परिभाषित करने के लिए, लंबाई n के प्रमेय उपस्थित हैं जिनमें दोहरे घातीय फ़ंक्शन लंबाई प्रमाण हैं। इस प्रकार सहजता से इससे पता चलता है कि कंप्यूटर प्रोग्राम द्वारा क्या सिद्ध किया जा सकता है, इसकी कम्प्यूटरीकृत सीमाएँ हैं। इस प्रकार फिशर और राबिन के काम का यह भी तात्पर्य है कि प्रेस्बर्गर अंकगणित का उपयोग उन सूत्रों को परिभाषित करने के लिए किया जा सकता है जो किसी भी कलन की सही गणना करते हैं जब तक कि इनपुट अपेक्षाकृत बड़ी सीमा से कम न हो। इस प्रकार इसकी सीमाएँ बढ़ाई जा सकती हैं, अपितु इसके लिए उपयुक्त सूत्र का उपयोग किया जाता हैं। दूसरी ओर प्रेस्बर्गर अंकगणित के लिए निर्णय प्रक्रिया पर त्रिगुण घातीय ऊपरी सीमा ओपेन्न (1978) द्वारा सिद्ध की गई थी।

वैकल्पिक जटिलता वर्गों का उपयोग करके अधिक सख्त जटिलता सीमा दिखाई गई थी Berman (1980). प्रेस्बर्गर अंकगणित (पीए) में सत्य कथनों का समुच्चय वैकल्पिक ट्यूरिंग मशीन (2)2nO(1), n) के लिए पूरा दिखाया गया है, इस प्रकार इसकी जटिलता दोहरे घातीय गैर-नियतात्मक समय (2-NEXP) और दोहरे घातीय स्थान (2-एक्सस्पेस) के बीच है। इसके पूर्ण बहुपद समय पर इसके अनेक एक से एक कटौतियों के अंतर्गत प्रदर्शित होते है। यह भी ध्यान दें कि प्रेस्बर्गर अंकगणित को सामान्यतः पीए के रूप में संक्षिप्त किया जाता है, गणित में सामान्य तौर पर पीए का अर्थ सामान्यतः पीनो अंकगणित होता है।

अधिक सुक्ष्म परिणाम के लिए, मान लें कि PA(i) सत्य Σi का समुच्चय है, यहाँ पर PA कथन, और PA(i, j) सत्य Σi का समुच्चय प्रत्येक क्वांटिफायर ब्लॉक के साथ पीए स्टेटमेंट जे वेरिएबल्स तक सीमित हैं। इस प्रकार '<' को क्वांटिफायर-मुक्त माना जाता है, यहां, परिबद्ध परिमाणकों को परिमाणकों के रूप में गिना जाता है।
PA(1, j) P में है, जबकि PA(1) NP-पूर्ण है।[7]
i > 0 और j > 2 के लिए, PA(i + 1, j) बहुपद_पदानुक्रम|Σ हैiPA-पूर्ण हैं। इस प्रकार अंतिम क्वांटिफायर ब्लॉक में कठोरता परिणाम के लिए केवल j>2 (j=1 के विपरीत) की आवश्यकता होती है।
i>0 के लिए, PA(i+1) घातीय_पदानुक्रम या ΣiEXP-पूर्ण (और समय परिवर्तन(2) हैnO(i), i)-पूर्ण) है।[8]

छोटा प्रेस्बर्गर अंकगणित () है पूर्ण (और इस प्रकार एनपी पूर्ण के लिए ) हैं। यहां पर 'शॉर्ट' के लिए बाउंडेड (यानी) की आवश्यकता होती है। ) वाक्य का आकार इसके अतिरिक्त इस पूर्णांक के लिए यह स्थिरांक असीमित हैं, अपितु बाइनरी में उनकी बिट्स की संख्या इनपुट आकार के विरुद्ध गिना जाता हैॉ। इसके आधार पर दो परिवर्तनीय पीए 'संक्षिप्त' होने के प्रतिबंध के बिना एनपी-पूर्ण है।[9] इसका मान कम से कम (और इस प्रकार ) PA में है, और यह निश्चित-आयामी पैरामीट्रिक पूर्णांक रैखिक प्रोग्रामिंग तक विस्तारित है।[10]

अनुप्रयोग

क्योंकि प्रेस्बर्गर अंकगणित निर्णायक है, प्रेस्बर्गर अंकगणित के लिए स्वचालित प्रमेय सिद्धकर्ता उपस्थित हैं। उदाहरण के लिए, कॉक प्रूफ सहायक प्रणाली में प्रेस्बर्गर अंकगणित के लिए रणनीति ओमेगा की सुविधा है और इसाबेल (प्रूफ सहायक) में निपकोव (2010) द्वारा सत्यापित क्वांटिफायर उन्मूलन प्रक्रिया सम्मिलित है। इसके सिद्धांत की दोहरी घातीय जटिलता जटिल सूत्रों पर प्रमेय कहावतों का उपयोग करना असंभव बनाती है, अपितु यह व्यवहार केवल नेस्टेड क्वांटिफायर की उपस्थिति में होता है: नेल्सेन & ओपेन्न (1978) स्वचालित प्रमेय कहावत का वर्णन करें जो क्वांटिफायर-मुक्त प्रेस्बर्गर अंकगणित सूत्रों के कुछ उदाहरणों को प्रमाणित करने के लिए नेस्टेड क्वांटिफायर के बिना विस्तारित प्रेस्बर्गर अंकगणित पर सिम्प्लेक्स कलन विधि का उपयोग करता है। वर्तमान समय में संतुष्टि मॉड्यूलो सिद्धांत सॉल्वर प्रेस्बर्गर अंकगणित सिद्धांत के क्वांटिफायर-मुक्त भाग को संभालने के लिए पूर्ण पूर्णांक प्रोग्रामिंग तकनीकों का उपयोग करते हैं।[11]

प्रेस्बर्गर अंकगणित को स्थिरांक द्वारा गुणन को सम्मिलित करने के लिए बढ़ाया जा सकता है, क्योंकि गुणन बार-बार जोड़ा जाता है। अधिकांश सरणी सबस्क्रिप्ट गणनाएँ निर्णय योग्य समस्याओं के क्षेत्र में आती हैं।[12] यह दृष्टिकोण कंप्यूटर प्रोग्रामों के लिए कम से कम पांच प्रूफ-ऑफ-करेक्टनेस (कंप्यूटर विज्ञान) प्रणालियों का आधार है, जो 1970 के दशक के अंत में स्टैनफोर्ड पास्कल सत्यापनकर्ता से शुरू हुआ और 2005 के माइक्रोसॉफ्ट के स्पेक सिस्टम तक प्रस्तुत किया हैं।

प्रेस्बर्गर-निश्चित पूर्णांक संबंध

अब प्रेस्बर्गर अंकगणित में परिभाषित पूर्णांक वित्तीय संबंध के बारे में कुछ गुण दिए गए हैं। सरलता के लिए, इस खंड में विचार किए गए सभी संबंध गैर-ऋणात्मक पूर्णांकों पर हैं।

एक संबंध प्रेस्बर्गर-परिभाषित है यदि और केवल यदि यह अर्धरेखीय समुच्चय है।[13]

एक एकात्मक पूर्णांक से संबंधित , अर्थात, गैर-ऋणात्मक पूर्णांकों का समुच्चय, प्रेस्बर्गर-परिभाषित है, इस प्रकार यदि यह अंततः आवधिक है। अर्थात्, यदि कोई सीमा उपस्थित है और धनात्मक अवधि ऐसा कि, सभी पूर्णांकों के लिए ऐसा है कि , यदि पर निर्भर रहता हैं।

कोबम-सेमेनोव प्रमेय के अनुसार, संबंध प्रेस्बर्गर-परिभाषित है, कि यदि यह आधार के बुची अंकगणित में निश्चित है सभी के लिए हैं।[14][15] इस प्रकार इसके आधार के बुची अंकगणित में परिभाषित संबंध और के लिए और गुणक स्वतंत्रता पूर्णांक होना प्रेस्बर्गर निश्चित है।

एक पूर्णांक संबंध में प्रेस्बर्गर द्वारा परिभाषित है कि यदि जब पूर्णांकों के सभी समुच्चय जो पहले क्रम के तर्क में जोड़ और के साथ परिभाषित किए जा सकते हैं, जहाँ पर (अर्थात, प्रेस्बर्गर अंकगणित प्लस के लिए विधेय ) प्रेस्बर्गर-परिभाषित हैं।[16] इस प्रकार समान्य रूप से, प्रत्येक संबंध के लिए जो कि प्रेस्बर्गर-परिभाषित नहीं है, इसमें अतिरिक्त और के साथ प्रथम-क्रम सूत्र उपस्थित है जो पूर्णांकों के समुच्चय को परिभाषित करता है जिसे केवल जोड़ का उपयोग करके परिभाषित नहीं किया जा सकता है।

मुचनिक की प्रमेय

प्रेस्बर्गर-परिभाषित संबंध और लक्षण वर्णन स्वीकार करते हैं: मुचनिक की प्रमेय द्वारा[17] इसको स्पष्ट करना अधिक जटिल है, अपितु इससे दो पूर्व लक्षणों का प्रमाण मिल गये हैं। इस प्रकार मुचनिक के प्रमेय को बताने से पहले, कुछ अतिरिक्त परिभाषाएँ प्रस्तुत की जानी चाहिए।

होने देना समुच्चय हो, खंड का , के लिए और परिभाषित किया जाता है।

इस प्रकार यहाँ पर दो समुच्चय और A -tuple दिए गए हैं। इसके लिए इन पूर्णांकों का , समुच्चय कहा जाता है, जिसके आधार पर -आवधिक में यदि, सभी के लिए ऐसा है कि तब को इस प्रकार प्रदर्शित करते हैं यदि . के लिए , समुच्चय बताया गया -periodic में यदि इस प्रकार है कि -periodic होने पर इसके कुछ मान होने पर उपयुक्त मान प्राप्त होता हैं-

अंत में, के लिए मान प्राप्त होता हैं।

आकार के घन को निरूपित करते हैं, जिसका निचला कोना है।

Muchnik's Theorem —  प्रेस्बर्गर-परिभाषित है यदि और केवल यदि:

  • if फिर सभी अनुभाग प्रेस्बर्गर-परिभाषित हैं और
  • वहां सम्मिलित होने वाले ऐसा कि, हर किसी के लिए , जहाँ उपस्थित हैं जिसका मान सभी के लिए इस प्रकार हैं कि जिसके साथ
    हैं -periodic जिसमें .

सहज रूप से, पूर्णांक पारी की लंबाई, पूर्णांक का प्रतिनिधित्व करता है, यहाँ पर घनों का आकार है और आवधिकता से पहले की सीमा है। यह परिणाम तब सत्य रहता है, इस स्थिति के अनुसार-

या तो द्वारा प्रतिस्थापित किया जाता है।
या द्वारा मान प्राप्त होता हैं।

इस लक्षण वर्णन ने प्रेस्बर्गर अंकगणित में निश्चितता के लिए तथाकथित निश्चित मानदंड को जन्म दिया हैं, अर्थात जोड़ और A के साथ प्रथम-क्रम सूत्र उपस्थित है, जिसके आधार पर -ary विधेय जो यदि और केवल यदि को धारण करता है, इसके आधार पर प्रेस्बर्गर-परिभाषित संबंध द्वारा व्याख्या की गई है। इस प्रकार मुचनिक का प्रमेय यह प्रमाणित करने की भी अनुमति देता है कि यह निर्णय लेने योग्य है कि स्वचालित अनुक्रम प्रेस्बर्गर-परिभाषित समुच्चय को स्वीकार करता है या नहीं यह स्वीकार किया जाता हैं।

यह भी देखें

संदर्भ

  1. Zoethout 2015, p. 8, Theorem 1.2.4..
  2. 2.0 2.1 Presburger 1929.
  3. Monk 2012, p. 240.
  4. Nipkow 2010.
  5. Enderton 2001, p. 188.
  6. Stansifer 1984.
  7. Nguyen Luu 2018, chapter 3.
  8. Haase 2014, pp. 47:1-47:10.
  9. Nguyen & Pak 2017.
  10. Eisenbrand & Shmonin 2008.
  11. King, Barrett & Tinelli 2014.
  12. For example, in the C programming language, if a is an array of 4 bytes element size, the expression a[i] can be translated to abaseadr+i+i+i+i which fits the restrictions of Presburger arithmetic.
  13. Ginsburg & Spanier 1966, pp. 285–296.
  14. Cobham 1969, pp. 186–192.
  15. Semenov 1977, pp. 403–418.
  16. Michaux & Villemaire 1996, pp. 251–277.
  17. Muchnik 2003, pp. 1433–1444.


ग्रन्थसूची

  • Berman, L. (1980). "The Complexity of Logical Theories". Theoretical Computer Science. 11 (1): 71–77. doi:10.1016/0304-3975(80)90037-7.
  • Cooper, D.C. (1972). "Theorem Proving in Arithmetic without Multiplication". In B. Meltzer and D. Michie (ed.). Machine Intelligence. Vol. 7. Edinburgh University Press. pp. 91–99.
  • Monk, J. Donald Monk (2012). Mathematical Logic (Graduate Texts in Mathematics (37)) (Softcover reprint of the original 1st ed. 1976 ed.). Springer. ISBN 9781468494549.
  • Nelson, Greg; Oppen, Derek C. (April 1978). "A simplifier based on efficient decision algorithms". Proc. 5th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages: 141–150. doi:10.1145/512760.512775. S2CID 6342372.
  • Presburger, Mojżesz (1929). "Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt". Comptes Rendus du I congrès de Mathématiciens des Pays Slaves, Warszawa: 92–101., see Stansifer (1984) for an English translation
  • Pugh, William (1991). "The Omega test: a fast and practical integer programming algorithm for dependence analysis". Supercomputing '91: Proceedings of the 1991 ACM/IEEE Conference on Supercomputing. New York, NY, USA: Association for Computing Machinery: 4–13. doi:10.1145/125826.125848. ISBN 0897914597. S2CID 3174094.
  • Reddy, C.R.; Loveland, D.W. (1978). "Presburger Arithmetic with Bounded Quantifier Alternation". ACM Symposium on Theory of Computing: 320–325. doi:10.1145/800133.804361. S2CID 13966721.
  • Semenov, A.L. (1977). "Presburgerness of predicates regular in two number systems". Sibirsk. Mat. Zh. (in русский). 18: 403–418.
  • Young, P. (1985). "Gödel theorems, exponential difficulty and undecidability of arithmetic theories: an exposition". In A. Nerode and R. Shore (ed.). Recursion Theory, American Mathematical Society. pp. 503–522.


बाहरी संबंध