Difference between revisions of "निर्णायकता (तर्क)"

Revision as of 09:16, 9 March 2023

तर्क में, सही/गलत निर्णय समस्या निर्णायक होती है यदि सही उत्तर प्राप्त करने के लिए कोई प्रभावी तरीका सम्मिलित हो। शून्य-क्रम तर्क (प्रस्तावात्मक तर्क) निर्णायक है, जबकि प्रथम-क्रम और उच्च-क्रम तर्क नहीं हैं। तार्किक रूप से मान्य सूत्रों (या प्रमेय) के उनके समुच्चय में सदस्यता प्रभावी रूप से निर्धारित की जा सकती है, तो तार्किक प्रणालियां निर्णायक हैं। औपचारिक प्रणालियाँ निर्णायक होती हैं यदि उनकी वैधता (तर्क) सूत्रों (या प्रमेय) के समुच्चय में सदस्यता प्रभावी रूप से निर्धारित की जा सकती है। निश्चित तार्किक प्रणाली में सिद्धांत (तार्किक परिणाम के अंतर्गत संवृत्त किए गए कथनों का समुच्चय) निर्णायक होता है यदि यह निर्धारित करने के लिए एक प्रभावी तरीका है कि सिद्धांत में एकपक्षीय सूत्र सम्मिलित हैं या नहीं है। कई महत्वपूर्ण समस्याएं अनिर्णीत हैं, अर्थात्, यह प्रमाणित हो गया है कि सदस्यता निर्धारित करने के लिए कोई प्रभावी तरीका नहीं है (परिमित के बाद एक सही उत्तर देना, हालांकि संभवतः बहुत लंबा, सभी स्थितियों में समय) उनके लिए सम्मिलित हो सकता है।

तार्किक प्रणाली की निर्णायकता

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

तार्किक प्रणाली निर्णायक होती है यदि यह निर्धारित करने के लिए एक प्रभावी तरीका है कि क्या स्वैच्छिक सूत्र तार्किक प्रणाली के प्रमेय हैं। उदाहरण के लिए, प्रस्तावपरक तर्क निर्णायक है, क्योंकि सत्य-सारणी पद्धति का उपयोग यह निर्धारित करने के लिए किया जा सकता है कि क्या एक एकपक्षीय तर्कवाक्य सूत्र तार्किक रूप से मान्य है।

प्रथम-क्रम तर्क सामान्य रूप से निर्णायक नहीं होता है; विशेष रूप से, किसी भी हस्ताक्षर (तर्क) में तार्किक वैधताओं का समुच्चय जिसमें समानता सम्मिलित है और दो या अधिक तर्कों के साथ कम से कम एक अन्य निर्धारक निर्णायक नहीं है।^[1] प्रथम-क्रम तर्क को विस्तारित करने वाली तार्किक प्रणालियाँ, जैसे कि द्वितीय-क्रम तर्क और प्रकार सिद्धांत, भी अनिर्णीत हैं।

पहचान के साथ एकपदीय निर्धारक कलन की वैधता, हालांकि, निर्णायक हैं। यह प्रणाली प्रथम-क्रम तर्क है जो उन हस्ताक्षरों तक सीमित है जिनके पास कोई फ़ंक्शन प्रतीक नहीं है और समानता के अतिरिक्त जिनके संबंध प्रतीक कभी भी एक से अधिक तर्क नहीं लेते हैं।

कुछ तार्किक प्रणालियाँ केवल प्रमेयों के समुच्चय द्वारा ही पर्याप्त रूप से प्रदर्शित नहीं होती हैं। (उदाहरण के लिए, क्लेन के तर्क में कोई भी प्रमेय नहीं है।) ऐसे स्थितियों में, तार्किक प्रणाली की निर्णायकता की वैकल्पिक परिभाषाओं का प्रायः उपयोग किया जाता है, जो सूत्रों की वैधता की तुलना में कुछ अधिक सामान्य निर्धारित करने के लिए एक प्रभावी विधि की मांग करती हैं; इंस्टेंस के लिए, अनुक्रमों की वैधता, या या परिणाम संबंध {(Г, A) | Г ⊧ A} तार्किक है।

सिद्धांत की निर्णायकता

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

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

सुसंगत सिद्धांत जिसमें गुण है कि प्रत्येक सुसंगत विस्तार अनिर्णीत है, अनिवार्य रूप से अनिर्णीत कहा जाता है। वास्तव में, प्रत्येक सुसंगत विस्तार अनिवार्य रूप से अनिर्णीत होगा। क्षेत्रों का सिद्धांत अनिर्णीत है लेकिन अनिवार्य रूप से अनिर्णीत नहीं है। रॉबिन्सन अंकगणित अनिवार्य रूप से अनिर्णीत होने के लिए जाना जाता है, और इस प्रकार प्रत्येक सुसंगत सिद्धांत जिसमें रॉबिन्सन अंकगणित सम्मिलित है या व्याख्या करता है, वह भी (अनिवार्य रूप से) अनिर्णीत है।

निर्णायक प्रथम-क्रम के सिद्धांतों के उदाहरणों में वास्तविक संवृत क्षेत्रो का सिद्धांत और प्रेस्बर्गर अंकगणित सम्मिलित हैं, जबकि समुच्चय का सिद्धांत (गणित) और रॉबिन्सन अंकगणित अनिर्णीत सिद्धांतों के उदाहरण हैं।

कुछ निर्णायक सिद्धांत

कुछ निर्णायक सिद्धांतों में सम्मिलित (मोंक 1976, पेज 234) हैं:^[2]

1915 में लियोपोल्ड लोवेनहेम द्वारा स्थापित केवल समानता के साथ हस्ताक्षर में प्रथम-क्रम तार्किक वैधता का समुच्चय।

1959 में एरेनफ्यूच्ट द्वारा स्थापित समानता और एकल फलन के साथ हस्ताक्षर में प्रथम-क्रम तार्किक वैधता का समुच्चय।
समानता और जोड़ के साथ हस्ताक्षर में प्राकृतिक संख्याओं का प्रथम-क्रम सिद्धांत, जिसे प्रेस्बर्गर अंकगणित भी कहा जाता है। पूर्णता 1929 में मोजेज़ प्रेस्बर्गर द्वारा स्थापित की गई थी।
समानता और गुणन के साथ हस्ताक्षर में प्राकृतिक संख्याओं का प्रथम-क्रम सिद्धांत, जिसे स्कोलेम अंकगणित भी कहा जाता है।
1940 में अल्फ्रेड टार्स्की द्वारा स्थापित बूलियन बीजगणित के पहले क्रम के सिद्धांत को विहित रूप से परिभाषित किया गया (1940 में पाया गया लेकिन 1949 में घोषित किया गया)।
टारस्की द्वारा 1949 में स्थापित दी गई विशेषता (बीजगणित) के बीजगणितीय रूप से संवृत क्षेत्रों का पहला क्रम सिद्धांत।
1949 में टार्स्की द्वारा स्थापित वास्तविक-संवृत क्रमित क्षेत्रों का प्रथम-क्रम सिद्धांत (टार्स्की की घातीय फलन समस्या भी देखें)।
1949 में टार्स्की द्वारा स्थापित यूक्लिडियन ज्यामिति का प्रथम-क्रम सिद्धांत।
एबेलियन समुच्चयो का प्रथम-क्रम सिद्धांत, 1955 में स्ज़मील्यू द्वारा स्थापित किया गया।
1959 में श्वाभौसर द्वारा स्थापित अतिपरवलयिक ज्यामिति का प्रथम-क्रम सिद्धांत।
1980 के दशक से लेकर आज तक समुच्चय सिद्धांत की विशिष्ट निर्णायक उपभाषाओं की जांच की गई। (कैंटोन एट अल, 2001)
ट्री का एकपदीय द्वित्तीय क्रम सिद्धांत (ग्राफ़ सिद्धांत) (S2S (गणित) देखें)।

निर्णायकता स्थापित करने के लिए उपयोग की जाने वाली विधियों में परिमाणक उन्मूलन, मॉडल पूर्णता और लोश-वॉच परीक्षण सम्मिलित हैं।

कुछ अनिर्णीत सिद्धांत

कुछ अनिर्णीत सिद्धांतों में सम्मिलित हैं (मोंक 1976, पृष्ठ 279):^[2]

समानता के साथ किसी भी पहले-क्रम के हस्ताक्षर में तार्किक वैधताओं का समुच्चय और या तो: 2 से कम नहीं, या दो एकल फलन प्रतीकों, या 2 से कम नहीं, 1953 में बोरिस ट्रेचटेनब्रॉट द्वारा स्थापित एरिटी का एक फलन प्रतीक है।
1949 में टार्स्की और आंद्रेज मोस्टोव्स्की द्वारा स्थापित योग, गुणन और समानता के साथ प्राकृतिक संख्याओं का पहला क्रम सिद्धांत।
1949 में जूलिया रॉबिन्सन द्वारा स्थापित जोड़, गुणा और समानता के साथ परिमेय संख्याओं का प्रथम-क्रम सिद्धांत।
1953 में अल्फ्रेड टार्स्की द्वारा स्थापित समुच्चयों का पहला क्रम सिद्धांत^[3] उल्लेखनीय रूप से, न केवल समुच्चयों का सामान्य सिद्धांत अनिर्णीत है, बल्कि कई और विशिष्ट सिद्धांत भी हैं, उदाहरण के लिए (जैसा कि माल्सेव 1961 द्वारा स्थापित) परिमित समुच्चयों का सिद्धांत है। मालसेव ने यह भी स्थापित किया कि अर्धसमुच्चयों का सिद्धांत और वलयों का सिद्धांत अनिर्णीत हैं। रॉबिन्सन ने 1949 में स्थापित किया कि क्षेत्रों का सिद्धांत अनिर्णीत है।
रॉबिन्सन अंकगणित (और इसलिए कोई भी सुसंगत विस्तार, जैसे पियानों अंकगणित) अनिवार्य रूप से अनिर्णीत है, जैसा कि 1950 में राफेल रॉबिन्सन द्वारा स्थापित किया गया था।
समानता और दो फलन प्रतीकों के साथ प्रथम-क्रम सिद्धांत है।^[4]

व्याख्यात्मकता पद्धति का उपयोग प्रायः सिद्धांतों की अनिश्चितता को स्थापित करने के लिए किया जाता है। यदि एक अनिवार्य रूप से अनिर्णीत सिद्धांत T एक सुसंगत सिद्धांत S में व्याख्या योग्य है, तो S भी अनिवार्य रूप से अनिर्णीत है। यह संगणनीयता सिद्धांत में कई लघुकरण की अवधारणा से निकटता से संबंधित है।

अर्धनिर्णायकता

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

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

पूर्णता से संबंध

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

संगणनीयता से संबंध

निर्णायक समुच्चय की अवधारणा के साथ, निर्णायक सिद्धांत या तार्किक प्रणाली की परिभाषा या तो प्रभावी तरीकों या गणना योग्य फलनों के संदर्भ में दी जा सकती है। इन्हें सामान्य रूप से प्रति चर्च की थीसिस के समान माना जाता है। वास्तव में, प्रमाण है कि एक तार्किक प्रणाली या सिद्धांत अनिर्णीत है, कम्प्यूटेबिलिटी (संगणनीयता) की औपचारिक परिभाषा का उपयोग यह दिखाने के लिए करेगा कि एक उपयुक्त समुच्चय एक निर्णायक समुच्चय नहीं है, और फिर चर्च की थीसिस को यह दिखाने के लिए उपयोग करें कि सिद्धांत या तार्किक प्रणाली किसी भी प्रभावी विधि (एंडर्टन 2001, पीपी 206ff) द्वारा निर्णायक नहीं है।

खेलों के संदर्भ में

कुछ खेलों को उनकी निर्णायकता के अनुसार वर्गीकृत किया गया है:

शतरंज निर्णायक है।^[5]^[6] परिशुद्ध जानकारी वाले अन्य सभी परिमित दो-खिलाड़ी खेलों के लिए भी यही प्रयुक्त होता है।
अनंत शतरंज में n में सहायक (नियमों और गेमपीस पर सीमाओं के साथ) निर्णायक है।^[7]^[8] हालांकि, ऐसी स्थितियाँ हैं (अंततः कई भागों के साथ) जो जीतने के लिए प्रणोदित हैं, लेकिन किसी सीमित n के लिए n में सहायक नहीं हैं।^[9]
सीमित बोर्ड (लेकिन असीमित समय के साथ) पर अपूर्ण जानकारी वाले कुछ समूह खेल अनिर्णीत हैं।^[10]

यह भी देखें

संदर्भ

↑ Trakhtenbrot, 1953 .
↑ ^2.0 ^2.1 Monk, Donald (1976). गणितीय तर्क. Springer. ISBN 9780387901701.
↑ Tarski, A.; Mostovski, A.; Robinson, R. (1953), Undecidable Theories, Studies in Logic and the Foundation of Mathematics, North-Holland, Amsterdam, ISBN 9780444533784
↑ Gurevich, Yuri (1976). "मानक कक्षाओं के लिए निर्णय समस्या". J. Symb. Log. 41 (2): 460–464. CiteSeerX 10.1.1.360.1517. doi:10.1017/S0022481200051513. S2CID 798307. Retrieved 5 August 2014.
↑ Stack Exchange Computer Science. "Is chess game movement TM decidable?"
↑ Undecidable Chess Problem?
↑ Mathoverflow.net/Decidability-of-chess-on-an-infinite-board Decidability-of-chess-on-an-infinite-board
↑ Brumleve, Dan; Hamkins, Joel David; Schlicht, Philipp (2012). "The Mate-in-n Problem of Infinite Chess Is Decidable". यूरोप में कम्प्यूटेबिलिटी पर सम्मेलन. Lecture Notes in Computer Science. Vol. 7318. Springer. pp. 78–88. arXiv:1201.5597. doi:10.1007/978-3-642-30870-3_9. ISBN 978-3-642-30870-3. S2CID 8998263.
↑ "Lo.logic – Checkmate in $\omega$ moves?".
↑ Poonen, Bjorn (2014). "10. Undecidable Problems: A Sampler: §14.1 Abstract Games". In Kennedy, Juliette (ed.). Interpreting Gödel: Critical Essays. Cambridge University Press. pp. 211–241 See p. 239. arXiv:1204.0299. CiteSeerX 10.1.1.679.3322. ISBN 9781107002661.}

ग्रन्थसूची

Barwise, Jon (1982), "Introduction to first-order logic", in Barwise, Jon (ed.), Handbook of Mathematical Logic, Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland, ISBN 978-0-444-86388-1
Cantone, D.; Omodeo, E. G.; Policriti, A. (2013) [2001], Set Theory for Computing. From Decision Procedures to Logic Programming with Sets, Monographs in Computer Science, Springer, ISBN 9781475734522
Chagrov, Alexander; Zakharyaschev, Michael (1997), Modal logic, Oxford Logic Guides, vol. 35, Oxford University Press, ISBN 978-0-19-853779-3, MR 1464942
Davis, Martin (2013) [1958], Computability and Unsolvability, Dover, ISBN 9780486151069
Enderton, Herbert (2001), A mathematical introduction to logic (2nd ed.), Academic Press, ISBN 978-0-12-238452-3
Keisler, H. J. (1982), "Fundamentals of model theory", in Barwise, Jon (ed.), Handbook of Mathematical Logic, Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland, ISBN 978-0-444-86388-1
Monk, J. Donald (2012) [1976], Mathematical Logic, Springer-Verlag, ISBN 9781468494525

[1] Trakhtenbrot, 1953 .

[Monk1976-2] 2.0 ^2.1 Monk, Donald (1976). गणितीय तर्क. Springer. ISBN 9780387901701.

[3] Tarski, A.; Mostovski, A.; Robinson, R. (1953), Undecidable Theories, Studies in Logic and the Foundation of Mathematics, North-Holland, Amsterdam, ISBN 9780444533784

[4] Gurevich, Yuri (1976). "मानक कक्षाओं के लिए निर्णय समस्या". J. Symb. Log. 41 (2): 460–464. CiteSeerX 10.1.1.360.1517. doi:10.1017/S0022481200051513. S2CID 798307. Retrieved 5 August 2014.

[5] Stack Exchange Computer Science. "Is chess game movement TM decidable?"

[6] Undecidable Chess Problem?

[Decidability-7] Mathoverflow.net/Decidability-of-chess-on-an-infinite-board Decidability-of-chess-on-an-infinite-board

[Mate_in_N-8] Brumleve, Dan; Hamkins, Joel David; Schlicht, Philipp (2012). "The Mate-in-n Problem of Infinite Chess Is Decidable". यूरोप में कम्प्यूटेबिलिटी पर सम्मेलन. Lecture Notes in Computer Science. Vol. 7318. Springer. pp. 78–88. arXiv:1201.5597. doi:10.1007/978-3-642-30870-3_9. ISBN 978-3-642-30870-3. S2CID 8998263.

[9] "Lo.logic – Checkmate in $\omega$ moves?".

[10] Poonen, Bjorn (2014). "10. Undecidable Problems: A Sampler: §14.1 Abstract Games". In Kennedy, Juliette (ed.). Interpreting Gödel: Critical Essays. Cambridge University Press. pp. 211–241 See p. 239. arXiv:1204.0299. CiteSeerX 10.1.1.679.3322. ISBN 9781107002661.}

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 1: / Line 1: @@
 {{Short description|Whether a decision problem has an effective method to derive the answer}}
-[[तर्क]] में, एक सही/गलत [[निर्णय समस्या]] निर्णायक होती है यदि सही उत्तर प्राप्त करने के लिए कोई [[प्रभावी तरीका]] मौजूद हो। [[शून्य-क्रम तर्क]] (प्रस्तावात्मक तर्क) निर्णायक है, जबकि प्रथम-क्रम तर्क | प्रथम-क्रम तर्क और उच्च-क्रम तर्क | उच्च-क्रम तर्क नहीं हैं। औपचारिक प्रणालियाँ निर्णायक होती हैं यदि उनकी [[वैधता (तर्क)]] सूत्रों (या प्रमेय) के सेट में सदस्यता प्रभावी ढंग से निर्धारित की जा सकती है। एक [[सिद्धांत (गणितीय तर्क)]] ([[तार्किक परिणाम]] के तहत वाक्यों का सेट [[डिडक्टिव क्लोजर]]) एक निश्चित तार्किक प्रणाली में निर्णायक है यदि यह निर्धारित करने के लिए एक प्रभावी तरीका है कि सिद्धांत में स्वैच्छिक सूत्र शामिल हैं या नहीं। कई महत्वपूर्ण समस्याएँ [[अनिर्णीत समस्या]]एँ हैं, अर्थात्, यह सिद्ध हो चुका है कि सदस्यता निर्धारित करने के लिए कोई प्रभावी तरीका (परिमित के बाद सही उत्तर देना, हालाँकि संभवतः बहुत लंबा, सभी मामलों में समय) उनके लिए मौजूद नहीं हो सकता है।
+तर्क में, सही/गलत निर्णय समस्या '''निर्णायक''' होती है यदि सही उत्तर प्राप्त करने के लिए कोई प्रभावी तरीका सम्मिलित हो। शून्य-क्रम तर्क (प्रस्तावात्मक तर्क) निर्णायक है, जबकि प्रथम-क्रम और उच्च-क्रम तर्क नहीं हैं। तार्किक रूप से मान्य सूत्रों (या प्रमेय) के उनके समुच्चय में सदस्यता प्रभावी रूप से निर्धारित की जा सकती है, तो तार्किक प्रणालियां निर्णायक हैं। औपचारिक प्रणालियाँ निर्णायक होती हैं यदि उनकी [[वैधता (तर्क)]] सूत्रों (या प्रमेय) के समुच्चय में सदस्यता प्रभावी रूप से निर्धारित की जा सकती है। निश्चित तार्किक प्रणाली में सिद्धांत (तार्किक परिणाम के अंतर्गत संवृत्त किए गए कथनों का समुच्चय) निर्णायक होता है यदि यह निर्धारित करने के लिए एक प्रभावी तरीका है कि सिद्धांत में एकपक्षीय सूत्र सम्मिलित हैं या नहीं है। कई महत्वपूर्ण समस्याएं अनिर्णीत हैं, अर्थात्, यह प्रमाणित हो गया है कि सदस्यता निर्धारित करने के लिए कोई प्रभावी तरीका नहीं है (परिमित के बाद एक सही उत्तर देना, हालांकि संभवतः बहुत लंबा, सभी स्थितियों में समय) उनके लिए सम्मिलित हो सकता है।
-== एक [[तार्किक प्रणाली]] की निर्णायकता ==
+== [[तार्किक प्रणाली]] की निर्णायकता ==
-प्रत्येक तार्किक प्रणाली एक [[सिंटेक्स (तर्क)]]तर्क) के साथ आती है, जो अन्य बातों के अलावा [[औपचारिक प्रमाण]] की धारणा को निर्धारित करती है, और एक [[औपचारिक शब्दार्थ (तर्क)]], जो [[तार्किक वैधता]] की धारणा को निर्धारित करता है। एक प्रणाली के तार्किक रूप से मान्य सूत्रों को कभी-कभी प्रणाली के प्रमेय कहा जाता है, विशेष रूप से प्रथम-क्रम तर्क के संदर्भ में जहां गोडेल की पूर्णता प्रमेय शब्दार्थ और वाक्य-विन्यास परिणाम की समानता स्थापित करता है। अन्य सेटिंग्स में, जैसे [[रैखिक तर्क]], सिंटैक्टिक परिणाम (प्रिवेबिलिटी) संबंध का उपयोग सिस्टम के प्रमेयों को परिभाषित करने के लिए किया जा सकता है।
+प्रत्येक तार्किक प्रणाली एक सिंटैक्टिक घटक के साथ आती है, जो अन्य वस्तुओ के साथ-साथ प्रवीणता की धारणा को निर्धारित करती है, और सिमेंटिक घटक, जो तार्किक वैधता की धारणा को निर्धारित करता है। एक प्रणाली के तार्किक रूप से मान्य सूत्रों को कभी-कभी प्रणाली के '''प्रमेय''' कहा जाता है, विशेष रूप से प्रथम-क्रम तर्क के संदर्भ में जहां गोडेल की पूर्णता प्रमेय सिमैन्टिक और सिंटैक्टिक परिणाम की समानता स्थापित करता है। अन्य स्थितियों में, जैसे रैखिक तर्क, सिंटैक्टिक परिणाम (प्रिवेबिलिटी) संबंध का उपयोग सिस्टम के प्रमेयों को परिभाषित करने के लिए किया जा सकता है।
-एक तार्किक प्रणाली निर्णायक होती है यदि यह निर्धारित करने के लिए एक प्रभावी तरीका है कि क्या मनमाने सूत्र तार्किक प्रणाली के प्रमेय हैं। उदाहरण के लिए, प्रस्तावपरक तर्क निर्णायक है, क्योंकि सत्य तालिका | सत्य-सारणी पद्धति का उपयोग यह निर्धारित करने के लिए किया जा सकता है कि क्या एक मनमाना तर्कवाक्य सूत्र तार्किक रूप से मान्य है।
+तार्किक प्रणाली निर्णायक होती है यदि यह निर्धारित करने के लिए एक प्रभावी तरीका है कि क्या स्वैच्छिक सूत्र तार्किक प्रणाली के प्रमेय हैं। उदाहरण के लिए, प्रस्तावपरक तर्क निर्णायक है, क्योंकि सत्य-सारणी पद्धति का उपयोग यह निर्धारित करने के लिए किया जा सकता है कि क्या एक एकपक्षीय तर्कवाक्य सूत्र तार्किक रूप से मान्य है।
-प्रथम-क्रम तर्क सामान्य रूप से निर्णायक नहीं होता है; विशेष रूप से, किसी भी [[हस्ताक्षर (तर्क)]] में तार्किक वैधताओं का सेट जिसमें समानता शामिल है और दो या अधिक तर्कों के साथ कम से कम एक अन्य विधेय निर्णायक नहीं है।<ref>[[Boris Trakhtenbrot|Trakhtenbrot]], 1953 <!-- This one? Trakhtenbrot BA. On recursive separability. InDoklady AN SSSR 1953 (Vol. 88, pp. 953-6) -->.</ref> प्रथम-क्रम तर्क को विस्तारित करने वाली तार्किक प्रणालियाँ, जैसे कि द्वितीय-क्रम तर्क और [[प्रकार सिद्धांत]], भी अनिर्णीत हैं।
+प्रथम-क्रम तर्क सामान्य रूप से निर्णायक नहीं होता है; विशेष रूप से, किसी भी [[हस्ताक्षर (तर्क)]] में तार्किक वैधताओं का समुच्चय जिसमें समानता सम्मिलित है और दो या अधिक तर्कों के साथ कम से कम एक अन्य निर्धारक निर्णायक नहीं है।<ref>[[Boris Trakhtenbrot|Trakhtenbrot]], 1953 <!-- This one? Trakhtenbrot BA. On recursive separability. InDoklady AN SSSR 1953 (Vol. 88, pp. 953-6) -->.</ref> प्रथम-क्रम तर्क को विस्तारित करने वाली तार्किक प्रणालियाँ, जैसे कि द्वितीय-क्रम तर्क और [[प्रकार सिद्धांत]], भी अनिर्णीत हैं।
-पहचान के साथ मोनडिक विधेय कलन की वैधता, हालांकि, निर्णायक हैं। यह प्रणाली प्रथम-क्रम तर्क है जो उन हस्ताक्षरों तक सीमित है जिनके पास कोई फ़ंक्शन प्रतीक नहीं है और समानता के अलावा जिनके संबंध प्रतीक कभी भी एक से अधिक तर्क नहीं लेते हैं।
+पहचान के साथ एकपदीय निर्धारक कलन की वैधता, हालांकि, निर्णायक हैं। यह प्रणाली प्रथम-क्रम तर्क है जो उन हस्ताक्षरों तक सीमित है जिनके पास कोई फ़ंक्शन प्रतीक नहीं है और समानता के अतिरिक्त जिनके संबंध प्रतीक कभी भी एक से अधिक तर्क नहीं लेते हैं।
-कुछ तार्किक प्रणालियाँ अकेले प्रमेयों के समुच्चय द्वारा पर्याप्त रूप से प्रदर्शित नहीं होती हैं। (उदाहरण के लिए, त्रिगुट तर्क | क्लेन के तर्क में कोई प्रमेय नहीं है।) ऐसे मामलों में, तार्किक प्रणाली की निर्णायकता की वैकल्पिक परिभाषाओं का अक्सर उपयोग किया जाता है, जो सूत्रों की वैधता की तुलना में कुछ अधिक सामान्य निर्धारित करने के लिए एक प्रभावी विधि की मांग करती हैं; उदाहरण के लिए, अनुक्रमों की वैधता, या तार्किक परिणाम {(जी, ए) | Г ⊧ A} तर्क।
+कुछ तार्किक प्रणालियाँ केवल प्रमेयों के समुच्चय द्वारा ही पर्याप्त रूप से प्रदर्शित नहीं होती हैं। (उदाहरण के लिए, क्लेन के तर्क में कोई भी प्रमेय नहीं है।) ऐसे स्थितियों में, तार्किक प्रणाली की निर्णायकता की वैकल्पिक परिभाषाओं का प्रायः उपयोग किया जाता है, जो सूत्रों की वैधता की तुलना में कुछ अधिक सामान्य निर्धारित करने के लिए एक प्रभावी विधि की मांग करती हैं; इंस्टेंस के लिए, अनुक्रमों की वैधता, या या परिणाम संबंध {(Г, ''A'') | Г ⊧ ''A''} तार्किक है।
-== एक सिद्धांत की निश्चितता ==
+== सिद्धांत की निर्णायकता ==
-एक सिद्धांत (गणितीय तर्क) सूत्रों का एक समूह है, जिसे अक्सर तार्किक परिणाम के तहत बंद माना जाता है। एक सिद्धांत के लिए निर्णायकता इस बात से संबंधित है कि क्या कोई प्रभावी प्रक्रिया है जो यह तय करती है कि सूत्र सिद्धांत का सदस्य है या नहीं, सिद्धांत के हस्ताक्षर में एक मनमाना सूत्र दिया गया है। निर्णायकता की समस्या स्वाभाविक रूप से तब उत्पन्न होती है जब सिद्धांत को सिद्धांतों के एक निश्चित सेट के तार्किक परिणामों के सेट के रूप में परिभाषित किया जाता है।
+सिद्धांत (गणितीय तर्क) सूत्रों का एक समुच्चय है, जिसे प्रायः तार्किक परिणाम के अंतर्गत संवृत माना जाता है। सिद्धांत के लिए निर्णायकता इस बात से संबंधित है कि क्या कोई प्रभावी प्रक्रिया है जो यह निर्धारित करती है कि सूत्र सिद्धांत का सदस्य है या नहीं, सिद्धांत के हस्ताक्षर में एक एकपक्षीय सूत्र दिया गया है। निर्णायकता की समस्या स्वाभाविक रूप से तब उत्पन्न होती है जब सिद्धांत को सिद्धांतों के एक निश्चित समुच्चय के तार्किक परिणामों के समुच्चय के रूप में परिभाषित किया जाता है।
-सिद्धांतों की निर्णायकता के बारे में कई बुनियादी परिणाम हैं। प्रत्येक (गैर-[[ परासंगत तर्क ]]) असंगत सिद्धांत निर्णायक है, क्योंकि सिद्धांत के हस्ताक्षर में प्रत्येक सूत्र एक तार्किक परिणाम होगा, और इस प्रकार सिद्धांत का एक सदस्य होगा। प्रत्येक पूर्ण सिद्धांत पुनरावर्ती गणना योग्य प्रथम-क्रम सिद्धांत निर्णायक है। एक निर्णायक सिद्धांत का विस्तार निर्णायक नहीं हो सकता है। उदाहरण के लिए, प्रस्तावपरक तर्क में अनिर्णीत सिद्धांत हैं, हालांकि वैधताओं का सेट (सबसे छोटा सिद्धांत) निर्णायक है।
+सिद्धांतों की निर्णायकता के बारे में कई आधारभूत परिणाम हैं। प्रत्येक (गैर-[[ परासंगत तर्क ]]) असंगत सिद्धांत निर्णायक है, क्योंकि सिद्धांत के हस्ताक्षर में प्रत्येक सूत्र एक तार्किक परिणाम होगा, और इस प्रकार सिद्धांत का एक सदस्य होगा। प्रत्येक पूर्ण सिद्धांत पुनरावर्ती गणना योग्य प्रथम-क्रम सिद्धांत निर्णायक है। निर्णायक सिद्धांत का विस्तार निर्णायक नहीं हो सकता है। उदाहरण के लिए, प्रस्तावपरक तर्क में अनिर्णीत सिद्धांत हैं, हालांकि वैधताओं का समुच्चय (सबसे छोटा सिद्धांत) निर्णायक है।
-एक सुसंगत सिद्धांत जिसमें संपत्ति है कि प्रत्येक सुसंगत विस्तार अनिर्णीत है, अनिवार्य रूप से अनिर्णीत कहा जाता है। वास्तव में, हर सुसंगत विस्तार अनिवार्य रूप से अनिर्णीत होगा। क्षेत्रों का सिद्धांत अनिर्णीत है लेकिन अनिवार्य रूप से अनिर्णीत नहीं है। [[रॉबिन्सन अंकगणित]] अनिवार्य रूप से अनिर्णीत होने के लिए जाना जाता है, और इस प्रकार हर सुसंगत सिद्धांत जिसमें रॉबिन्सन अंकगणित शामिल है या व्याख्या करता है, वह भी (अनिवार्य रूप से) अनिर्णीत है।
+सुसंगत सिद्धांत जिसमें गुण है कि प्रत्येक सुसंगत विस्तार अनिर्णीत है, अनिवार्य रूप से अनिर्णीत कहा जाता है। वास्तव में, प्रत्येक सुसंगत विस्तार अनिवार्य रूप से अनिर्णीत होगा। क्षेत्रों का सिद्धांत अनिर्णीत है लेकिन अनिवार्य रूप से अनिर्णीत नहीं है। [[रॉबिन्सन अंकगणित]] अनिवार्य रूप से अनिर्णीत होने के लिए जाना जाता है, और इस प्रकार प्रत्येक सुसंगत सिद्धांत जिसमें रॉबिन्सन अंकगणित सम्मिलित है या व्याख्या करता है, वह भी (अनिवार्य रूप से) अनिर्णीत है।
-निर्णायक प्रथम-क्रम के सिद्धांतों के उदाहरणों में [[वास्तविक बंद क्षेत्र]]ों का सिद्धांत और [[प्रेस्बर्गर अंकगणित]] शामिल हैं, जबकि समूह का सिद्धांत (गणित) और रॉबिन्सन अंकगणित अनिर्णीत सिद्धांतों के उदाहरण हैं।
+निर्णायक प्रथम-क्रम के सिद्धांतों के उदाहरणों में [[वास्तविक बंद क्षेत्र|वास्तविक संवृत क्षेत्रो]] का सिद्धांत और [[प्रेस्बर्गर अंकगणित]] सम्मिलित हैं, जबकि समुच्चय का सिद्धांत (गणित) और रॉबिन्सन अंकगणित अनिर्णीत सिद्धांतों के उदाहरण हैं।
 == कुछ निर्णायक सिद्धांत ==
-कुछ निर्णायक सिद्धांतों में शामिल हैं (मोंक 1976, पृष्ठ 234):<ref name=Monk1976 />* 1915 में लियोपोल्ड लोवेनहेम द्वारा स्थापित केवल समानता के साथ हस्ताक्षर में प्रथम-क्रम तार्किक वैधता का सेट।
+कुछ निर्णायक सिद्धांतों में सम्मिलित (मोंक 1976, पेज 234) हैं:<ref name=Monk1976 />
-* 1959 में Ehrenfeucht द्वारा स्थापित समानता और एक एकल कार्य के साथ एक हस्ताक्षर में प्रथम-क्रम तार्किक वैधता का सेट।
-* समानता और जोड़ के साथ हस्ताक्षर में प्राकृतिक संख्याओं का प्रथम-क्रम सिद्धांत, जिसे प्रेस्बर्गर अंकगणित भी कहा जाता है। पूर्णता 1929 में Mojzesz Presburger द्वारा स्थापित की गई थी।
+* 1915 में लियोपोल्ड लोवेनहेम द्वारा स्थापित केवल समानता के साथ हस्ताक्षर में प्रथम-क्रम तार्किक वैधता का समुच्चय।
+* 1959 में एरेनफ्यूच्ट द्वारा स्थापित समानता और एकल फलन के साथ हस्ताक्षर में प्रथम-क्रम तार्किक वैधता का समुच्चय।
+* समानता और जोड़ के साथ हस्ताक्षर में प्राकृतिक संख्याओं का प्रथम-क्रम सिद्धांत, जिसे प्रेस्बर्गर अंकगणित भी कहा जाता है। पूर्णता 1929 में मोजेज़ प्रेस्बर्गर द्वारा स्थापित की गई थी।
 * समानता और गुणन के साथ हस्ताक्षर में प्राकृतिक संख्याओं का प्रथम-क्रम सिद्धांत, जिसे स्कोलेम अंकगणित भी कहा जाता है।
 * 1940 में [[अल्फ्रेड टार्स्की]] द्वारा स्थापित बूलियन बीजगणित के पहले क्रम के सिद्धांत को विहित रूप से परिभाषित किया गया (1940 में पाया गया लेकिन 1949 में घोषित किया गया)।
-* तर्स्की द्वारा 1949 में स्थापित दी गई [[विशेषता (बीजगणित)]] के बीजगणितीय रूप से बंद क्षेत्रों का पहला क्रम सिद्धांत।
+* टारस्की द्वारा 1949 में स्थापित दी गई [[विशेषता (बीजगणित)]] के बीजगणितीय रूप से संवृत क्षेत्रों का पहला क्रम सिद्धांत।
-* [[वास्तविक संख्या के प्रथम-क्रम सिद्धांत की निर्णायकता]] | वास्तविक-बंद आदेशित क्षेत्रों का प्रथम-क्रम सिद्धांत, टार्स्की-सीडेनबर्ग प्रमेय (टार्स्की की घातीय कार्य समस्या भी देखें)।
+* 1949 में टार्स्की द्वारा स्थापित वास्तविक-संवृत क्रमित क्षेत्रों का प्रथम-क्रम सिद्धांत (टार्स्की की घातीय फलन समस्या भी देखें)।
 * 1949 में टार्स्की द्वारा स्थापित [[यूक्लिडियन ज्यामिति]] का प्रथम-क्रम सिद्धांत।
-* [[एबेलियन समूह]]ों का प्रथम-क्रम सिद्धांत, 1955 में स्ज़मील्यू द्वारा स्थापित किया गया।
+* [[एबेलियन समूह|एबेलियन समुच्चयो]] का प्रथम-क्रम सिद्धांत, 1955 में स्ज़मील्यू द्वारा स्थापित किया गया।
 * 1959 में श्वाभौसर द्वारा स्थापित अतिपरवलयिक ज्यामिति का प्रथम-क्रम सिद्धांत।
-* 1980 के दशक से लेकर आज तक सेट थ्योरी की विशिष्ट निर्णायक उपभाषाओं की जांच की गई। (कैंटोन एट अल।, 2001)
+* 1980 के दशक से लेकर आज तक समुच्चय सिद्धांत की विशिष्ट निर्णायक उपभाषाओं की जांच की गई। (कैंटोन एट अल, 2001)
-* सन्यासी दूसरे क्रम का तर्क | वृक्ष का द्वित्तीय क्रम सिद्धांत (ग्राफ़ सिद्धांत) (S2S (गणित) देखें)।
+* ट्री का एकपदीय द्वित्तीय क्रम सिद्धांत (ग्राफ़ सिद्धांत) (S2S (गणित) देखें)।
-निर्णायकता स्थापित करने के लिए उपयोग की जाने वाली विधियों में [[क्वांटिफायर उन्मूलन]], [[मॉडल पूर्णता]] और लोश-वॉच टेस्ट शामिल हैं।
+निर्णायकता स्थापित करने के लिए उपयोग की जाने वाली विधियों में [[क्वांटिफायर उन्मूलन|परिमाणक उन्मूलन]], [[मॉडल पूर्णता]] और लोश-वॉच परीक्षण सम्मिलित हैं।
 == कुछ अनिर्णीत सिद्धांत ==
-कुछ अनिर्णीत सिद्धांतों में शामिल हैं (मोंक 1976, पृष्ठ 279):<ref name="Monk1976">{{cite book |first=Donald |last=Monk |year =1976 |title =गणितीय तर्क|publisher =Springer |isbn =9780387901701 |url-access =registration |url =https://archive.org/details/mathematicallogi00jdon }}</ref>
+कुछ अनिर्णीत सिद्धांतों में सम्मिलित हैं (मोंक 1976, पृष्ठ 279):<ref name="Monk1976">{{cite book |first=Donald |last=Monk |year =1976 |title =गणितीय तर्क|publisher =Springer |isbn =9780387901701 |url-access =registration |url =https://archive.org/details/mathematicallogi00jdon }}</ref>
-* समानता के साथ किसी भी पहले-क्रम के हस्ताक्षर में तार्किक वैधताओं का सेट और या तो: 2 से कम नहीं, या दो यूनरी फ़ंक्शन प्रतीकों, या 2 से कम नहीं, 1953 में [[बोरिस ट्रेचटेनब्रॉट]] द्वारा स्थापित एरिटी का एक संबंध प्रतीक .
+* समानता के साथ किसी भी पहले-क्रम के हस्ताक्षर में तार्किक वैधताओं का समुच्चय और या तो: 2 से कम नहीं, या दो एकल फलन प्रतीकों, या 2 से कम नहीं, 1953 में [[बोरिस ट्रेचटेनब्रॉट]] द्वारा स्थापित एरिटी का एक फलन प्रतीक है।
 * 1949 में टार्स्की और [[आंद्रेज मोस्टोव्स्की]] द्वारा स्थापित योग, गुणन और समानता के साथ प्राकृतिक संख्याओं का पहला क्रम सिद्धांत।
 * 1949 में [[जूलिया रॉबिन्सन]] द्वारा स्थापित जोड़, गुणा और समानता के साथ परिमेय संख्याओं का प्रथम-क्रम सिद्धांत।
-* 1953 में अल्फ्रेड टार्स्की द्वारा स्थापित समूहों का पहला क्रम सिद्धांत।<ref>{{Citation| last1=Tarski| first1=A. | last2=Mostovski| first2=A. | last3=Robinson| first3=R. |  title=Undecidable Theories | publisher=North-Holland, Amsterdam | series=Studies in Logic and the Foundation of Mathematics | year=1953 |url=https://www.google.com/books/edition/Undecidable_Theories/XtLbjZjB1B8C?hl=en&pg=PP1 |isbn=9780444533784}}</ref> उल्लेखनीय रूप से, न केवल समूहों का सामान्य सिद्धांत अनिर्णीत है, बल्कि कई और विशिष्ट सिद्धांत भी हैं, उदाहरण के लिए (जैसा कि माल्सेव 1961 द्वारा स्थापित) परिमित समूहों का सिद्धांत। मालसेव ने यह भी स्थापित किया कि अर्धसमूहों का सिद्धांत और छल्लों का सिद्धांत अनिर्णीत हैं। रॉबिन्सन ने 1949 में स्थापित किया कि क्षेत्रों का सिद्धांत अनिर्णीत है।
+* 1953 में अल्फ्रेड टार्स्की द्वारा स्थापित समुच्चयों का पहला क्रम सिद्धांत<ref>{{Citation| last1=Tarski| first1=A. | last2=Mostovski| first2=A. | last3=Robinson| first3=R. |  title=Undecidable Theories | publisher=North-Holland, Amsterdam | series=Studies in Logic and the Foundation of Mathematics | year=1953 |url=https://www.google.com/books/edition/Undecidable_Theories/XtLbjZjB1B8C?hl=en&pg=PP1 |isbn=9780444533784}}</ref> उल्लेखनीय रूप से, न केवल समुच्चयों का सामान्य सिद्धांत अनिर्णीत है, बल्कि कई और विशिष्ट सिद्धांत भी हैं, उदाहरण के लिए (जैसा कि माल्सेव 1961 द्वारा स्थापित) परिमित समुच्चयों का सिद्धांत है। मालसेव ने यह भी स्थापित किया कि अर्धसमुच्चयों का सिद्धांत और वलयों का सिद्धांत अनिर्णीत हैं। रॉबिन्सन ने 1949 में स्थापित किया कि क्षेत्रों का सिद्धांत अनिर्णीत है।
-*रॉबिन्सन अंकगणित (और इसलिए कोई भी सुसंगत विस्तार, जैसे पीनो अंकगणित) अनिवार्य रूप से अनिर्णीत है, जैसा कि 1950 में [[राफेल रॉबिन्सन]] द्वारा स्थापित किया गया था।
+*रॉबिन्सन अंकगणित (और इसलिए कोई भी सुसंगत विस्तार, जैसे पियानों अंकगणित) अनिवार्य रूप से अनिर्णीत है, जैसा कि 1950 में [[राफेल रॉबिन्सन]] द्वारा स्थापित किया गया था।
-* समानता और दो कार्य प्रतीकों के साथ प्रथम-क्रम सिद्धांत<ref>{{cite journal |last=Gurevich |first=Yuri |date=1976 |title= मानक कक्षाओं के लिए निर्णय समस्या|url=http://dblp.uni-trier.de/rec/bib/journals/jsyml/Gurevich76 |journal= J. Symb. Log.|volume=41 |issue=2 |pages=460–464 |doi= 10.1017/S0022481200051513|access-date=5 August 2014|citeseerx=10.1.1.360.1517 |s2cid=798307 }}</ref>
+* समानता और दो फलन प्रतीकों के साथ प्रथम-क्रम सिद्धांत है।<ref>{{cite journal |last=Gurevich |first=Yuri |date=1976 |title= मानक कक्षाओं के लिए निर्णय समस्या|url=http://dblp.uni-trier.de/rec/bib/journals/jsyml/Gurevich76 |journal= J. Symb. Log.|volume=41 |issue=2 |pages=460–464 |doi= 10.1017/S0022481200051513|access-date=5 August 2014|citeseerx=10.1.1.360.1517 |s2cid=798307 }}</ref>
-व्याख्यात्मकता पद्धति का उपयोग अक्सर सिद्धांतों की अनिश्चितता को स्थापित करने के लिए किया जाता है। यदि एक अनिवार्य रूप से अनिर्णीत सिद्धांत टी एक सुसंगत सिद्धांत एस में व्याख्या योग्य है, तो एस भी अनिवार्य रूप से अनिर्णीत है। यह कम्प्यूटेबिलिटी सिद्धांत में कई-एक कमी की अवधारणा से निकटता से संबंधित है।
+व्याख्यात्मकता पद्धति का उपयोग प्रायः सिद्धांतों की अनिश्चितता को स्थापित करने के लिए किया जाता है। यदि एक अनिवार्य रूप से अनिर्णीत सिद्धांत ''T'' एक सुसंगत सिद्धांत ''S'' में व्याख्या योग्य है, तो ''S'' भी अनिवार्य रूप से अनिर्णीत है। यह संगणनीयता सिद्धांत में कई लघुकरण की अवधारणा से निकटता से संबंधित है।
-== अर्ध-अम्लता ==
+== अर्धनिर्णायकता ==
-एक सिद्धांत या तार्किक प्रणाली की एक संपत्ति जो निर्णायकता से कमजोर है, अर्ध-निर्णायकता है। एक सिद्धांत अर्धनिर्णीत होता है यदि कोई प्रभावी तरीका है, जो एक मनमाना सूत्र दिया जाता है, हमेशा सिद्धांत में सूत्र होने पर सही ढंग से बताएगा, लेकिन सिद्धांत में सूत्र नहीं होने पर या तो नकारात्मक उत्तर दे सकता है या कोई उत्तर नहीं दे सकता है। यदि प्रमेय (और केवल प्रमेय) उत्पन्न करने के लिए एक प्रभावी विधि है, तो प्रत्येक प्रमेय अंततः उत्पन्न होगा, तो एक तार्किक प्रणाली अर्ध-निर्णायक है। यह निर्णायकता से अलग है क्योंकि एक अर्धनिर्णायक प्रणाली में यह जाँचने के लिए कोई प्रभावी प्रक्रिया नहीं हो सकती है कि कोई सूत्र ''नहीं'' एक प्रमेय है।
+सिद्धांत या तार्किक प्रणाली का गुण जो निर्णायकता से दुर्बल है, और '''अर्ध-निर्णायकता''' है। एक सिद्धांत अर्धनिर्णीत होता है यदि कोई प्रभावी तरीका है, जो एकपक्षीय सूत्र दिया जाता है, हमेशा सिद्धांत में सूत्र होने पर सही रूप से बताएगा, लेकिन सिद्धांत में सूत्र नहीं होने पर या तो ऋणात्मक उत्तर दे सकता है या कोई उत्तर नहीं दे सकता है। यदि प्रमेय (और केवल प्रमेय) उत्पन्न करने के लिए एक प्रभावी विधि है, तो प्रत्येक प्रमेय अंततः उत्पन्न होगा, तो एक तार्किक प्रणाली अर्ध-निर्णायक है। यह निर्णायकता से अलग है क्योंकि एक अर्धनिर्णायक प्रणाली में यह जाँचने के लिए कोई प्रभावी प्रक्रिया नहीं हो सकती है कि कोई सूत्र नहीं एक प्रमेय है।
-प्रत्येक निर्णायक सिद्धांत या तार्किक प्रणाली अर्ध-निर्णायक होती है, लेकिन सामान्य तौर पर इसका विलोम सत्य नहीं होता है; एक सिद्धांत निर्णायक है अगर और केवल अगर यह और इसके पूरक दोनों अर्ध-निर्णायक हैं। उदाहरण के लिए, पहले क्रम के तर्क की तार्किक वैधता का सेट ''वी'' अर्ध-निर्णायक है, लेकिन निर्णायक नहीं है। इस मामले में, ऐसा इसलिए है क्योंकि मनमानी सूत्र ''ए'' के निर्धारण के लिए कोई प्रभावी तरीका नहीं है कि क्या ''ए'' ''वी'' में नहीं है। इसी तरह, प्रथम-क्रम के स्वयंसिद्धों के किसी भी [[पुनरावर्ती गणना योग्य सेट]] के तार्किक परिणामों का सेट अर्ध-निर्णायक है। ऊपर दिए गए अनिर्णीत प्रथम-क्रम सिद्धांतों के कई उदाहरण इस रूप के हैं।
+प्रत्येक निर्णायक सिद्धांत या तार्किक प्रणाली अर्ध-निर्णायक होती है, लेकिन सामान्य रूप से इसका उत्क्रम सत्य नहीं होता है; एक सिद्धांत निर्णायक है यदि और केवल यदि यह और इसके पूरक दोनों अर्ध-निर्णायक हैं। उदाहरण के लिए, पहले क्रम के तर्क की तार्किक वैधता का समुच्चय ''V'' अर्ध-निर्णायक है, लेकिन निर्णायक नहीं है। इस स्थिति में, ऐसा इसलिए है क्योंकि एकपक्षीय सूत्र ''A'' के निर्धारण के लिए कोई प्रभावी तरीका नहीं है कि क्या ''A,'' ''V'' में नहीं है। इसी तरह, प्रथम-क्रम के स्वयंसिद्धों के किसी भी [[पुनरावर्ती गणना योग्य सेट|पुनरावर्ती गणना योग्य समुच्चय]] के तार्किक परिणामों का समुच्चय अर्ध-निर्णायक है। ऊपर दिए गए अनिर्णीत प्रथम-क्रम सिद्धांतों के कई उदाहरण इस रूप के हैं।
 == पूर्णता से संबंध ==
-निर्णायकता को पूर्ण सिद्धांत के साथ भ्रमित नहीं होना चाहिए। उदाहरण के लिए, बीजगणितीय रूप से बंद क्षेत्रों का सिद्धांत निर्णायक है, लेकिन अधूरा है, जबकि + और × वाली भाषा में गैर-नकारात्मक पूर्णांकों के बारे में सभी सत्य प्रथम-क्रम कथनों का सेट पूर्ण है लेकिन अनिर्णीत है।
+निर्णायकता को पूर्ण सिद्धांत के साथ भ्रमित नहीं होना चाहिए। उदाहरण के लिए, बीजगणितीय रूप से संवृत क्षेत्रों का सिद्धांत निर्णायक है, लेकिन अधूरा है, जबकि + और × वाली भाषा में गैर-ऋणात्मक पूर्णांकों के बारे में सभी सत्य प्रथम-क्रम कथनों का समुच्चय पूर्ण है लेकिन अनिर्णीत है। दुर्भाग्य से, एक पारिभाषिक अस्पष्टता के रूप में, अनिश्चित कथन पद को कभी-कभी [[स्वतंत्रता (गणितीय तर्क)|स्वतंत्र कथन (गणितीय तर्क)]] के उपपद के रूप में प्रयोग किया जाता है।
-दुर्भाग्य से, एक पारिभाषिक अस्पष्टता के रूप में, अनिर्णीत कथन शब्द को कभी-कभी [[स्वतंत्रता (गणितीय तर्क)]] के पर्याय के रूप में प्रयोग किया जाता है।
-== कम्प्यूटेबिलिटी से संबंध ==
+== संगणनीयता से संबंध ==
-एक [[निर्णायक सेट]] की अवधारणा के साथ, एक निर्णायक सिद्धांत या तार्किक प्रणाली की परिभाषा या तो प्रभावी तरीकों या गणना योग्य कार्यों के संदर्भ में दी जा सकती है। इन्हें आम तौर पर प्रति चर्च की थीसिस के बराबर माना जाता है। वास्तव में, सबूत है कि एक तार्किक प्रणाली या सिद्धांत अनिर्णीत है, कम्प्यूटेबिलिटी की औपचारिक परिभाषा का उपयोग यह दिखाने के लिए करेगा कि एक उपयुक्त सेट एक निर्णायक सेट नहीं है, और फिर चर्च की थीसिस को यह दिखाने के लिए आमंत्रित करें कि सिद्धांत या तार्किक प्रणाली किसी भी प्रभावी द्वारा निर्णायक नहीं है। विधि (एंडर्टन 2001, पीपी। 206ff।)।
+[[निर्णायक सेट|निर्णायक समुच्चय]] की अवधारणा के साथ, निर्णायक सिद्धांत या तार्किक प्रणाली की परिभाषा या तो प्रभावी तरीकों या गणना योग्य फलनों के संदर्भ में दी जा सकती है। इन्हें सामान्य रूप से प्रति चर्च की थीसिस के समान माना जाता है। वास्तव में, प्रमाण है कि एक तार्किक प्रणाली या सिद्धांत अनिर्णीत है, कम्प्यूटेबिलिटी (संगणनीयता) की औपचारिक परिभाषा का उपयोग यह दिखाने के लिए करेगा कि एक उपयुक्त समुच्चय एक निर्णायक समुच्चय नहीं है, और फिर चर्च की थीसिस को यह दिखाने के लिए उपयोग करें कि सिद्धांत या तार्किक प्रणाली किसी भी प्रभावी विधि (एंडर्टन 2001, पीपी 206ff) द्वारा निर्णायक नहीं है।
-== [[खेल]]ों के संदर्भ में ==
+== खेलों के संदर्भ में ==
 कुछ खेलों को उनकी निर्णायकता के अनुसार वर्गीकृत किया गया है:
-* [[शतरंज]] निर्णायक है।<ref>[https://cs.stackexchange.com/q/47722 Stack Exchange Computer Science. "Is chess game movement TM decidable?"]</ref><ref>[https://www.redhotpawn.com/forum/posers-and-puzzles/undecidable-chess-problem.90513 Undecidable Chess Problem?]</ref> सटीक जानकारी वाले अन्य सभी परिमित दो-खिलाड़ी खेलों के लिए भी यही है।
+* [[शतरंज]] निर्णायक है।<ref>[https://cs.stackexchange.com/q/47722 Stack Exchange Computer Science. "Is chess game movement TM decidable?"]</ref><ref>[https://www.redhotpawn.com/forum/posers-and-puzzles/undecidable-chess-problem.90513 Undecidable Chess Problem?]</ref> परिशुद्ध जानकारी वाले अन्य सभी परिमित दो-खिलाड़ी खेलों के लिए भी यही प्रयुक्त होता है।
-* [[अनंत शतरंज]] में एन में मेट (नियमों और गेमपीस पर सीमाओं के साथ) निर्णायक है।<ref name="Decidability">[https://mathoverflow.net/q/27967 Mathoverflow.net/Decidability-of-chess-on-an-infinite-board Decidability-of-chess-on-an-infinite-board]</ref><ref name="Mate in N">{{cite book |first1=Dan |last1=Brumleve |first2=Joel David |last2=Hamkins |first3=Philipp |last3=Schlicht |chapter=The Mate-in-n Problem of Infinite Chess Is Decidable |chapter-url=https://link.springer.com/chapter/10.1007%2F978-3-642-30870-3_9 |title=यूरोप में कम्प्यूटेबिलिटी पर सम्मेलन|publisher=Springer |date=2012 |isbn=978-3-642-30870-3 |pages=78–88 |doi=10.1007/978-3-642-30870-3_9 |series=Lecture Notes in Computer Science |volume=7318 |arxiv=1201.5597|s2cid=8998263 }}</ref> हालांकि, ऐसे स्थान हैं (बहुत सारे टुकड़ों के साथ) जो जीतने के लिए मजबूर हैं, लेकिन किसी परिमित एन के लिए एन में दोस्त नहीं हैं।<ref>{{Cite web|url=https://mathoverflow.net/q/63423 |title=Lo.logic – Checkmate in $\omega$ moves?}}</ref>
+* [[अनंत शतरंज]] में n में सहायक (नियमों और गेमपीस पर सीमाओं के साथ) निर्णायक है।<ref name="Decidability">[https://mathoverflow.net/q/27967 Mathoverflow.net/Decidability-of-chess-on-an-infinite-board Decidability-of-chess-on-an-infinite-board]</ref><ref name="Mate in N">{{cite book |first1=Dan |last1=Brumleve |first2=Joel David |last2=Hamkins |first3=Philipp |last3=Schlicht |chapter=The Mate-in-n Problem of Infinite Chess Is Decidable |chapter-url=https://link.springer.com/chapter/10.1007%2F978-3-642-30870-3_9 |title=यूरोप में कम्प्यूटेबिलिटी पर सम्मेलन|publisher=Springer |date=2012 |isbn=978-3-642-30870-3 |pages=78–88 |doi=10.1007/978-3-642-30870-3_9 |series=Lecture Notes in Computer Science |volume=7318 |arxiv=1201.5597|s2cid=8998263 }}</ref> हालांकि, ऐसी स्थितियाँ हैं (अंततः कई भागों के साथ) जो जीतने के लिए प्रणोदित हैं, लेकिन किसी सीमित n के लिए n में सहायक नहीं हैं।<ref>{{Cite web|url=https://mathoverflow.net/q/63423 |title=Lo.logic – Checkmate in $\omega$ moves?}}</ref>
-* परिमित बोर्ड (लेकिन असीमित समय के साथ) पर अपूर्ण जानकारी वाले कुछ टीम गेम अनिर्णीत हैं।<ref>{{cite book |first=Bjorn |last=Poonen |chapter=10. Undecidable Problems: A Sampler: §14.1 Abstract Games |chapter-url=https://www.google.com/books/edition/Interpreting_Godel/ulw3BAAAQBAJ?hl=en&pg=PA211 |editor-first=Juliette |editor-last=Kennedy |title=Interpreting Gödel: Critical Essays |publisher=Cambridge University Press |date=2014 |isbn=9781107002661 |pages=211–241 See p. 239 |arxiv=1204.0299 |citeseerx=10.1.1.679.3322}}}</ref>
+* सीमित बोर्ड (लेकिन असीमित समय के साथ) पर अपूर्ण जानकारी वाले कुछ समूह खेल अनिर्णीत हैं।<ref>{{cite book |first=Bjorn |last=Poonen |chapter=10. Undecidable Problems: A Sampler: §14.1 Abstract Games |chapter-url=https://www.google.com/books/edition/Interpreting_Godel/ulw3BAAAQBAJ?hl=en&pg=PA211 |editor-first=Juliette |editor-last=Kennedy |title=Interpreting Gödel: Critical Essays |publisher=Cambridge University Press |date=2014 |isbn=9781107002661 |pages=211–241 See p. 239 |arxiv=1204.0299 |citeseerx=10.1.1.679.3322}}}</ref>
 == यह भी देखें ==
 {{Portal|Philosophy}}
-* [[निर्णय समस्या]]
+* [[निर्णय समस्या|निर्णय की समस्या]]
-* [[अस्तित्वगत परिमाणीकरण]]<!--
+* [[अस्तित्वगत परिमाणीकरण]]
-Full citations are needed:
-*[[László Kalmár]] (1936)
-*[[Alonzo Church]] (1956)
-*[[W. V. O. Quine]] (1953)
-*Meyer and [[Karel Lambert|Lambert]] (1967)-->