💻 computer science

On the Complexity of the Bi-infinite Post Correspondence Problem

यह शोध पत्र ट्यूरिंग मशीन के गैर-हल्टिंग (non-halting) से कटौती की एक श्रृंखला प्रस्तुत करके और कई संबंधित अनंत और शिफ्टेड वेरिएंट्स की $\Pi^0_1$ -पूर्णता को सिद्ध करके यह स्थापित करता है कि द्वि-अनंत पोस्ट कॉरेस्पोंडेंस प्रॉब्लम ( $\mathbb{Z}$ PCP), अरिथमेटिक पदानुक्रम के भीतर $\Sigma^0_2$ -पूर्ण है।

मूल लेखक: Olivier Finkel, Vesa Halava

प्रकाशित 2026-06-10✓ Author reviewed ⓘ

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Olivier Finkel, Vesa Halava

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने नहीं लिखा है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप दो अनंत टेप रिकॉर्डर, रिकॉर्डर G और रिकॉर्डर H के साथ एक खेल खेल रहे हैं। आपके पास ताश की एक गड्डी है, और प्रत्येक कार्ड के दो पक्ष हैं: एक "G-साइड" और एक "H-साइड।" प्रत्येक पक्ष में अक्षरों की एक स्ट्रिंग है (जैसे "apple" या "banana")।

खेल सरल है: आपको कार्डों का एक क्रम चुनना है और उन्हें एक के ऊपर एक रखना है।

यदि आप ऊपर से नीचे तक G-साइड को पढ़ते हैं, तो आपको अक्षरों की एक लंबी स्ट्रिंग प्राप्त होती है।
यदि आप ऊपर से नीचे तक H-साइड को पढ़ते हैं, तो आपको दूसरी लंबी स्ट्रिंग प्राप्त होती है।

लक्ष्य एक ऐसा कार्ड क्रम खोजना है जहाँ G-स्ट्रिंग और H-स्ट्रिंग बिल्कुल एक समान हों। यह क्लासिक पोस्ट कॉरेस्पोंडेंस प्रॉब्लम (PCP) है। यह एक प्रसिद्ध पहेली है जो कंप्यूटर विज्ञान में यह सिद्ध करती है कि यह हर संभव स्थिति के लिए हल करने योग्य नहीं है; ऐसा कोई सामान्य एल्गोरिदम नहीं है जो आपको बता सके कि "हाँ, एक समाधान मौजूद है" या "नहीं, यह असंभव है।"

नया मोड़: "बाय-इनफिनिट" (Bi-infinite) गेम

यह पेपर इस गेम का एक अधिक जटिल संस्करण पेश करता है जिसे बाय-इनफिनिट पोस्ट कॉरेस्पोंडेंस प्रॉब्लम (ZPCP) कहा जाता है।

कार्डों के एक स्टैक को ऊपर से नीचे तक पढ़ने के बजाय, कल्पना करें कि कार्डों का स्टैक दोनों दिशाओं में अनंत तक फैला हुआ है: बाईं ओर $-\infty$ से लेकर दाईं ओर $+\infty$ तक।

आप कार्डों के एक अनंत क्रम की तलाश कर रहे हैं जो $-\infty$ से $+\infty$ तक फैला हुआ है।
नियम वही है: अनंत G-स्ट्रिंग को अनंत H-स्ट्रिंग से मेल खाना चाहिए।

हालाँकि, इसमें एक पेच है। क्योंकि स्ट्रिंग दोनों दिशाओं में अनंत है, इसलिए दोनों स्ट्रिंग्स को बिल्कुल एक ही "जीरो" पॉइंट से शुरू करने की आवश्यकता नहीं है। वे शिफ्ट (खिसकी हुई) हो सकती हैं। कल्पना करें कि H-स्ट्रिंग, G-स्ट्रिंग के समान ही है, लेकिन किसी ने उसे थोड़ा बाईं या दाईं ओर खिसका दिया है। यदि आप एक को दूसरे से पूरी तरह मिलाने के लिए खिसका सकते हैं, तो आपने पहेली को हल कर लिया है।

बड़ा सवाल: यह कितना कठिन है?

कंप्यूटर वैज्ञानिक समस्याओं को वर्गीकृत करते हैं कि वे हल करने में कितनी "कठिन" हैं, जिसके लिए वे अरिथमेटिकल हाइरार्की (Arithmetical Hierarchy) नामक एक सीढ़ी का उपयोग करते हैं।

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

पेपर की खोज:
लेखकों, ओलिवर फिंकेल और वेसा हालावा ने सिद्ध किया कि बाय-इनफिनिट गेम (ZPCP) इस सीढ़ी पर सख्ती से स्तर 2 पर स्थित है।

यह मानक PCP (स्तर 1) से अधिक कठिन है।
यह समस्याओं के ब्रह्मांड के बिल्कुल शीर्ष पर नहीं है; इसकी एक विशिष्ट, प्रबंधनीय जटिलता है।
महत्वपूर्ण रूप से, उन्होंने सिद्ध किया कि यह स्तर 1 के "आसान" भागों में नहीं है। एक समाधान मौजूद है या नहीं, यह निर्धारित करने के लिए एक अधिक जटिल प्रकार के तर्क की आवश्यकता होती है।

उन्होंने इसे कैसे सिद्ध किया? (एक "टाइम मशीन" सादृश्य)

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

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

अन्य निष्कर्ष

इस प्रक्रिया के दौरान, उन्होंने कुछ उप-पहेलियों को भी हल किया:

इन्जेक्टिव मॉर्फिज्म (Injective Morphisms): उन्होंने यह भी सिद्ध किया कि भले ही आप खेल को इस तरह प्रतिबंधित करें कि प्रत्येक कार्ड अद्वितीय हो और कोई भी दो कार्ड एक ही अक्षर पैटर्न न बनाते हों (जिससे खेल "इन्जेक्टिव" हो जाए), तो भी समस्या अनसुलझी रहती है और उतनी ही कठिन बनी रहती है।
फिक्स्ड शिफ्ट्स (Fixed Shifts): उन्होंने उन संस्करणों को देखा जहाँ दोनों स्ट्रिंग्स के बीच का शिफ्ट एक विशिष्ट संख्या के लिए निश्चित है (उदाहरण के लिए, "H-स्ट्रिंग हमेशा G-स्ट्रिंग से ठीक 5 अक्षर दाईं ओर है")। उन्होंने सिद्ध किया कि ये भी अविश्वसनीय रूप से कठिन (स्तर 1 पूर्ण) हैं।

मुख्य निष्कर्ष

यह पेपर अनंत शब्द पहेलियों के "कठिनाई परिदृश्य" का एक मानचित्र है।

मानक PCP एक "स्तर 1" का राक्षस है।
बाय-इनफिनिट PCP (ZPCP) एक "स्तर 2" का राक्षस है। यह मूल संस्करण से सख्त रूप से कठिन है, लेकिन अनंत रूप से कठिन नहीं है।
लेखकों ने एक चतुर "रिवाइंड" तंत्र (रिवर्सिबिलिटी) का उपयोग करके यह दिखाया कि यह नया पजल वास्तव में कहाँ स्थित है।

संक्षेप में: दो-तरफा अनंत संस्करण वाले इस कार्ड गेम को हल करना कठिनाई का एक विशिष्ट प्रकार है, जो मूल, अनसुलझे संस्करण से एक स्तर ऊपर है, और लेखकों ने सटीक रूप से निर्धारित किया है कि यह गणितीय ब्रह्मांड में कहाँ स्थित है।

तकनीकी सारांश: द्वि-अनंत पोस्ट कोरेस्पोंडेंस प्रॉब्लम (Bi-infinite Post Correspondence Problem) की जटिलता पर

समस्या की परिभाषा
यह शोध पत्र द्वि-अनंत पोस्ट कोरेस्पोंडेंस प्रॉब्लम (ZPCP) की कम्प्यूटेशनल जटिलता की जांच करता है। जबकि शास्त्रीय पोस्ट कोरेस्पोंडेंस प्रॉब्लम (PCP) दो दिए गए मॉर्फिज्म के लिए एक गैर-रिक्त परिमित शब्द $w$ की खोज करता है ताकि $g(w) = h(w)$ हो, और इनफिनिट PCP ( $\omega$ PCP) एक अनंत शब्द की खोज करता है, ZPCP यह पूछता है कि क्या एक द्वि-अनंत शब्द $\alpha = \dots a_{-1}a_0a_1 \dots$ अस्तित्व में है जिससे $g(\alpha) = h(\alpha)$ हो। महत्वपूर्ण रूप से, द्वि-अनंत शब्दों के लिए समानता को एक शिफ्ट (shift) तक परिभाषित किया गया है: $g(\alpha) = h(\alpha)$ तब होता है जब एक पूर्णांक शिफ्ट $\tau$ मौजूद हो जिससे $g(\alpha)$ में स्थिति $i$ पर स्थित अक्षर $h(\alpha)$ में स्थिति $i+\tau$ पर स्थित अक्षर के बराबर हो।

पिछले कार्यों ने स्थापित किया कि ZPCP अनिर्णायक (undecidable) है और अरिथमेटिक पदानुक्रम (arithmetical hierarchy) के $\Sigma^0_2$ वर्ग में स्थित है, लेकिन इसे सख्ती से पदानुक्रम में स्थित नहीं किया गया था (अर्थात, यह ज्ञात नहीं था कि यह $\Pi^0_1$ -पूर्ण है या स्तर 2 पर है)। इस कार्य का प्राथमिक लक्ष्य ZPCP की अरिथमेटिक पदानुक्रम में सटीक स्थिति निर्धारित करना है।

कार्यप्रणाली (Methodology)
लेखक खाली इनपुट पर नियतात्मक ट्यूरिंग मशीनों (TMs) की नॉन-हाल्टिंग समस्या से शुरू होकर, सेमी-थ्यू सिस्टम (semi-Thue systems) के माध्यम से होते हुए, अंततः PCP के वेरिएंट्स तक पहुँचने वाली रेडक्शन (reduction) की एक श्रृंखला स्थापित करते हैं। कार्यप्रणाली कई प्रमुख तकनीकी निर्माणों पर निर्भर करती है:

प्रतिवर्ती सेमी-थ्यू सिस्टम (Reversible Semi-Thue Systems): लेखक एक दिए गए ट्यूरिंग मशीन $M$ से एक विशिष्ट सेमी-थ्यू सिस्टम $S_M$ का निर्माण करते हैं। यह सिस्टम इस तरह बनाया गया है कि यह $\Theta$ -नियतात्मक (deterministic) और $\Theta$ -प्रतिवर्ती (reversible) हो। प्रतिवर्तीता का गुण ZPCP के लिए अंतिम रेडक्शन हेतु महत्वपूर्ण है, क्योंकि यह फॉरवर्ड और बैकवर्ड दोनों दिशाओं में गणना के चरणों के अनुकरण (simulation) की अनुमति देता है।
इन्जेक्टिव मॉर्फिज्म और बाउंडेड डिले (Injective Morphisms and Bounded Delay): शोध पत्र ऐसे मॉर्फिज्म $g$ और $h$ का निर्माण करते हैं जो सेमी-थ्यू सिस्टम का अनुकरण करते हैं। एक महत्वपूर्ण तकनीकी योगदान यह सिद्ध करना है कि ये मॉर्फिज्म "बाउंडेड डिले 2" के हैं, जिसका अर्थ है कि वे 'इन्जेक्टिव' हैं। यह लेखकों को अनडिसाइडेबिलिटी के परिणामों को 'इन्जेक्टिव मॉर्फिज्म' के वर्ग तक विस्तारित करने की अनुमति देता है।
शिफ्टेड वेरिएंट्स (Shifted Variants): लेखक "s-शिफ्ट" वेरिएंट्स ( $\omega$ PCP $_s$ और ZPCP $_s$ ) को परिभाषित और विश्लेषित करते हैं, जहाँ समानता की स्थिति एक विशिष्ट शिफ्ट $s$ पर स्थिर होती है। वे सिद्ध करते हैं कि ये वेरिएंट $\Pi^0_1$ -पूर्ण हैं।
डीसिंक्रोनाइजेशन और ओवरलाइनिंग (Desynchronization and Overlining): ZPCP की द्वि-अनंत प्रकृति को संभालने और ट्रिवियल समाधानों को समाप्त करने के लिए, लेखक प्रतीकों के ओवरलाइन वाले और बिना ओवरलाइन वाले कॉपियों के साथ एक जटिल वर्णमाला (alphabet) निर्माण का उपयोग करते हैं, जिसमें विशिष्ट "डीसिंक्रोनाइजेशन" मार्कर ( $d^4$ और $f^4$ ) शामिल हैं। यह किसी भी समाधान को फॉरवर्ड और बैकवर्ड कॉन्फ़िगरेशन के बीच बारी-बारी से चलने के लिए मजबूर करता है, जिससे प्रभावी रूप से दोनों दिशाओं में सेमी-थ्यू सिस्टम के व्युत्पत्ति (derivation) का अनुकरण होता है।

प्रमुख योगदान और परिणाम

$\omega$ PCP की जटिलता: लेखक सिद्ध करते हैं कि इनफिनिट PCP ( $\omega$ PCP) इन्जेक्टिव मॉर्फिज्म (विशेष रूप से, बाउंडेड डिले 2 के मॉर्फिज्म) तक सीमित होने पर भी अनिर्णायक है। इसके अलावा, वे स्थापित करते हैं कि यह प्रतिबंधित संस्करण $\Pi^0_1$ -पूर्ण है।
शिफ्टेड समस्याओं की जटिलता: शोध पत्र सिद्ध करता है कि किसी भी प्राकृतिक संख्या $s$ के लिए, $s$ -शिफ्ट इनफिनिट PCP ( $\omega$ PCP $_s$ ) और $s$ -शिफ्ट द्वि-अनंत PCP (ZPCP $_s$ ) $\Pi^0_1$ -पूर्ण हैं।
ZPCP की जटिलता: मुख्य परिणाम मानक ZPCP से संबंधित है। लेखक सिद्ध करते हैं कि ZPCP $\Pi^0_1$ -हार्ड है। यह ज्ञात परिणाम कि ZPCP $\Sigma^0_2$ में है और $\Pi^0_1$ में नहीं है, तथा $\Sigma^0_1$ में न होने के नए प्रमाण के साथ मिलकर, वे निष्कर्ष निकालते हैं कि:
$\text{ZPCP} \in \Sigma^0_2 \setminus (\Pi^0_1 \cup \Sigma^0_1)$
यह समस्या को अरिथमेटिक पदानुक्रम के दूसरे स्तर पर सख्ती से स्थापित करता है।
सेमी-थ्यू सिस्टम: $\Theta$ -नियतात्मक और $\Theta$ -प्रतिवर्ती सेमी-थ्यू सिस्टम के लिए नॉन-टर्मिनेशन समस्या को $\Pi^0_1$ -पूर्ण दिखाया गया है।

महत्व और दावे
यह शोध पत्र दावा करता है कि इसने पोस्ट कोरेस्पोंडेंस प्रॉब्लम के वेरिएंट्स के जटिलता परिदृश्य (complexity landscape) की समझ को स्पष्ट किया है। विशेष रूप से:

इसने ZPCP के अरिथमेटिक पदानक्रम में स्थान के संबंध में अस्पष्टता को सुलझा दिया है, यह पुष्टि करते हुए कि यह $\Pi^0_1$ -पूर्ण नहीं है बल्कि स्तर 2 पर स्थित है।
यह प्रदर्शित करता है कि अनिर्णायकता और $\Pi^0_1$ -पूर्णता, इन्फिनिटी वेरिएंट्स में भी बनी रहती है, भले ही उन्हें 'इन्जेक्टिविटी' और 'बाउंडेड डिले' जैसे कड़े प्रतिबंधों के तहत रखा गया हो, जिनका उपयोग अक्सर निर्णय समस्याओं को सरल बनाने के लिए किया जाता है।
लेखक नोट करते हैं कि हालांकि उन्होंने ZPCP को स्तर 2 पर स्थित कर दिया है, लेकिन यह प्रश्न कि क्या यह $\Sigma^0_2$ -पूर्ण है, अभी भी खुला है।

यह कार्य ट्यूरिंग मशीन नॉन-हाल्टिंग से सेमी-थ्यू नॉन-टर्मिनेशन और फिर विभिन्न PCP वेरिएंट्स तक रेडक्शन की एक कठोर श्रृंखला पर निर्भर करता है, जिसमें द्वि-अनंत बाधाओं को संभालने के लिए निर्मित सिस्टम की प्रतिवर्तीता (reversibility) का उपयोग किया गया है।

नया मोड़: "बाय-इनफिनिट" (Bi-infinite) गेम

बड़ा सवाल: यह कितना कठिन है?

उन्होंने इसे कैसे सिद्ध किया? (एक "टाइम मशीन" सादृश्य)

अन्य निष्कर्ष

मुख्य निष्कर्ष

इसी तरह के और पेपर