From Dag-Like Proofs to Boolean Circuits in Lean

कल्पना कीजिए कि आप एक विशाल, जटिल पहेली को हल करने की कोशिश कर रहे हैं जहाँ हर टुकड़ा एक तार्किक तर्क (logical argument) है। कंप्यूटर विज्ञान और गणित की दुनिया में, इसे "औपचारिक सत्यापन" (formal verification) कहा जाता है। यह यह सिद्ध करने की प्रक्रिया है कि एक कंप्यूटर प्रोग्राम या गणितीय प्रमेय पूरी तरह से सही है, जिसमें कोई छिपी हुई त्रुटि या तार्किक छेद नहीं है। इसे करने के लिए, गणितज्ञ "नेचुरल डिडक्शन" (Natural Deduction) का उपयोग करते हैं, जो प्रमाण बनाने की एक चरण-दर-चरण विधि है जो कुछ हद तक एक वंशावली वृक्ष (family tree) की तरह दिखती है। प्रत्येक निष्कर्ष पिछले चरणों से शाखाओं के रूप में निकलता है, जिससे तर्क का एक विशाल, फैलता हुआ पेड़ बनता है।

हालाँकि, जैसे-जैसे ये प्रमाण बड़े होते जाते हैं, पेड़ बहुत विशाल और अव्यवस्थित हो जाते हैं। इनमें बहुत अधिक पुनरावृत्ति होती है, जैसे कि एक ही शाखा बार-बार एक ही स्थान से निकल रही हो। यह प्रमाण की जाँच करना धीमा और कठिन बना देता है। इसे ठीक करने के लिए, शोधकर्ता एक तकनीक का उपयोग करते हैं जिसे "क्षैतिज संपीड़न" (horizontal compression) कहा जाता है। कल्पना कीजिए कि आप उस विशाल पेड़ को दबाकर छोटा कर रहे हैं ताकि समान शाखाएं एक ही साझा पथ में विलीन हो जाएं। परिणाम अब एक पेड़ नहीं रह जाता; यह एक "डैग-लाइक डेरिवैबिलिटी स्ट्रक्चर" (DLDS) बन जाता है, जो मूल रूप से एक मानचित्र है जहाँ पथ एक-दूसरे को काट सकते हैं और मिल सकते हैं, जिससे बहुत स्थान बचता है। लेकिन यहाँ पेचीदा हिस्सा यह है कि केवल इसलिए कि मानचित्र छोटा है, इसका मतलब यह नहीं है कि इसे पढ़ना आसान है। एक संपीड़ित मानचित्र की वैधता की जाँच करना एक उलझे हुए मेट्रो नेटवर्क के माध्यम से एक एकल मार्ग को खोजने जैसा है।

यहीं से इस शोध पत्र की कहानी शुरू होती है। लेखक, लोरेन्ज़ो साराइवा और एडवर्ड हरमन हेउस्लर, एक साहसी प्रश्न पूछते हैं: क्या हम इस जटिल, संपीड़ित प्रमाण के मानचित्र को कुछ और भी सरल और यांत्रिक चीज़ में बदल सकते हैं? वे इस जटिल तार्किक संरचना को "बूलियन सर्किट" (Boolean circuits) में अनुवादित करने का एक तरीका प्रस्तावित करते हैं। एक बूलियन सर्किट को सिलिकॉन के टुकड़े के रूप में नहीं, बल्कि लाइट स्विच और तारों के एक विशाल, कठोर ग्रिड के रूप में सोचें। एक जटिल ग्राफ के माध्यम से पथ को ट्रेस करने के बजाय, आप बस स्विचों का एक सेट चालू करते हैं (जो प्रमाण के एक संभावित पथ का प्रतिनिधित्व करता है) और रोशनी देखते हैं। यदि अंत में लाइटें सही पैटर्न में जलती हैं, तो प्रमाण वैध है। यदि नहीं, तो यह अमान्य है।

यह शोध पत्र "शुद्ध इम्पलीकेशनल मिनिमल लॉजिक" (purely implicational minimal logic) नामक तर्क के एक विशिष्ट प्रकार में किसी भी संपीड़ित प्रमाण के लिए इस सर्किट को बनाने का तरीका प्रस्तुत करता है। वे दिखाते हैं कि स्विचों को चालू करने के किसी भी विशिष्ट तरीके (एक "पाथ असाइनमेंट") के लिए, सर्किट सही ढंग से गणना करता है कि क्या वह पथ तर्क के नियमों का पालन करता है। उन्होंने केवल अनुमान नहीं लगाया; उन्होंने "लीन" (Lean) नामक एक शक्तिशाली कंप्यूटर टूल का उपयोग करके एक औपचारिक, मशीन-चेक किया गया प्रमाण लिखा कि उनका सर्किट निर्माण पूरी तरह से काम करता है। यह एक ऐसे रोबोट को बनाने जैसा है जो अपने स्वयं के ब्लूप्रिंट की दोबारा जाँच कर सकता है। हालाँकि उन्होंने हर संभव पथ को तुरंत जाँचने की समस्या को हल नहीं किया है (वह बहुत कठिन होगा), लेकिन उन्होंने यह सिद्ध किया है कि उनका सर्किट किसी भी एकल पथ को जाँचने के लिए एक विश्वसनीय, एकसमान तरीका है। यह भविष्य में प्रमाणों को सत्यापित करने के लिए नई, सुपर-फास्ट तकनीकों, जैसे क्वांटम कंप्यूटरों, का उपयोग करने का द्वार खोलता है, जिससे प्रमाण-जाँच के कठिन कार्य को 'ऑन' और 'ऑफ' के एक स्वच्छ, विद्युत खेल में बदल दिया जाता है।

मुख्य खोज: तर्क को एक चमकते ग्रिड में बदलना

इस शोध पत्र की मुख्य उपलब्धि इन संपीड़ित प्रमाणों के लिए एक "एकीकृत बूलियन मूल्यांकन" (uniform Boolean evaluation) का निर्माण है। लेखकों ने एक DLDS (संपीदित प्रमाण मानचित्र) कैसे काम करता है, इसके जटिल नियमों को लिया और उन्हें तर्क के गेट्स (logic gates) के एक निश्चित ग्रिड में अनुवादित किया।

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

फिर सर्किट एक विशाल, स्वचालित निरीक्षक की तरह कार्य करता है। यह दो मुख्य चीजों की जाँच करता है:

1. क्या मार्ग सुव्यवस्थित है? क्या आपने तार्किक चरणों (जैसे इम्पलीकेशन इंट्रोडक्शन या एलिमिनेशन) का एक वैध क्रम चुना? यदि आपने एक ऐसा यादृच्छिक रास्ता चुना जो किसी चीज़ से जुड़ा नहीं है, तो सर्किट उसे "अमान्य" (Invalid) घोषित कर देगा।
2. क्या धारणाएँ समाप्त (discharged) हो गई हैं? तर्क में, आप अक्सर एक अस्थायी धारणा के साथ शुरुआत करते हैं (जैसे, "मान लीजिए कि X सत्य है")। एक वैध प्रमाण को अंततः यह सिद्ध करना चाहिए कि X अब मायने नहीं रखता। सर्किट एक "डिपेंडेंसी बिटस्ट्रिंग" (dependency bitstring) को ट्रैक करता है—जो सक्रिय धारणाओं का प्रतिनिधित्व करने वाली लाइटों की एक स्ट्रिंग है। यदि, मार्ग के बिल्कुल अंत में, सभी लाइटें बंद हैं (अर्थात कोई भी धारणा अधूरी नहीं बची है), तो सर्किट "स्वीकृत" (Accepted) कहता है।

शोध पत्र सिद्ध करता है कि यह सर्किट आपके द्वारा चुने गए किसी भी एकल पथ के लिए पूरी तरह से काम करता है। वे इसे "पॉइंटवाइज करेक्टनेस" (pointwise correctness) कहते हैं। इसका अर्थ है कि यदि आप सर्किट को स्विचों को चालू करने का एक विशिष्ट सेट देते हैं, तो यह उस विशिष्ट पथ के बारे में आपको सत्य बताएगा।

यह शोध पत्र क्या खारिज करता है और स्पष्ट करता है

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

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

वे यह भी स्पष्ट करते हैं कि वे शास्त्रीय, चरण-दर-चरण सत्यापन के लिए मौजूदा "फ्लो" (Flow) फंक्शन (इन प्रमाणों की जाँच करने का मानक तरीका) में सुधार का दावा नहीं कर रहे हैं। वास्तविक मूल्य वर्तमान जाँच को तेज़ बनाने में नहीं है; बल्कि जाँच के स्वरूप को बदलने में है। प्रमाण को एक बूलियन फ़ंक्शन (एक विशाल ऑन/ऑफ मशीन) में बदलकर, वे सत्यापन के विभिन्न प्रकार के तरीकों के लिए द्वार खोलते हैं, जैसे कि क्वांटम कंप्यूटिंग तकनीकें, जो पारंपरिक कंप्यूटरों की तुलना में इन विशाल "सभी पथों" की जाँच करने में सक्षम हो सकती हैं।

वे कितने आश्वस्त हैं?

लेखक बहुत आश्वस्त हैं, लेकिन एक बहुत ही विशिष्ट और कठोर तरीके से। उन्होंने केवल कंप्यूटर पर इसका सिमुलेशन नहीं किया या यह अनुमान नहीं लगाया कि यह काम करेगा। उन्होंने इसे औपचारिक रूप से सिद्ध किया है।

"लीन" (Lean) प्रूफ़ असिस्टेंट का उपयोग करके, उन्होंने अपने पूरे निर्माण का एक मशीन-चेक किया गया सत्यापन लिखा है। इसका अर्थ है कि एक कंप्यूटर ने उनके गणितीय प्रमाण को पंक्ति-दर-पंक्ति पढ़ा है और पुष्टि की है कि इसमें कोई तार्किक अंतराल नहीं है।

• सिद्ध: "पॉइंटवाइज करेक्टनेस" एक गणितीय तथ्य है। किसी भी निश्चित पथ के लिए, सर्किट ठीक उसी तरह व्यवहार करता है जैसा तर्क की आवश्यकता होती है।
• सिद्ध (सीमाओं के साथ): उन्होंने इस सर्किट को मूल प्रमाण संरचना से जोड़ने वाला एक "सेतु" (bridge) सिद्ध किया, लेकिन केवल एक विशिष्ट, सरल प्रकार के प्रमाण के लिए जिसे "अनकंप्रेस्ड सिंपल-ट्री फ्रैगमेंट" कहा जाता है।
• भविष्य का कार्य: वे स्वीकार करते हैं कि उन्होंने अभी तक "एंसेस्टर एड्ज" (ancestor edges) और रिकर्सिव फ्लो स्थितियों वाले पूर्ण रूप से संपीड़ित, जटिल मामलों के लिए सेतु सिद्ध नहीं किया है। वे इसे भविष्य के अनुसंधान के लिए एक कार्य के रूप में छोड़ देते हैं।

क्रिया में "लाइट-अप" उपमा

इसे देखने के लिए, एक विशाल, पारदर्शी बोर्ड की कल्पना करें जिसमें ग्रिड में व्यवस्थित हजारों छोटे बल्ब हैं। प्रत्येक पंक्ति एक प्रमाण के चरण का प्रतिनिधित्व करती है, और प्रत्येक कॉलम एक अलग तार्किक सूत्र का प्रतिनिधित्व करता है।

• इनपुट: आपके पास एक रिमोट कंट्रोल है जिसमें बटनों की एक लंबी सूची है। प्रत्येक बटन दबाना बोर्ड को बताता है कि अगले चरण के बीच कौन सा "तार" (wire) जलाना है। यह आपका "पाथ असाइनमेंट" है।
• सर्किट: बोर्ड के अंदर, छोटे लॉजिक गेट्स हैं। यदि आप एक तार को रोशन करते हैं जो एक "प्रिमाइज़ A" को "प्रिमाइज़ B" से जोड़कर एक "निष्कर्ष" बनाता है, तो गेट जाँचता है: "क्या यह तर्क के नियमों से मेल खाता है?" यदि आप ऐसी दो चीज़ों को जोड़ने की कोशिश करते जो फिट नहीं बैठतीं, तो गेट काला रहता है या लाल एरर लाइट चमकाता है।
• आउटपुट: बोर्ड के बिल्कुल नीचे, एक एकल "गोल" (Goal) लाइट है। यदि आपने एक ऐसे पथ का अनुसरण किया है जो सभी नियमों का पालन करता है और सफलतापूर्वक अपनी सभी अस्थायी धारणाओं को "डिस्चार्ज" करता है, तो गोल लाइट हरी हो जाती है। यदि आपने कोई कदम छोड़ दिया या कोई धारणा अधूरी छोड़ दी, तो लाइट लाल रहती है।

शोध पत्र की सफलता यह दिखाने में है कि आप किसी भी संपीड़ित प्रमाण के लिए यह बोर्ड बना सकते हैं, और लाइटों के व्यवहार के नियम हमेशा एक जैसे रहते हैं, चाहे प्रमाण कितना भी जटिल क्यों न हो। यह अमूर्त, अव्यवस्थित तार्किक कटौती की कला को स्विचों को चालू करने और लाइटों को देखने की एक ठोस, यांत्रिक प्रक्रिया में बदल देता है।

यह क्यों मायने रखता है

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

निष्कर्ष में, लेखक एक ऐसे भविष्य का संकेत देते हैं जहाँ हम सभी संभावित पथों के विशाल स्थान में से वैध पथों को खोजने के लिए "एम्प्लीट्यूड एम्प्लीफिकेशन" (एक क्वांटम तकनीक) का उपयोग कर सकते हैं, या यह सिद्ध कर सकते हैं कि कोई भी अमान्य पथ मौजूद नहीं है। वे यह भी उल्लेख करते हैं कि यह स्वचालित प्रमेय सिद्ध करने (automated theorem proving) में मदद कर सकता है, जहाँ कंप्यूटर जटिल गणितीय समस्याओं के लिए स्वयं प्रमाण खोजने का प्रयास करते हैं।

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