An Undecidability Proof for the Plan Existence Problem
यह शोध पत्र सिद्ध करता है कि एपिस्टेमिक लॉजिक (epistemic logic) में प्लान अस्तित्व समस्या (plan existence problem) अनिर्णयक्षम (undecidable) है, यहाँ तक कि अत्यधिक प्रतिबंधित स्थितियों के तहत भी जैसे कि एक्शन प्रीकंडिशन्स (action preconditions) के लिए सीमित मोडल डेप्थ (modal depth) और पोस्टकंडिशन्स (postconditions) की अनुपस्थिति।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
अनंत निर्देश नियमावली का रहस्य: एक व्याख्या
कल्पना कीजिए कि आप एक वीडियो गेम खेल रहे हैं जहाँ आपको एक पात्र को खजाने तक पहुँचने के लिए कमरों की एक श्रृंखला के माध्यम से मार्गदर्शन करना है। यह एक "प्लानिंग प्रॉब्लम" (योजना बनाने की समस्या) है। अधिकांश खेलों में, नियम सरल होते हैं: "यदि आपके पास चाबी है, तो आप दरवाजा खोल सकते हैं।"
लेकिन यह शोध पत्र एपिस्टेमिक प्लानिंग (Epistemic Planning) नामक एक बहुत अधिक जटिल खेल के बारे में है। इस खेल में, पात्र केवल भौतिक कमरों में नहीं घूम रहा है; वह मन की अवस्थाओं (states of mind) के माध्यम से घूम रहा है। लक्ष्य केवल "खजाना कमरे में होना" नहीं है, बल्कि "यह जानना कि खजाना खजाने वाले कमरे में है" या "यह सुनिश्चित होना कि आपका साथी गुप्त कोड जानता है" है।
यह शोध पत्र एक चौंकाने वाली बात सिद्ध करता है: भले ही आपके कार्यों के नियम अविश्वसनीय रूप से सरल हों, फिर भी यह खेल हल करना असंभव हो सकता है।
मुख्य समस्या: "ज्ञान" की भूलभुलैया
मानक प्लानिंग में, आप तथ्यों से निपटते हैं: दरवाजा खुला है।
एपिस्टेमिक प्लानिंग में, आप विश्वासों से निपटते हैं: मुझे विश्वास है कि दरवाजा खुला है, लेकिन मैं निश्चित नहीं हूँ कि क्या आप इसे मानते हैं।
शोधकर्ता, एंटोनिस अचिलियोस (Antonis Achilleos) ने इस खेल के एक विशिष्ट संस्करण का अध्ययन किया। इस संस्करण में:
- सरल नियम: "प्रीकंडिशन्स" (कुछ करने के लिए आवश्यक शर्तें) बहुत बुनियादी हैं। आपको जटिल, नेस्टेड लॉजिक की आवश्यकता नहीं है जैसे कि "मैं जानता हूँ कि आप जानते हैं कि मैं जानता हूँ..." आपको केवल एक स्तर की गहराई की आवश्यकता है: "मैं X को जानता हूँ।"
- वास्तविकता में कोई परिवर्तन नहीं: कार्य वास्तव में भौतिक दुनिया को नहीं बदलते (जैसे कुर्सी हिलाना); वे केवल यह बदलते हैं कि पात्र क्या जानते हैं या मानते हैं (जैसे कोई रहस्य बताना)।
आप सोच सकते हैं, "यदि नियम इतने सरल हैं और भौतिक दुनिया में कुछ भी नहीं बदल रहा है, तो निश्चित रूप से एक कंप्यूटर अंततः एक योजना बना ही लेगा!"
शोध पत्र कहता है: नहीं। यह "अनडिसाइडेबल" (undecidable) है। इसका अर्थ है कि ऐसा कोई मास्टर एल्गोरिदम नहीं है जो किसी भी दिए गए सेटअप को देख सके और गारंटी के साथ कह सके कि "हाँ, एक योजना मौजूद है" या "नहीं, एक योजना मौजूद नहीं है" एक सीमित समय के भीतर।
उपमा: लेगो टावर (Lego Tower) की उपमा
यह समझने के लिए कि यह इतना कठिन क्यों है, आइए लेगो टावर उपमा का उपयोग करें।
कल्पure कीजिए कि आपको लेगो निर्देशों का एक सेट दिया गया है। प्रत्येक निर्देश एक "ब्लॉक" है जो दो अलग-अलग रंगों के टुकड़ों (मान लीजिए एक लाल टुकड़ा और एक नीला टुकड़ा) से बना है। आपका लक्ष्य दो अलग-अलग टावर बनाना है—एक केवल लाल टुकड़ों का उपयोग करके और एक केवल नीले टुकड़ों का उपयोग करके—ताकि दोनों टावर ऊंचाई और पैटर्न में बिल्कुल समान हों।
यह एक प्रसिद्ध गणितीय पहेली है जिसे पोस्ट कॉरेस्पोंडेंस प्रॉब्लम (Post Correspondence Problem - PCP) कहा जाता है। यह ज्ञात है कि कंप्यूटर के लिए ब्लॉकों के हर संभावित सेट के लिए इसे हल करना असंभव है।
शोधकर्ता की "जादुई ट्रिक":
उन्होंने सिद्ध किया कि आप इस लेगो पहेली को "नॉलेज गेम" (ज्ञान के खेल) में बदल सकते हैं।
- लाल टुकड़े पात्र का "ऊपरी अनुक्रम का ज्ञान" बन जाते हैं।
- नीले टुकड़े "निचले अनुक्रम का ज्ञान" बन जाते हैं।
- कार्य (Actions) खेल में लेगो ब्लॉक को टावर में जोड़ने की तरह काम करते हैं।
- लक्ष्य उस स्थिति तक पहुँचना है जहाँ पात्र "जानता" है कि दोनों अनुक्रम पूरी तरह से मेल खाते हैं।
चूंकि लेगो पहेली को एक सार्वभौमिक सूत्र के साथ हल करना असंभव है, और चूंकि नॉलेज गेम इस लेगो पहेली की सटीक नकल कर सकता है, इसलिए नॉलेज गेम को भी हल करना असंभव है।
यह क्यों मायने रखता है?
आप पूछ सकते हैं, "हमें इस बात से क्या फर्क पड़ता है कि एक कंप्यूटर ज्ञान के बारे में खेल को हल नहीं कर सकता?"
यह शोध आर्टिफिशियल इंटेलिजेंस (AI) की सीमाओं के बारे में है। जैसे-जैसे हम ऐसे AI एजेंट बना रहे हैं जिन्हें मनुष्यों के साथ समन्वय करने की आवश्यकता है (जैसे ट्रैफिक लाइट के साथ संवाद करने वाली सेल्फ-ड्राइविंग कारें, या गोदाम में काम करने वाले रोबोट), उन्हें यह तर्क देने की आवश्यकता है कि दूसरे क्या जानते हैं।
यह शोध पत्र कंप्यूटर विज्ञान के मानचित्र पर एक "चेतावनी संकेत" के रूप में कार्य करता है। यह इंजीनियरों को बताता है: "सावधान रहें। यदि आप अपने AI एजेंटों को ज्ञान के बारे में तर्क करने की थोड़ी सी भी क्षमता देते हैं, तो आप अनजाने में एक ऐसी समस्या बना सकते हैं जिसे उनके लिए पूरी तरह से मास्टर करना गणितीय रूप से असंभव है।"
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।