Proof Theory and Dependent Type Theory: Distinct Foundations for Designing Proof Assistants
यह शोध पत्र तर्क देता है कि आधुनिक संरचनात्मक प्रमाण सिद्धांत (structural proof theory), जिसका उदाहरण सीक्वेंट कैलकुलस (sequent calculus) है और जिसे एबेला (Abella) थ्योरम प्रूवर में कार्यान्वित किया गया है, तर्क को प्रमाण संरचना से बेहतर ढंग से अलग करने, गैर-निर्धारणवाद (non-determinism) का रणनीतिक उपयोग करने, जटिल टाइपिंग संबंधी समस्याओं से बचने और बाइंडिंग्स (bindings) को संभालने के लिए एक सुरुचिपूर्ण दृष्टिकोण प्रदान करने के माध्यम से, प्रूफ असिस्टेंट्स को डिजाइन करने के लिए डिपेंडेंट टाइप थ्योरी (dependent type theory) का एक सम्मोहक विकल्प प्रस्तुत करता है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कल्पना कीजिए कि आप एक परम "प्रूफ असिस्टेंट" (Proof Assistant) बनाने की कोशिश कर रहे हैं—एक सुपर-स्मार्ट रोबोट जो मनुष्यों को उनका गणित और तर्क का होमवर्क चेक करने में मदद करता है ताकि यह सुनिश्चित हो सके कि वह 100% सही है। दशकों से, अधिकांश रोबोटों को एक विशिष्ट ब्लूप्रिंट का उपयोग करके बनाया गया है जिसे डिपेंडेंट टाइप थ्योरी (Dependent Type Theory - DTT) कहा जाता है। यह एक बहुत ही जटिल, हाई-टेक लेगो (Lego) सेट की तरह है जहाँ हर एक ईंट पर एक विशिष्ट लेबल होता है, और रोबोट यह जाँचता है कि लेबल पूरी तरह से मेल खाते हैं या नहीं, इससे पहले कि वह आपको उन्हें आपस में जोड़ने दे।
लेकिन इस पेपर में, लेखक डेल मिलर (Dale Miller) सुझाव देते हैं कि हमारे पास एक दूसरा, शायद बेहतर, तरीका है जिससे इन रोबोटों को बनाया जा सकता है। वे तर्क देते हैं कि हमें स्ट्रक्चरल प्रूफ थ्योरी (Structural Proof Theory) को देखना चाहिए, विशेष रूप से एक फ्रेमवर्क जिसे सीक्वेंट कैलकुलस (Sequent Calculus) कहा जाता है। इसे इस तरह न सोचें कि यह एक कठोर लेगो सेट है, बल्कि इसे एक गतिशील, चलते-फिरते पहेली के रूप में देखें जहाँ टुकड़े तब तक इधर-उधर खिसक सकते हैं और आकार बदल सकते हैं जब तक कि तर्क बना रहता है।
यहाँ मिलर के इस विचार का विवरण दिया गया है कि यह "पहेली" दृष्टिकोण "लेगो" दृष्टिकोण की तुलना में क्यों बेहतर हो सकता है, छह प्रमुख विचारों का उपयोग करते हुए:
1. "क्या" और "कैसे" को अलग करना
लेगो की दुनिया (DTT) में, रोबोट दो चीजें एक साथ तय करता है: आप क्या तर्क (logic) उपयोग कर रहे हैं और प्रमाण (proof) कैसे बनाया गया है। यह ऐसा कहने जैसा है, "हमें केवल लाल ईंटों का उपयोग करके टावर बनाने की अनुमति है, और एकमात्र तरीका उन्हें सीधा ऊपर रखना है।"
मिलर सुझाव देते हैं कि हमें इन्हें अलग करना चाहिए। हम तर्क (खेल के नियम) तय कर सकते हैं और फिर हम कोई भी प्रमाण संरचना चुन सकते हैं जो उसे हल करे। यह ऐसा है जैसे आप तय करते हैं कि आप फुटबॉल खेलना चाहते हैं, और फिर आपको एहसास होता है कि आप गोल करने के लिए किक, हेडिंग, या यदि नियम अनुमति दें तो नेट-कैनन का उपयोग भी कर सकते हैं। सीक्वेंट कैलकुलस आपको कई अलग-अलग "चालें" (जैसे नेचुरल डडक्शन, टेबलो, या रेज़ोल्यूशन) उपयोग करने की अनुमति देता है बिना आपको एक एकल, कठोर शैली में मजबूर किए।
2. "प्रूफ ऐज़ कोड" (Proofs as Code) की समस्या
लेगो दृष्टिकोण प्रमाण को एक कंप्यूटर प्रोग्राम (एक λ-term) की तरह मानता है। जबकि कंप्यूटर प्रोग्राम चलाने में बहुत अच्छे होते हैं, वे थोड़े नखरेबाज हो सकते हैं। कभी-कभी, प्रोग्राम उत्तर तक पहुँचने के लिए एक अजीब रास्ता लेता है, या वह अटक जाता है क्योंकि वह एक विशिष्ट प्रकार के इनपुट का इंतज़ार कर रहा होता है।
मिलर बताते हैं कि लेगो दृष्टिकोण को "यूनिवर्स लेवल" (टाइप्स को व्यवस्थित करने का एक जटिल तरीका ताकि वे आपस में न टकराएं) और "प्रूफ इरेलेवेंस" (उन हिस्सों की जाँच करने में समय बर्बाद करना जो वास्तव में मायने नहीं रखते) जैसे उलझे हुए मुद्दों से निपटना पड़ता है। सीक्वेंट कैलकुलस दृष्टिकोण सरल है; इसे भारी टाइपिंग नियमों की चिंता करने की आवश्यकता नहीं है क्योंकि यह प्रमाण संरचना को सीधे एक जटिल कोड स्क्रिप्ट के बजाय एक फ्लोचार्ट की तरह मानता है।
3. "क्लासिकल" तर्क को संभालना (Either/Or की समस्या)
कुछ तर्क "इंट्यूशनिस्टिक" (intuitionistic) होते हैं (आपको कुछ अस्तित्व में होने को सिद्ध करने के लिए उसे बनाना होगा) और कुछ "क्लासिकल" (classical) होते हैं (आप यह दिखाकर भी सिद्ध कर सकते हैं कि कुछ अस्तित्व में होना असंभव नहीं है)।
लेगो दृष्टिकोण "क्लासिकल" शैली को सुचारू रूप से संभालने में संघर्ष करता है। इसे काम करने के लिए अक्सर अतिरिक्त, बोझिल नियम जोड़ने पड़ते हैं। मिलर का तर्क है कि सीक्वेंट कैलकुलस को शुरू से ही दोनों शैलियों को समान रूप से संभालने के लिए डिज़ाइन किया गया था, जैसे कि एक यूनिवर्सल अडैप्टर जो बिना किसी भारी कनवर्टर के किसी भी प्लग में फिट हो जाता है।
4. "शायद" को अपनाना (Non-Determinism)
यह एक बड़ा बिंदु है। लेगो रोबोट "डिटरमिनिस्टिक" (deterministic) बनाए जाते हैं, जिसका अर्थ है कि उन्हें एक प्रमाण की जाँच करने के लिए एक एकल, सीधे पथ का पालन करना चाहिए। यदि वे डेड एंड (बंद रास्ते) पर पहुँचते हैं, तो वे रुक जाते हैं।
मिलर सुझाव देते हैं कि थोड़ी सी "नॉन-डिटरमिनिज्म" (अनुमान लगाना और बैकट्रैक करना) को अनुमति देना वास्तव में एक सुपरपावर है। एक भूलभुलैया की कल्पना करें। एक डिटरमिनिस्टिक रोबोट एक पथ पर चलता है और यदि वह दीवार से टकराता है, तो रुक जाता है। एक नॉन-डिटरमिनिस्टिक रोबोट एक पथ आज़मा सकता है, दीवार से टकरा सकता है, "ओह्स" कह सकता है, और तुरंत एक अलग पथ आज़मा सकता है।
मिलर का तर्क है कि प्रमाण-जाँचकर्ता (proof-checker) को "अनुमान" लगाने और बैकट्रैक करने की अनुमति देकर, हम "प्रूफ सर्टिफिकेट" (वह होमवर्क जो आप जमा करते हैं) को बहुत छोटा बना सकते हैं। रोबोट भारी काम करता है, इसलिए आपको हर एक कदम लिखने की ज़रूरत नहीं है। यह एक ट्रेड-ऑफ है: एक छोटा होमवर्क शीट और एक ऐसा रोबोट जिसे थोड़ा अधिक सोचने की आवश्यकता है।
5. "मूविंग बाइंडर्स" (Moving Binders) का जादू
यह इस पेपर की सबसे रोमांचक ट्रिक है। तर्क में, हम अक्सर ऐसे वेरिएबल्स (variables) के साथ काम करते हैं जो "बाउंड" (bound) होते हैं (जैसे "सभी x के लिए..." में "x")। लेगो की दुनिया में, ये वेरिएबल्स अक्सर एक जगह स्थिर होते हैं, और उन्हें संभालना तकनीकी सिरदर्द का एक दुःस्वप्न है (जैसे प्रसिद्ध POPLMark चुनौती)।
मिलर एक ऐसा दृष्टिकोण प्रस्तावित करते हैं जहाँ ये वेरिएबल्स मोबाइल (चलने वाले) हैं। वे इसे λ-ट्री सिंटैक्स (λ-tree syntax) कहते हैं।
कल्पना कीजिए कि एक वेरिएबल एक व्यक्ति पर लगा नाम का टैग है। लेगो की दुनिया में, यदि आप व्यक्ति को हिलाते हैं, तो नाम का टैग गिर सकता है या भ्रमित हो सकता है। मिलर की दुनिया में, नाम का टैग उस व्यक्ति से चिपका हुआ है। आप व्यक्ति को कमरे में कहीं भी घुमाएँ, नाम का टैग उनके साथ रहता है।
वे ∇-क्वांटिफायर (nabla) नामक एक विशेष उपकरण पेश करते हैं। इसे एक "लोकल स्कोप" बटन के रूप में सोचें। जब आप इसे दबाते हैं, तो यह कहता है, "यह वेरिएबल केवल प्रमाण के इस विशिष्ट हिस्से का है, और यह कभी बाहर नहीं निकल सकता।" यह जटिल भाषाओं, जैसे प्रोग्रामिंग भाषाओं या π-कैलकुलस (कंप्यूटर कैसे बात करते हैं इसे मॉडल करने का एक तरीका) के बारे में तर्क करना अविश्वसनीय रूप से आसान बनाता है।
6. अबेला रोबोट (Abella Robot)
मिलर केवल इसके बारे में बात नहीं करते; उन्होंने इसे काम करने के लिए सिद्ध करने हेतु एक रोबोट बनाया है। इसे अबेला (Abella) कहा जाता है।
अबेला एक थ्योरम प्रोवर है जो पूरी तरह से सीक्वेंट कैलकुलस के सिद्धांतों पर बना है। यह वेरिएबल्स और बाइंडिंग्स के बारे में जटिल तर्क को आसानी से संभालने के लिए "मूविंग बाइंडर्स" और ∇-क्वांटिफायर का उपयोग करता है। जबकि लेगो-आधारित रोबोट (जैसे Coq या Lean) बहुत लोकप्रिय हैं और उनके पास पहले से बने हुए प्रमाणों की विशाल लाइब्रेरी है, अबेला यह सुझाव देता है कि कुछ कठिन समस्याओं के लिए—विशेष रूप से उन समस्याओं के लिए जिनमें वेरिएबल्स के नामकरण और उनके घूमने का मामला शामिल है—यह नया दृष्टिकोण अधिक स्वाभाविक और सुरुचिपूर्ण है।
निचोड़
मिलर यह नहीं कह रहे हैं कि लेगो रोबोट (डिपेंडेंट टाइप थ्योरी) बुरे हैं या उन्हें फेंक देना चाहिए। वे स्वीकार करते हैं कि वे परिपक्व हैं, व्यापक रूप से उपयोग किए जाते हैं, और कई चीजों के लिए बहुत अच्छे हैं।
हालाँकि, वे सुझाव देते हैं कि इन प्रूफ असिस्टेंट्स को डिजाइन करने के आधार (foundations) के लिए, सीक्वेंट कैलकुलस एक अधिक लचीला, सरल और शक्तिशाली टूलकिट प्रदान करता है। यह तर्क को संरचना से अलग करता है, स्मार्ट अनुमान को अपनाता है, और "मूविंग वेरिएबल्स" के पेचीदा मामले को उस सुंदरता के साथ संभालता है जिसे वर्तमान मानक मुकाबला करने में संघर्ष करते हैं। यह एक आमंत्रण है कि हम तर्क के अन्य क्षेत्रों में सफल रहे एक फ्रेमवर्क का उपयोग करके, एक अलग कोण से समस्या को देखें, जिसने इंटरैक्टिव प्रूफ असिस्टेंट की दुनिया में अभी तक मुख्य ध्यान नहीं खींचा है।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।