Nonlinear Arithmetic with SMTLIB Division is Undecidable

कल्पना कीजिए कि आप एक जासूस हैं जो नियमों के एक बहुत ही सख्त सेट का उपयोग करके एक रहस्य को सुलझाने की कोशिश कर रहे हैं। कंप्यूटर विज्ञान की दुनिया में, इन नियमों को "थ्योरीज़" (theories) कहा जाता है, और वे कंप्यूटर को यह तय करने में मदद करती हैं कि क्या किसी गणितीय पहेली का कोई समाधान है या नहीं।

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

वह "जादुई" नियम जो खेल को बिगाड़ देता है

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

हालाँकि, लेखक, देजान जोवनोविक (Dejan Jovanović) ने आधिकारिक नियम पुस्तिका (SMTLIB मानक) में एक छिपे हुए जाल की खोज की। यह जाल इस बात में है कि नियम शून्य से विभाजन (division by zero) को कैसे संभालते हैं।

सामान्य गणित में, शून्य से भाग देना एक बड़ा "नहीं" है। लेकिन इस विशिष्ट कंप्यूटर नियम पुस्तिका में, नियम कहते हैं: "यदि आप शून्य से विभाजित करते हैं, तो हमें परवाह नहीं है कि उत्तर क्या है। यह कुछ भी हो सकता है, जब तक कि यह एक सामान्य संख्या की तरह व्यवहार करता है जब आप शून्य से विभाजित नहीं कर रहे होते हैं।"

लेखक इसे एक "अनइंटरप्रिटेड फंक्शन" (uninterpreted function) कहते हैं। इसे समझाने के लिए एक उदाहरण लें: कल्पना कीजिए कि एक वेंडिंग मशीन है जो आपके द्वारा खरीदे गए हर स्नैक के लिए पूरी तरह से काम करती है। लेकिन यदि आप "जीरो स्नैक" खरीदने की कोशिश करते हैं, तो मशीन क्रैश नहीं होती है; इसके बजाय, यह कुछ थूक देती है—शायद एक कैंडी बार, शायद एक पत्थर, या शायद एक बादल। नियम यह नहीं बताते कि वह क्या होगा; वे बस कहते हैं: "यह कुछ होगा।"

यह खेल को हल करने के लिए असंभव कैसे बनाता है

लेखक का तर्क है कि शून्य विभाजन के लिए यह "कुछ भी चलेगा" वाला नियम अराजकता के दरवाजे को खोलने वाली कुंजी है।

यहाँ तर्क दिया गया है, जिसे सरल बनाया गया है:

1. लक्ष्य: लेखक यह सिद्ध करना चाहता है कि यदि आपके पास यह "जादुई" विभाजन नियम है, तो आप कंप्यूटर को पूर्णांक (integer) पहेलियाँ (पूर्ण संख्याओं जैसे 1, 2, 3 वाली पहेलियाँ) हल करने के लिए मजबूर कर सकते हैं।
2. समस्या: पूर्णांक पहेलियों को हल करना कंप्यूटर के लिए पूरी तरह से संभव नहीं है (इसे हिल्बर्ट की 10वीं समस्या के रूप में जाना जाता है। यह घास के ढेर में सुई खोजने जैसा है जो अनंत तक बढ़ता रहता है)।
3. चाल: लेखक दिखाता है कि इस "जादुिक" शून्य विभाजन का उपयोग करके, आप एक गणितीय पुल बना सकते हैं। आप एक कठिन पूर्णांक पहेली को वास्तविक संख्याओं की पहेली में बदल सकते हैं (इस विभाजन ट्रिक का उपयोग करके)।
   • उपमा: कल्पना कीजिए कि आपके पास एक गुप्त कोड है जो केवल मनुष्यों द्वारा समझी जाने वाली भाषा (पूर्णांक) में लिखा गया है। आप एक मशीन (विभाजन ट्रिक) बनाते हैं जो इस कोड को उस भाषा में अनुवादित करती है जिसे कंप्यूटर समझते हैं (वास्तविक संख्याएँ)। क्योंकि कंप्यूटर की भाषा में यह "जादुई" शून्य-विभाजन नियम है, कंप्यूटर अनजाने में मानव कोड को हल कर सकता है।
4. परिणाम: चूंकि हम जानते हैं कि कंप्यूटर सभी पूर्णांक पहेलियों को हल नहीं कर सकते, और यह ट्रिक उन्हें वास्तविक संख्याओं का उपयोग करके पूर्णांक पहेलियों को हल करने की कोशिश करने देती है, इसका मतलब है कि कंप्यूटर सभी वास्तविक-संख्या पहेलियों को भी हल नहीं कर सकता। खेल अनिर्णीत (undecidable) हो जाता है।

"फ्लोर" (Floor) फंक्शन की उपमा

इसे सिद्ध करने के लिए, लेखक एक चतुर ट्रिक का उपयोग करता है। वे दिखाते हैं कि यदि आपके पास यह "जादुई" विभाजन है, तो आप कंप्यूटर को एक फ्लोर फंक्शन (floor function) की तरह कार्य करने के लिए मजबूर कर सकते हैं (एक ऐसा फंक्शन जो एक संख्या को निकटतम पूर्ण संख्या तक नीचे की ओर राउंड करता है, जैसे 3.9 को 3 में बदलना)।

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

इसका वास्तविक दुनिया में क्या अर्थ है (पेपर के अनुसार)

यह शोध पत्र भविष्य के AI या चिकित्सा उपयोगों के बारे में बात नहीं करता है। यह कंप्यूटर बेंचमार्क (परीक्षण समस्याओं) की वर्तमान स्थिति पर केंद्रित है:

• जाल: SMTLIB लाइब्रेरी (कंप्यूटरों का परीक्षण करने के लिए उपयोग किए जाने वाले परीक्षण समस्याओं का एक विशाल संग्रह) में कई मौजूदा परीक्षण समस्याएँ चर (variables) के साथ विभाजन (जैसे x / y) का उपयोग करती हैं। यदि y शून्य होता है, तो ये पहेलियाँ "अनिर्णीत" जाल में गिर जाती हैं।
• समाधान? लेखक नियम पुस्तिका को ठीक करने के दो तरीके सुझाते हैं:
  1. एक विशिष्ट उत्तर चुनें: यह तय करें कि शून्य से विभाजित करना हमेशा एक विशिष्ट संख्या के बराबर होता है (जैसे 0 या 1), ठीक वैसे ही जैसे कुछ कंप्यूटर सिस्टम बाइनरी नंबरों के लिए इसे संभालते हैं।
  2. खेल को विभाजित करें: उन समस्याओं के लिए एक नया, अलग श्रेणी बनाएँ जहाँ आप चर (variables) के साथ विभाजित करते हैं, और "सुरक्षित" श्रेणी को रखें जहाँ आप केवल ज्ञात संख्याओं (constants) से विभाजित करते हैं।

निचोड़

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