कोई भी एल्गोरिद्म कुछ चार-आयामी आकृतियों को नहीं पहचान सकता

कुछ सवालों का कोई नुस्ख़ा नहीं होता। इसलिए नहीं कि अब तक किसी को मिला नहीं, बल्कि इसलिए कि यह सिद्ध है कि कोई भी एल्गोरिद्म — कोई भी क्रमवार प्रक्रिया, चाहे कितनी भी लंबी हो, किसी भी कंप्यूटर पर चलाई जाए — हर बार उनका सही उत्तर नहीं दे सकता। यूनिवर्सिटी ऑफ़ टेक्सस एट ऑस्टिन (University of Texas at Austin) में कार्यरत कैमरन मैकए. गॉर्डन (Cameron McA. Gordon) ने चार-आयामी आकृतियों के बारे में ऐसे दो सवाल और जोड़े हैं।

क्या यह वही आकृति है?

गणितज्ञ इन आकृतियों को 4-मैनिफ़ोल्ड (4-manifolds) कहते हैं: ऐसे स्थान जो पास से देखने पर हर जगह साधारण चार-आयामी स्थान जैसे दिखते हैं। उन्हें कंप्यूटर को सौंपने के लिए, शोधपत्र मानता है कि वे आपस में जोड़े गए समतल टुकड़ों से बने हैं (“खंडशः रैखिक”, piecewise linear, या PL), ताकि हर एक का वर्णन आँकड़ों की एक सीमित सूची से किया जा सके। तब मूल सवाल यह है: ऐसी दो आकृतियाँ दी गई हों, तो क्या वे सतत विरूपण (continuous deformation) के हिसाब से एक ही हैं?

1958 में, ए. ए. मार्कोव (A. A. Markov) ने दिखाया कि इस सवाल के लिए कोई एल्गोरिद्म नहीं है। मार्कोव का प्रमाण आकृतियों की समस्या को समूहों (groups) की एक समस्या में बदल देता है: ऐसे समूह मौजूद हैं, जो सीमित संख्या के नियमों से परिभाषित होते हैं, जिनके लिए कोई भी एल्गोरिद्म यह तय नहीं कर सकता कि उनके तत्वों का कोई दिया गया संयोजन तत्समक (identity) के बराबर है या नहीं — यही “शब्द समस्या” (word problem) है। ऐसे किसी समूह से ऐसी आकृतियाँ बनाई जा सकती हैं जिन्हें कोई एल्गोरिद्म केवल उसी असंभव समस्या को हल करके ही एक-दूसरे से अलग पहचान सकता।

सात तक की उलटी गिनती

मार्कोव का तर्क कठिनाई को ख़ास आकृतियों पर भी टिका देता है। S² लीजिए, यानी एक साधारण गेंद की सतह, और गुणनफल S² × S² बनाइए, जो एक चार-आयामी आकृति है। इसकी k प्रतियों को आपस में जोड़िए (एक “संबद्ध योग”, connected sum, जिसे #k लिखा जाता है)। किसी k के लिए, कोई भी एल्गोरिद्म यह तय नहीं कर सकता कि दी गई आकृति #k(S² × S²) है या नहीं। कौन-सा k?

शोधपत्र इस उलटी गिनती का पीछा करता है। अनसुलझी शब्द समस्या वाला 12 नियमों का एक समूह, जिसे बोरिसोव (Borisov) ने 1969 में खोजा, 14 प्रतियाँ देता था। गॉर्डन ने 2022 में इसे 12 तक पहुँचाया। एम. टैंसर (M. Tancer) ने फ़्रीडमैन (Freedman) के चार-आयामी आकृतियों के वर्गीकरण से होकर एक नया रास्ता खोजा, और “टोपोलॉजिकल” संस्करण में, जहाँ आकृतियों का समतल टुकड़ों से बना होना ज़रूरी नहीं, संख्या को 9 तक पहुँचाया। इस काम के एक पहले संस्करण ने 8 तक पहुँच बनाई थी। फिर केगल (Kegel), ली (Li) और रेन (Ren) ने अनसुलझी शब्द समस्या वाला एक कहीं छोटा समूह बनाया — 3 जनक (generators) और 9 नियम — जिससे टोपोलॉजिकल संस्करण में संख्या 7 तक और समतल-टुकड़ों वाले संस्करण में 9 तक पहुँची।

गॉर्डन ने टैंसर के रास्ते को समतल टुकड़ों से बनी आकृतियों के लिए भी कारगर बनाया है, और सिद्ध किया है:

ऐसा कोई एल्गोरिद्म नहीं है जो यह तय कर सके कि दिया गया कोई 4-मैनिफ़ोल्ड, टुकड़े-दर-टुकड़े, S² × S² की 7 प्रतियों के संबद्ध योग के समान है या नहीं।

प्रमाण के मूल में एक शब्दकोश है। केगल, ली और रेन के समूह के हर शब्द w के लिए, गॉर्डन की रचना एक चार-आयामी आकृति देती है। अगर w तत्समक के बराबर है, तो नियमों पर अनुमत चालों का एक क्रम — एंड्रयूज़-कर्टिस चालें (Andrews-Curtis moves), जो आकृति को बदले बिना उसके विवरण को फिर से लिखती हैं — दिखाता है कि आकृति ठीक S² × S² की सात प्रतियाँ है। अगर नहीं, तो आकृति में ऐसे लूप (loops) होते हैं जिन्हें कसकर एक बिंदु तक नहीं सिकोड़ा जा सकता — जो S² × S² की सात प्रतियों में कभी नहीं होता — इसलिए वह वे सात प्रतियाँ नहीं हो सकती। इसलिए #7(S² × S²) को पहचानने वाला कोई एल्गोरिद्म शब्द समस्या को हल कर देता, जो असंभव है।

गाँठदार गोले

दूसरा सवाल गाँठों के बारे में है। एक साधारण गाँठ तीन-आयामी स्थान में बँधा हुआ एक वृत्त है, और यह तय करना कि कोई गाँठ खोली जा सकती है या नहीं, संभव है: इसके लिए एक एल्गोरिद्म है, जो हाकेन (Haken) की देन है। एक आयाम ऊपर, एक द्वि-आयामी गोला चार-आयामी स्थान के भीतर गाँठदार हो सकता है। उच्चतर आयामों में, यह ज्ञात है कि संगत समस्या के लिए कोई एल्गोरिद्म नहीं है। चार-आयामी गोले S⁴ में द्वि-आयामी गोलों के लिए, कोई नहीं जानता।

गॉर्डन ने सिद्ध किया है कि #7(S² × S²) के भीतर, ऐसा कोई एल्गोरिद्म नहीं है जो तय कर सके कि कोई द्वि-आयामी गोला — या कोई भी सतह, अभिविन्यसनीय (orientable) हो या नहीं — गाँठ-रहित है या नहीं। इसी क्रम में, शोधपत्र उस आकृति में एक ऐसा गोला बनाता है जिसके आसपास के स्थान का समूह अनसुलझी शब्द समस्या वाला है, और S² × S² की 12 प्रतियों में एक ऐसा गोला, जिसके समूह में हर उस समूह की एक प्रति मौजूद है जिसका वर्णन कंप्यूटर द्वारा किया जा सकता है।

इनाम: शून्य प्रतियाँ

शोधपत्र लक्ष्य को साफ़ शब्दों में रखता है: प्रतियों की संख्या घटाकर शून्य तक लाना। शून्य प्रतियों का अर्थ है ख़ुद चार-आयामी गोला S⁴। पाँच और उससे अधिक आयामों में, कोई भी एल्गोरिद्म गोले को नहीं पहचान सकता; दो और तीन आयामों में, पहचान सकता है। चार आयाम अब भी खुले हैं — और यह सवाल भी कि क्या S⁴ में गाँठदार गोलों का पता लगाया जा सकता है। हटाई गई हर प्रति दोनों सवालों को और क़रीब ले आती है।