गोडेल की अपूर्णता और संगणना

गोडेल के अपूर्णता प्रमेय दर्शाते हैं कि कोई भी पर्याप्त रूप से सुदृढ़, सुसंगत औपचारिक प्रणाली ऐसे सत्य कथन समाहित करती है जिन्हें वह सिद्ध नहीं कर सकती, यह परिणाम संगणनीयता सिद्धांत में खोजी गई अनिर्णेयता (undecidability) से गहराई से जुड़ा हुआ है।

Definition

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

Scope

यह विषय प्रथम और द्वितीय अपूर्णता प्रमेयों, अंकगणितिकरण (arithmetization) की तकनीक और गोडेल संख्यांकन (Gödel numbering) के माध्यम से स्व-संदर्भ, अपूर्णता और हॉल्टिंग समस्या (halting problem) की अनिर्णेयता तथा प्रथम-क्रम तर्क (first-order logic) के बीच घनिष्ठ संबंध, और औपचारिक तर्क तथा स्वचालित प्रमाण की सीमाओं के परिणामों को शामिल करता है।

Core questions

• कोई भी सुसंगत, पर्याप्त रूप से सुदृढ़ औपचारिक प्रणाली सभी सत्य अंकगणितीय कथनों को क्यों सिद्ध नहीं कर सकती?
• गोडेल संख्यांकन के माध्यम से स्व-संदर्भ एक अप्रमाणित सत्य वाक्य कैसे उत्पन्न करता है?
• अपूर्णता और हॉल्टिंग समस्या की अनिर्णेयता एक ही घटना के दो दृष्टिकोण कैसे हैं?
• स्वचालित प्रमेय सिद्ध करने की सीमाओं के लिए अपूर्णता का क्या अर्थ है?

Key theories

प्रथम अपूर्णता प्रमेय

कोई भी सुसंगत औपचारिक प्रणाली जो अंकगणित को एन्कोड करने के लिए पर्याप्त मजबूत है, एक सत्य कथन को समाहित करती है जिसे वह न तो सिद्ध कर सकती है और न ही खंडन कर सकती है, जिसे एक ऐसे वाक्य द्वारा निर्मित किया जाता है जो प्रभावी रूप से अपनी स्वयं की अप्रमाणनीयता का दावा करता है।

संगणनीयता के माध्यम से अपूर्णता

अपूर्णता हॉल्टिंग समस्या की अनिर्णेयता से उत्पन्न होती है: यदि प्रत्येक अंकगणितीय सत्य सिद्ध करने योग्य होता, तो कोई प्रमाणों की खोज करके हॉल्टिंग का निर्णय कर सकता था, इसलिए अनिर्णेय समस्याओं का अस्तित्व अप्रमाणित सत्यों के अस्तित्व को मजबूर करता है।

Clinical relevance

अपूर्णता और इसके संगणनात्मक समकक्ष स्वचालित तर्क पर कठोर सीमाएँ लगाते हैं: कोई भी एल्गोरिथम सभी अंकगणितीय सत्यों का निर्णय नहीं कर सकता या हर गणितीय प्रश्न का समाधान नहीं कर सकता, इसलिए प्रमेय सिद्ध करने वाले (theorem provers) और सत्यापन प्रणालियों (verification systems) को पूर्ण स्वचालित निर्णय के बजाय मानवीय मार्गदर्शन, प्रतिबंधित सिद्धांतों या संवादात्मक प्रमाण पर निर्भर रहना पड़ता है।

History

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

Key figures

• Kurt Gödel
• Alan Turing
• Alonzo Church
• John Barkley Rosser

Seminal works

• godel1931
• boolos2007

Frequently asked questions

क्या अपूर्णता का मतलब है कि गणित टूट गया है?

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

गोडेल का प्रमेय हॉल्टिंग समस्या से कैसे संबंधित है?

वे घनिष्ठ रूप से जुड़े हुए हैं। हॉल्टिंग समस्या की असुलभता अपूर्णता को दर्शाती है: यदि एक औपचारिक प्रणाली उन सभी सत्यों को सिद्ध कर सकती थी कि कौन से प्रोग्राम रुकते हैं, तो कोई प्रमाणों की खोज करके हॉल्टिंग का निर्णय कर सकता था, जो ट्यूरिंग के परिणाम का खंडन करता है। दोनों, तर्क और संगणना में, औपचारिक विधि की समान मौलिक सीमाओं को व्यक्त करते हैं।