सेमी-थू प्रणाली: Difference between revisions

Latest revision as of 09:49, 2 August 2023

सैद्धांतिक कंप्यूटर विज्ञान और गणितीय तर्क में स्ट्रिंग पुनर्लेखन प्रणाली (एसआरएस), जिसे ऐतिहासिक रूप से सेमी-एक्सल थ्यू प्रणाली कहा जाता है, सामान्यतः इसे परिमित समुच्चय में वर्णमाला (कंप्यूटर विज्ञान) से स्ट्रिंग (कंप्यूटर विज्ञान) पर पुनर्लेखन प्रणाली के लिए भी जाना जाता है। इस प्रकार इसमें बाइनरी संबंध भी उपयोग किया जाता है, जो $R$ वर्णमाला पर निश्चित स्ट्रिंग के बीच, जिसे पुनर्लेखन नियम कहा जाता है, इसे $s\rightarrow t$ के द्वारा दर्शाया जाता है, इसके आधार पर एसआरएस सभी स्ट्रिंग्स के लिए पुनर्लेखन संबंध का विस्तार करता है जिसमें नियमों के बाएँ और दाएँ ओर सबस्ट्रिंग भी दिखाई देती हैं, अर्थात $usv\rightarrow utv$ , जहाँ $s$ , $t$ , $u$ , और $v$ स्ट्रिंग के रूप में हैं।

यहाँ पर सेमी-थ्यू प्रणाली की मुख्य धारणा अनिवार्यतः मोनॉइड की प्रस्तुति से मेल खाती है। इस प्रकार ऐसे मोनोइड्स और समुच्चयों के लिए शब्द समस्या (गणित) को हल करने के लिए प्राकृतिक रूपरेखा बनायी जाती हैं।

इसके आधार पर किसी एसआरएस को सीधे स्यूडो पुनर्लेखन प्रणाली के रूप में परिभाषित किया जा सकता है। इसे प्रतिबंधित प्रकार की शब्द पुनर्लेखन प्रणाली के रूप में भी देखा जा सकता है। इसके आधार पर औपचारिकता रूप से किसी स्ट्रिंग की पुनर्लेखन प्रणालियाँ ट्यूरिंग पूर्ण पर आधारित होती हैं।^[1] इस प्रकार सेमी-थ्यू नाम नॉर्वेजियन गणितज्ञ एक्सल थ्यू से आया है, जिन्होंने 1914 के पेपर में स्ट्रिंग रीराइटिंग प्रणाली का व्यवस्थित उपचार प्रस्तुत किया था।^[2] इस प्रकार थ्यू ने इस धारणा को इस उम्मीद से प्रस्तुत किया कि वह सीमित रूप से प्रस्तुत होने वाले सेमीसमुच्चयों के लिए शाब्दिक रूप से उत्पन्न होने वाली विभिन्न गणितीय समस्याओं को हल करने में सफल हो सके। इस प्रकार यह केवल 1947 में ही किसी समस्या को अनिर्णीत समस्या के रूप में दिखाया गया था - यह परिणाम एमिल पोस्ट और एंड्री मार्कोव के सोवियत गणितज्ञ या ए. मार्कोव जूनियर द्वारा स्वतंत्र रूप से प्राप्त किया गया था।^[3]^[4]

परिभाषा

किसी स्ट्रिंग के पुनर्लेखन प्रणाली या सेमी-थ्यू प्रणाली को टपल $(\Sigma ,R)$ कहा जाता है, जहाँ पर इन मुख्य बिंदुओं पर ध्यान दिया जाता हैं जो इस प्रकार हैं-

$Σ$ वर्णमाला है, जिसे सामान्यतः सीमित वर्णमाला माना जाता है।^[5] इस प्रकार के समुच्चयओं के लिए तत्व $\Sigma ^{*}$ का उपयोग किया जाता हैं, यहां पर क्लेन स्टार * का उपयोग किया जाता है, इस प्रकार परिमित संभवतः रिक्त स्ट्रिंग $Σ$ का उदाहरण हैं, जिसे कभी-कभी औपचारिक भाषाओं में शब्द भी कहा जाता है, हम यहाँ पर इन्हें बस स्ट्रिंग्स कहते हैं।
$R$ स्ट्रिंग्स पर बाइनरी संबंध $Σ$ द्वारा प्रदर्शित होता है, अर्थात $R\subseteq \Sigma ^{*}\times \Sigma ^{*}.$ इसमें पाये जाने वाले प्रत्येक तत्व $(u,v)\in R$ के लिए इसे उचित पुनर्लेखन नियम के रूप से जाना जाता है, और इसे सामान्यतः $u\rightarrow v$ इस प्रकार लिखा जाता है।

यदि संबंध $R$ सममित संबंध को प्रदर्शित करता है, तो इस प्रणाली को थ्यू प्रणाली कहा जाता है।

इसमें पुनर्लेखन नियम $R$ को स्वाभाविक रूप से अन्य स्ट्रिंग्स $\Sigma ^{*}$ तक बढ़ाया जा सकता है, जिसके अनुसार सबस्ट्रिंग को पुनः $R$ द्वारा लिखने की अनुमति देकर इसे अधिकांशतः औपचारिक रूप से वन फेस पुनर्लेखन संबंध ${\xrightarrow[{R}]{}}$ प्रेरक $R$ पर $\Sigma ^{*}$ किसी भी स्ट्रिंग $s,t\in \Sigma ^{*}$ के लिए इस प्रकार प्रदर्शित होता हैं :

इस प्रकार

s{\xrightarrow[{R}]{}}t

होने पर यदि

x,y,u,v\in \Sigma ^{*}

मान प्राप्त होता हैं जो इस प्रकार है कि-

s=xuy

,

t=xvy

, और

u\rightarrow v

के समान होता हैं।

इस स्थिति में ${\xrightarrow[{R}]{}}$ पर रिलेशन $x,y,u,v\in \Sigma ^{*}$ प्राप्त होता हैं, यहाँ पर संयुग्म $(\Sigma ^{*},{\xrightarrow[{R}]{}})$ स्यूडो पुनर्लेखन प्रणाली की परिभाषा में फिट बैठता है। सामान्यतः $R$ का उपसमुच्चय ${\xrightarrow[{R}]{}}$ है, इसके आधार पर यहाँ पर कुछ लेखक इन एरों के लिए ${\xrightarrow[{R}]{}}$ (उदा ${\xrightarrow[{R}]{}}$ ) संकेतन का उपयोग करते हैं, इसे अलग करने के लिए $R$ स्वयं अपने आप ( $\rightarrow$ ) द्वारा प्रदर्शित होता हैं। क्योंकि वे इसके पश्चात सबस्क्रिप्ट को छोड़ने में सक्षम होना चाहते हैं और फिर भी बीच में $R$ से उत्पन्न होने वाले भ्रम से बचना चाहते हैं, और वन-फेस $R$ वाले पुनर्लेखन से प्रेरित होते हैं।

स्पष्ट रूप से सेमी-थ्यू प्रणाली में हम प्रारंभिक स्ट्रिंग से प्रारंभ करके उत्पादित स्ट्रिंग्स का परिमित या अनंत अनुक्रम $s_{0}\in \Sigma ^{*}$ बना सकते हैं, और इस समय सबस्ट्रिंग-प्रतिस्थापन करके इसे बार-बार दोबारा लिखा जाता हैं:

s_{0}\ {\xrightarrow[{R}]{}}\ s_{1}\ {\xrightarrow[{R}]{}}\ s_{2}\ {\xrightarrow[{R}]{}}\ \ldots

इस प्रकार के शून्य-या-अधिक-चरणों वाले पुनर्लेखन को प्रतिवर्ती सकर्मक समापन ${\xrightarrow[{R}]{}}$ द्वारा कैप्चर किया जाता है, ${\xrightarrow[{R}]{*}}$ द्वारा चिह्नित इस अर्थ को पुनर्लेखन प्रणाली में मौलिक धारणाओं पर देखा जा सकता हैं। इसे पुनर्लेखन संबंध या न्यूनीकरण संबंध $\Sigma ^{*}$ प्रेरक $R$ कहा जाता है।

थ्यू सर्वांगसमता

सामान्यतः समुच्चय $\Sigma ^{*}$ वर्णमाला पर स्ट्रिंग्स की संख्या में उपस्थित होने वाले स्ट्रिंग संयोजन के लिए उपयुक्त बाइनरी ऑपरेशन के साथ मिलकर मुक्त मोनॉइड बनाते है, जिसे इस रूप में दर्शाया गया है। यहाँ पर प्रतीक को हटाकर गुणनात्मक रूप से लिखा जाता है। इस प्रकार एसआरएस में होने वाली कमी ${\xrightarrow[{R}]{*}}$ के संबंध को मोनॉइड ऑपरेशन के साथ संगत किया जाता है, जिसका अर्थ $x{\xrightarrow[{R}]{*}}y$ है, जिसका तात्पर्य $uxv{\xrightarrow[{R}]{*}}uyv$ के लिए इसमें पाये जाने वाले सभी स्ट्रिंग के लिए $x,y,u,v\in \Sigma ^{*}$ हैं। जहाँ पर ${\xrightarrow[{R}]{*}}$ की परिभाषा के अनुसार पूर्व आदेश प्राप्त होते है, इस प्रकार $\left(\Sigma ^{*},\cdot ,{\xrightarrow[{R}]{*}}\right)$ के लिए मोनोइडल श्रेणी या मोनोइडल प्रीऑर्डर बनाया जाता है।

यहाँ पर प्रतिवर्ती सकर्मक सममित समापन ${\xrightarrow[{R}]{}}$ , को ${\overset {*}{\underset {R}{\leftrightarrow }}}$ द्वारा निरूपित करते हैं।

इस प्रकार पुनर्लेखन प्रणाली की मौलिक धारणाएँ इस प्रकार देखी जा सकती हैं, इसके आधार पर सर्वांगसमताओं का आपस में संबंध रहता है, जिसका अर्थ है कि यह तुल्यता से संबंधित है, इस प्रकार परिभाषा के अनुसार और यह स्ट्रिंग संयोजन के साथ भी संगत रहता है। यहाँ पर रिलेशन ${\overset {*}{\underset {R}{\leftrightarrow }}}$ के द्वारा उत्पन्न होने वाले थ्यू सर्वांगसमता $R$ कहलाती है, इस थ्यू प्रणाली में, अर्ताथ यदि $R$ सममित है तो पुनर्लेखन संबंध ${\xrightarrow[{R}]{*}}$ थ्यू सर्वांगसमता ${\overset {*}{\underset {R}{\leftrightarrow }}}$ से मेल खाता है।

फ़ैक्टर मोनॉइड और मोनॉइड प्रस्तुतियाँ

इस प्रकार ${\overset {*}{\underset {R}{\leftrightarrow }}}$ रिलेशन के आधार पर यह सर्वांगसमता को प्रदर्शित करता है, यहाँ पर हम इस कारक के आधार पर मोनॉयड ${\mathcal {M}}_{R}=\Sigma ^{*}/{\overset {*}{\underset {R}{\leftrightarrow }}}$ को परिभाषित कर सकते हैं, जिसमें मुक्त मोनॉइड का $\Sigma ^{*}$ कारक मोनॉयड में थ्यू सर्वांगसमता द्वारा प्रदर्शित होता हैं। इसके आधार पर यदि मोनोइड ${\mathcal {M}}$ के साथ समरूपी अर्ताथ ${\mathcal {M}}_{R}$ है, इसके पश्चात पुनः यह सेमी-थ्यू प्रणाली $(\Sigma ,R)$ की मोनोइड प्रस्तुति ${\mathcal {M}}$ कहलाती है।

इसके आधार पर हम इसे पुनः बीजगणित के अन्य क्षेत्रों के साथ कुछ बहुत उपयोगी संबंध मिलते हैं। उदाहरण के लिए, वर्णमाला {a, b} नियमों के साथ {ab → ε, ba → ε } इसका उपयोग किया जाता हैं, जहाँ पर ε रिक्त स्ट्रिंग को प्रदर्शित करता है, इस प्रकार से जनरेटर पर मुक्त समूह को प्रस्तुत किया जाता है। यदि इसके अतिरिक्त इस नियम को केवल { ab → ε } पर स्थापित करते हैं, तो हमें बाइसिकल मोनोइड की प्राप्ति होती है।

मोनोइड्स की प्रस्तुति के रूप में सेमी-थ्यू प्रणाली का महत्व निम्नलिखित द्वारा मजबूत किया गया है:

'प्रमेय': प्रत्येक मोनॉइड में $(\Sigma ,R)$ रूप की प्रस्तुति होती है, इस प्रकार इसे हमेशा सेमी-थ्यू प्रणाली द्वारा प्रस्तुत किया जा सकता है, संभवतः अनंत वर्णमाला पर इसको प्रस्तुत किया जाता हैं।^[6] इस संदर्भ में, समुच्चय $\Sigma$ के जनरेटरों का समुच्चय ${\mathcal {M}}$ कहलाता है, और $R$ संबंधों को परिभाषित करने वाले समुच्चय ${\mathcal {M}}$ को कहा जाता है, हम मोनोइड्स को उनकी प्रस्तुति के आधार पर तुरंत वर्गीकृत कर सकते हैं। जिसे ${\mathcal {M}}$ कहा जाता है

अंतिम रूप से उत्पन्न यदि $\Sigma$ परिमित है।
दोनों को अंतिम रूप से प्रस्तुत किया गया है, इस प्रकार $\Sigma$ और $R$ परिमित हैं।

समस्या शब्द की अनिश्चयता

पोस्ट ने शब्द समस्या सेमीसमुच्चयों के लिए सामान्य रूप से अनिर्णीत प्रमाणित कर दिया गया हैं, इस प्रकार अनिवार्य रूप से रुकने की समस्या को कम करके^[7] ट्यूरिंग मशीनें के लिए शब्द समस्या का उदाहरण प्रकट किया गया हैं।

सीधे तौर पर पोस्ट ने ट्यूरिंग मशीन प्लस टेप की स्थिति की सीमित स्ट्रिंग के रूप में एन्कोडिंग तैयार की हैं, जैसे कि इस मशीन की गतिविधियों को इस स्ट्रिंग एन्कोडिंग पर अभिनय करने वाले स्ट्रिंग रीराइट प्रणाली द्वारा किया जा सकता है। इसके आधार पर एन्कोडिंग की वर्णमाला में अक्षरों का समुच्चय होता है, जहाँ पर $S_{0},S_{1},\dotsc ,S_{m}$ टेप पर प्रतीकों के लिए जहाँ $S_{0}$ का अर्थ रिक्त, अक्षरों का और समुच्चय $q_{1},\dotsc ,q_{r}$ ट्यूरिंग मशीन की अवस्थाओं के लिए, और अंत में तीन अक्षर $q_{r+1},q_{r+2},h$ जिनकी एन्कोडिंग में विशेष भूमिका होती है। इस प्रकार $q_{r+1}$ और $q_{r+2}$ ट्यूरिंग मशीन की सहज रूप से अतिरिक्त आंतरिक अवस्थाएँ हैं, जिनमें यह रुकते समय परिवर्तित हो जाती है, जबकि $h$ टेप के गैर-रिक्त भाग के अंत को चिह्नित करता है, मशीन $h$ पर पहुंच रही है, इसी प्रकार मशीन से उचित व्यवहार करना चाहिए, जैसे कि वहां कोई रिक्त स्थान था, और $h$ अगले बाॅक्स में था, जिसमें वे स्ट्रिंग जो ट्यूरिंग मशीन स्थिति की वैध एन्कोडिंग हैं, वे $h$ से प्रारंभ होती हैं , इसके बाद शून्य या अधिक प्रतीक अक्षर, उसके बाद ठीक आंतरिक स्थिति अक्षर $q_{i}$ जो मशीन की स्थिति को एन्कोड करता है, उसके बाद या अधिक प्रतीक अक्षर, उसके बाद $h$ का अंत होता है, इस प्रकार इस प्रतीक को उचित अक्षर द्वारा टेप करके इसकी सामग्री से सीधे संयोजित करते हैं, और आंतरिक स्थिति पत्र के ऊपर की स्थिति को चिह्नित किया जाता है, इस प्रकार आंतरिक स्थिति पत्र के बाद का प्रतीक वह सेल है, जो वर्तमान में ट्यूरिंग मशीन के प्रमुख के अंतर्गत है।

एक संक्रमण जहां मशीन इस स्थिति में होने वाले $q_{i}$ के मान और प्रतीक $S_{k}$ को देख रहे हैं, जहाँ $S_{l}$ को वापस से इसके प्रतीक के रूप में लिखा जाता है, यह इससे दाईं ओर चलता है, और स्थिति में परिवर्तित हो जाता है, इस प्रकार $q_{j}$ की पुनर्लेखन द्वारा कार्यान्वित किया जाता है, जो इस प्रकार हैं-

q_{i}S_{k}\to S_{l}q_{j}

जबकि वह संक्रमण बाईं ओर जाने के अतिरिक्त पुनर्लेखन द्वारा कार्यान्वित होता है।

S_{p}q_{i}S_{k}\to q_{j}S_{p}S_{l}

प्रत्येक प्रतीक के लिए उदाहरण के साथ $S_{p}$ बायीं ओर उस कक्ष में यदि हम टेप के विज़िट किए गए भाग के अंत तक पहुँचते हैं, तो हम इसके अतिरिक्त उपयोग करते हैं।

hq_{i}S_{k}\to hq_{j}S_{0}S_{l}

,

इस प्रकार किसी स्ट्रिंग को अक्षर से लंबा किया जाता हैं। क्योंकि सभी पुनर्लेखन में आंतरिक स्थिति पत्र $q_{i}$ पर उपस्थित होता है, इस प्रकार किसी वैध एन्कोडिंग में केवल ऐसा अक्षर होता है, और प्रत्येक पुनर्लेखन बिल्कुल ऐसा अक्षर उत्पन्न करता है, जो पुनर्लेखन प्रक्रिया बिल्कुल एन्कोडेड ट्यूरिंग मशीन के चलने का अनुसरण करती है। इससे यह प्रमाणित होता है कि स्ट्रिंग रीराइट प्रणाली ट्यूरिंग पूर्ण हैं।

इस कारण दो रुके हुए चिन्ह $q_{r+1}$ और $q_{r+2}$ होने का कारण यह हो सकता हैं, कि क्या हम चाहते हैं कि सभी रुकने वाली ट्यूरिंग मशीनें ही कुल स्थिति में समाप्त हों, न कि केवल विशेष आंतरिक स्थिति में रहें। इसके लिए रुकने के बाद टेप को साफ़ करने की आवश्यकता होती है, इसलिए $q_{r+1}$ तक पहुंचने तक उस पर बाईं ओर दिए गए चिह्न $h$ को खत्म कर देता है, जहां यह संक्रमण $q_{r+2}$ पर प्रभावित होता है, जो इसके अतिरिक्त अपने दाहिनी ओर के प्रतीक को खत्म करता है। इस प्रकार इस चरण में स्ट्रिंग रीराइट प्रणाली अब ट्यूरिंग मशीन का अनुकरण नहीं करता है, क्योंकि वह टेप से कोशिकाओं को नहीं हटा सकता है। इस प्रकार सभी प्रतीकों के चले जाने के बाद, हम टर्मिनल स्ट्रिंग $hq_{r+2}h$ पर पहुंच गए हैं।

शब्द समस्या के लिए निर्णय प्रक्रिया से यह निर्णय लेने की प्रक्रिया भी प्राप्त होगी कि दी गई ट्यूरिंग मशीन किसी विशेष कुल स्थिति में प्रारंभ होने पर समाप्त हो जाती है या $t$ पर नहीं होती हैं, इसका परीक्षण करके कि क्या $t$ और $hq_{r+2}h$ इस स्ट्रिंग पुनर्लेखन प्रणाली के संबंध में समान सर्वांगसमता वर्ग से संबंधित हैं। इस तकनीकी के आधार पर हमारे पास निम्नलिखित बिंदु प्राप्त होते हैं:

लेम्मा के आधार पर $M$ नियतात्मक ट्यूरिंग मशीन बनें और $R$ स्ट्रिंग रीराइट प्रणाली $M$ को कार्यान्वित करते हैं, जैसा ऊपर वर्णित है। इसके पश्चात $M$ के रूप में एन्कोड की गई कुल स्थिति से प्रारंभ होने पर रुक जाएगा, इस कारण $t$ यदि $t\mathrel {\overset {*}{\underset {R}{\leftrightarrow }}} hq_{r+2}h$ के लिए अर्थात, यदि $t$ और $hq_{r+2}h$ थ्यू के लिए सर्वांगसम मान $R$ के समान हैं।

इस प्रकार $t\mathrel {\overset {*}{\underset {R}{\rightarrow }}} hq_{r+2}h$ पर यदि $M$ से प्रारंभ करने पर रुक जाता है, तो $t$ के निर्माण से तत्काल $R$ का मान प्राप्त होता है, जहाँ पर $M$ को जब तक यह रुकता नहीं जाता तब तक इसका प्रमाण उत्पन्न करता है, इस प्रकार $t\mathrel {\overset {*}{\underset {R}{\rightarrow }}} hq_{r+2}h$ ) मान प्राप्त होता हैं, अपितु ${\overset {*}{\underset {R}{\leftrightarrow }}}$ ट्यूरिंग मशीन को भी अनुमति देता है, जिसके लिए $M$ के पीछे की ओर इस स्टेप को बढ़ाते हैं, इस प्रकार यहाँ यह प्रासंगिक हो जाता है कि $M$ नियतिवादी है, क्योंकि तब आगे के सभी चरण अद्वितीय होते हैं, जिसमें ${\overset {*}{\underset {R}{\leftrightarrow }}}$ से चलना प्रारंभ करके $t$ को $hq_{r+2}h$ के अंतिम पिछड़े कदम को उसके समकक्ष द्वारा आगे के कदम के रूप में पालन किया जाना आवश्यक होता हैं, इसलिए ये दोनों निरस्त हो जाते हैं, और प्रेरण द्वारा सभी पिछड़े कदमों को इस तरह की चाल से हटाया जा सकता है। इसलिए यदि $M$ से प्रारंभ होने पर $t$ पर रुकता नहीं है, अर्ताथ यदि हमारे पास $t\mathrel {\overset {*}{\underset {R}{\rightarrow }}} hq_{r+2}h$ नहीं है, तो हमारे पास $t\mathrel {\overset {*}{\underset {R}{\leftrightarrow }}} hq_{r+2}h$ भी नहीं है, इसलिए ${\overset {*}{\underset {R}{\leftrightarrow }}}$ के द्वारा निर्णय लेकर हमें रुकने की समस्या का उत्तर $M$ बताता है।

इस तर्क की स्पष्ट सीमा यह है कि सेमीसमूह तैयार करना होता हैं, जिसके लिए $\Sigma ^{*}{\big /}{\overset {*}{\underset {R}{\leftrightarrow }}}$ के द्वारा अनिर्णीत शब्द समस्या के साथ, सबसे पहले किसी के पास ट्यूरिंग मशीन $M$ का ठोस उदाहरण होना चाहिए, जिसके लिए रुकने की समस्या अनिर्णीत है, अपितु सामान्य रुकने की समस्या की अनिर्णयता के प्रमाण में सम्मिलित होने वाले विभिन्न ट्यूरिंग मशीनों में घटक के रूप में रुकने की समस्या को हल करने वाली काल्पनिक ट्यूरिंग मशीन होती है, इसलिए उनमें से कोई भी मशीन वास्तव में सम्मिलित नहीं हो सकती है, यह सब प्रमाणित करता है कि कुछ ट्यूरिंग मशीन है जिसके लिए निर्णय समस्या अनिर्णीत है। चूंकि, कुछ ट्यूरिंग मशीनों में अनिर्णीत रुकने की समस्या है, इसका अर्थ है कि सार्वभौमिक ट्यूरिंग मशीन के लिए रुकने की समस्या अनिर्णीत है, क्योंकि यह किसी भी ट्यूरिंग मशीन का अनुकरण कर सकती है, और सार्वभौमिक ट्यूरिंग मशीनों के ठोस उदाहरण बनाए गए हैं।

अन्य धारणाओं के साथ संबंध

सेमी-थू प्रणाली भी शब्द-पुनर्लेखन प्रणाली है - जिसमें मोनैडिक (एरिटी) शब्द वाले फलन उपलब्ध होते हैं, जो बाएँ और दाएँ हाथ के शब्दों के समान वैरियेबल में समाप्त होते हैं,^[8] जैसे इस प्रकार के शब्दों के लिए उचित नियम $f_{2}(f_{1}(x))\rightarrow g(x)$ दिया गया हैं जो स्ट्रिंग नियम $f_{1}f_{2}\rightarrow g$ के समतुल्य है।

सेमी-थ्यू प्रणाली भी विशेष प्रकार की पोस्ट विहित प्रणाली है, अपितु प्रत्येक पोस्ट कैनोनिकल प्रणाली को एसआरएस में भी कम किया जा सकता है। इस प्रकार इसकी दोनों औपचारिकताएं ट्यूरिंग पूर्ण हैं, और इस प्रकार नोम चौमस्की के अप्रतिबंधित व्याकरण के समान हैं, जिन्हें कभी-कभी सेमी-थ्यू व्याकरण भी कहा जाता है।^[9] इस प्रकार औपचारिक व्याकरण सेमी-थ्यू प्रणाली से केवल वर्णमाला को टर्मिनल प्रतीकों और गैर-टर्मिनलों में अलग करने और गैर-टर्मिनलों के बीच प्रारंभिक प्रतीक के निर्धारण से भिन्न होता है। इस प्रकार लेखकों का अल्पसंख्यक वर्ग वास्तव में सेमी-थू प्रणाली को ट्रिपल $(\Sigma ,A,R)$ के रूप में परिभाषित करता है, जहाँ $A\subseteq \Sigma ^{*}$ स्वयंसिद्धों का समुच्चय कहलाता है। इसी प्रकार सेमी-थ्यू प्रणाली की इस उत्पादक परिभाषा के अनुसार अप्रतिबंधित व्याकरण केवल एकल स्वयंसिद्ध के साथ सेमी-थू प्रणाली है, जिसमें कोई वर्णमाला को टर्मिनलों और गैर-टर्मिनलों में विभाजित करता है, और स्वयंसिद्ध को गैर-टर्मिनल बनाता है।^[10] इस वर्णमाला को टर्मिनलों और गैर-टर्मिनलों में विभाजित करने की कला सामान्यतः शक्तिशाली होती है, इस प्रकार के नियमों में उपस्थित टर्मिनलों और गैर-टर्मिनलों के संयोजन के आधार पर चॉम्स्की पदानुक्रम की परिभाषा की अनुमति देता है। इसकी औपचारिक भाषाओं के सिद्धांत में यह महत्वपूर्ण विकास था।

क्वांटम कंप्यूटिंग में, क्वांटम थ्यू प्रणाली की धारणा विकसित की जा सकती है।^[11]

चूँकि क्वांटम गणना आंतरिक रूप से प्रतिवर्ती है, पुनर्लेखन वर्णमाला पर नियम बनाता है, जिसमें $\Sigma$ द्विदिश होना आवश्यक है, अर्थात अंतर्निहित प्रणाली थ्यू प्रणाली है,^{[dubious – discuss]} इसके आधार पर सेमी-थ्यू प्रणाली नहीं होती हैं।

इस प्रकार की वर्णमाला के वर्णों के उपसमूह पर $Q\subseteq \Sigma$ कोई हिल्बर्ट स्थान $\mathbb {C} ^{d}$ संलग्न कर सकता है, और सबस्ट्रिंग को दूसरे में ले जाने वाला पुनर्लेखन नियम स्ट्रिंग्स से जुड़े हिल्बर्ट स्पेस के टेंसर उत्पाद पर एकात्मक ऑपरेशन कर सकता है, इसका तात्पर्य यह है कि वे समुच्चय से वर्णों की संख्या $Q$ को सुरक्षित रखते हैं, मौलिक रूप से इसके समान कोई यह दिखा सकता है कि क्वांटम थ्यू प्रणाली क्वांटम गणना के लिए सार्वभौमिक कम्प्यूटेशनल प्रारूप है, इस अर्थ में कि निष्पादित क्वांटम संचालन एकसमान सर्किट कक्षाओं के अनुरूप हैं, जैसे कि बीक्यूपी में जब स्ट्रिंग पुनर्लेखन नियमों की समाप्ति की गारंटी होती है, इस प्रकार इस इनपुट के आधार पर उचित आकार वाले बहुपदों के लिए कई चरणों के भीतर या समकक्ष रूप से क्वांटम ट्यूरिंग मशीन का उपयोग करते हैं।

इतिहास और महत्व

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

अलोंजो चर्च के सुझाव पर, एमिल पोस्ट ने 1947 में प्रकाशित पेपर में पहली बार थ्यू की निश्चित समस्या को अघुलनशील प्रमाणित किया था, जिसे मार्टिन डेविस (गणितज्ञ) कहते हैं, इसके आधार पर मौलिक गणित से किसी समस्या के लिए पहला अघुलनशील प्रमाणित हुए थे, इस स्थिति में सेमीसमुच्चयों के लिए शब्द गणितीय समस्या का उपयोग करते हैं।^[12]

डेविस का यह भी प्रमाणित किया है कि यह उचित प्रमाण ए. ए. मार्कोव द्वारा स्वतंत्र रूप से प्रस्तुत किया गया था।^[13]

यह भी देखें

एल प्रणाली
मार्कोव एल्गोरिथ्म - स्ट्रिंग पुनर्लेखन प्रणाली का प्रकार
एमयू पज़ल

↑ See section "Undecidability of the word problem" in this article.
↑ Book and Otto, p. 36
↑ Abramsky et al. p. 416
↑ Salomaa et al., p.444
↑ In Book and Otto a semi-Thue system is defined over a finite alphabet through most of the book, except chapter 7 when monoid presentation are introduced, when this assumption is quietly dropped.
↑ Book and Otto, Theorem 7.1.7, p. 149
↑ Post, following Turing, technically makes use of the undecidability of the printing problem (whether a Turing machine ever prints a particular symbol), but the two problems reduce to each other. Indeed, Post includes an extra step in his construction that effectively converts printing the watched symbol into halting.
↑ Nachum Dershowitz and Jean-Pierre Jouannaud. Rewrite Systems (1990) p. 6
↑ D.I.A. Cohen, Introduction to Computer Theory, 2nd ed., Wiley-India, 2007, ISBN 81-265-1334-9, p.572
↑ Dan A. Simovici, Richard L. Tenney, Theory of formal languages with applications, World Scientific, 1999 ISBN 981-02-3729-4, chapter 4
↑ J. Bausch, T. Cubitt, M. Ozols, The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension, Ann. Henri Poincare 18(11), 2017 doi:10.1007/s00023-017-0609-7 pp. 3449-3513
↑ Martin Davis (editor) (1965), The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, after page 292, Raven Press, New York
↑ A. A. Markov (1947) Doklady Akademii Nauk SSSR (N.S.) 55: 583–586

संदर्भ

मोनोग्राफ

रोनाल्ड वी. बुक और फ्रेडरिक ओटो, स्ट्रिंग-रीराइटिंग प्रणाली्स, स्प्रिंगर, 1993, ISBN 0-387-97965-4.
मैथियास जैंटज़ेन, कंफ्लुएंट स्ट्रिंग रीराइटिंग, बिरखौसर, 1988, ISBN 0-387-13715-7.

पाठ्यपुस्तकें

Martin Davis, Ron Sigal, Elaine J. Weyuker, Computability, complexity, and languages: fundamentals of theoretical computer science, 2nd ed., Academic Press, 1994, ISBN 0-12-206382-1, chapter 7
Elaine Rich, Automata, computability and complexity: theory and applications, Prentice Hall, 2007, ISBN 0-13-228806-0, chapter 23.5.

सर्वेक्षण

सैमसन अब्रामस्की, डोव एम. गब्बे, थॉमस एस. ई. माईबौम (सं.), हैंडबुक ऑफ लॉजिक इन कंप्यूटर साइंस: सिमेंटिक प्रारूपिंग, ऑक्सफोर्ड यूनिवर्सिटी प्रेस, 1995, ISBN 0-19-853780-8.
ग्रेज़गोर्ज़ रोज़ेनबर्ग, आर्टो सैलोमा (सं.), औपचारिक भाषाओं की पुस्तिका: शब्द, भाषा, व्याकरण, स्प्रिंगर, 1997, ISBN 3-540-60420-0.

ऐतिहासिक कागजात

Post, Emil (1947). "थ्यू की एक समस्या की पुनरावर्ती असाध्यता". The Journal of Symbolic Logic. 12 (1): 1–11. doi:10.2307/2267170. JSTOR 2267170. S2CID 30320278.{{cite journal}}: CS1 maint: url-status (link)

[1] See section "Undecidability of the word problem" in this article.

[2] Book and Otto, p. 36

[3] Abramsky et al. p. 416

[4] Salomaa et al., p.444

[5] In Book and Otto a semi-Thue system is defined over a finite alphabet through most of the book, except chapter 7 when monoid presentation are introduced, when this assumption is quietly dropped.

[6] Book and Otto, Theorem 7.1.7, p. 149

[7] Post, following Turing, technically makes use of the undecidability of the printing problem (whether a Turing machine ever prints a particular symbol), but the two problems reduce to each other. Indeed, Post includes an extra step in his construction that effectively converts printing the watched symbol into halting.

[8] Nachum Dershowitz and Jean-Pierre Jouannaud. Rewrite Systems (1990) p. 6

[9] D.I.A. Cohen, Introduction to Computer Theory, 2nd ed., Wiley-India, 2007, ISBN 81-265-1334-9, p.572

[10] Dan A. Simovici, Richard L. Tenney, Theory of formal languages with applications, World Scientific, 1999 ISBN 981-02-3729-4, chapter 4

[11] J. Bausch, T. Cubitt, M. Ozols, The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension, Ann. Henri Poincare 18(11), 2017 doi:10.1007/s00023-017-0609-7 pp. 3449-3513

[12] Martin Davis (editor) (1965), The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, after page 292, Raven Press, New York

[13] A. A. Markov (1947) Doklady Akademii Nauk SSSR (N.S.) 55: 583–586

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

@@ Line 1: / Line 1: @@
 {{Short description|String rewriting system}}
-[[सैद्धांतिक कंप्यूटर विज्ञान]] और [[गणितीय तर्क]] में एक स्ट्रिंग [[पुनर्लेखन]] प्रणाली (एसआरएस), जिसे ऐतिहासिक रूप से सेमी-एक्सल थ्यू सिस्टम कहा जाता है, एक (आमतौर पर [[परिमित सेट]]) [[वर्णमाला (कंप्यूटर विज्ञान)]] से [[स्ट्रिंग (कंप्यूटर विज्ञान)]] पर एक पुनर्लेखन प्रणाली है। एक [[द्विआधारी संबंध]] दिया गया है <math>R</math> वर्णमाला पर निश्चित तारों के बीच, जिसे पुनर्लेखन नियम कहा जाता है, द्वारा दर्शाया गया है <math>s\rightarrow t</math>, एक एसआरएस सभी स्ट्रिंग्स के लिए पुनर्लेखन संबंध का विस्तार करता है जिसमें नियमों के बाएँ और दाएँ हाथ [[सबस्ट्रिंग]] के रूप में दिखाई देते हैं, अर्थात <math>usv\rightarrow utv</math>, कहाँ <math>s</math>, <math>t</math>, <math>u</math>, और <math>v</math> तार हैं.
+[[सैद्धांतिक कंप्यूटर विज्ञान]] और [[गणितीय तर्क]] में स्ट्रिंग [[पुनर्लेखन]] प्रणाली (एसआरएस), जिसे ऐतिहासिक रूप से '''सेमी-एक्सल थ्यू प्रणाली''' कहा जाता है, सामान्यतः इसे [[परिमित सेट|परिमित समुच्चय]] में [[वर्णमाला (कंप्यूटर विज्ञान)]] से [[स्ट्रिंग (कंप्यूटर विज्ञान)]] पर पुनर्लेखन प्रणाली के लिए भी जाना जाता है। इस प्रकार इसमें [[द्विआधारी संबंध|बाइनरी संबंध]] भी उपयोग किया जाता है, जो <math>R</math> वर्णमाला पर निश्चित स्ट्रिंग के बीच, जिसे पुनर्लेखन नियम कहा जाता है, इसे <math>s\rightarrow t</math> के द्वारा दर्शाया जाता है, इसके आधार पर एसआरएस सभी स्ट्रिंग्स के लिए पुनर्लेखन संबंध का विस्तार करता है जिसमें नियमों के बाएँ और दाएँ ओर [[सबस्ट्रिंग]] भी दिखाई देती हैं, अर्थात <math>usv\rightarrow utv</math>, जहाँ <math>s</math>, <math>t</math>, <math>u</math>, और <math>v</math> स्ट्रिंग के रूप में हैं।
-सेमी-थ्यू प्रणाली की धारणा अनिवार्य रूप से एक मोनॉइड की प्रस्तुति से मेल खाती है। इस प्रकार वे मोनोइड्स और समूहों के लिए [[शब्द समस्या (गणित)]] को हल करने के लिए एक प्राकृतिक रूपरेखा बनाते हैं।
-एक एसआरएस को सीधे एक [[अमूर्त पुनर्लेखन प्रणाली]] के रूप में परिभाषित किया जा सकता है। इसे एक प्रतिबंधित प्रकार की [[शब्द पुनर्लेखन]] प्रणाली के रूप में भी देखा जा सकता है। एक औपचारिकता के रूप में, स्ट्रिंग पुनर्लेखन प्रणालियाँ [[ट्यूरिंग पूर्ण]] हैं।<ref>See section "Undecidability of the word problem" in this article.</ref> सेमी-थ्यू नाम नॉर्वेजियन गणितज्ञ एक्सल थ्यू से आया है, जिन्होंने 1914 के एक पेपर में स्ट्रिंग रीराइटिंग सिस्टम का व्यवस्थित उपचार पेश किया था।<ref>Book and Otto, p. 36</ref> थू ने इस धारणा को इस उम्मीद से पेश किया कि वह सीमित रूप से प्रस्तुत अर्धसमूहों के लिए शब्द समस्या (गणित) को हल कर सके। केवल 1947 में ही समस्या को [[अनिर्णीत समस्या]] के रूप में दिखाया गया था - यह परिणाम [[एमिल पोस्ट]] और एंड्री मार्कोव (सोवियत गणितज्ञ)|ए द्वारा स्वतंत्र रूप से प्राप्त किया गया था। ए. मार्कोव जूनियर<ref>Abramsky et al. p. 416</ref><ref>Salomaa et al., p.444</ref>
+यहाँ पर सेमी-थ्यू प्रणाली की मुख्य धारणा अनिवार्यतः मोनॉइड की प्रस्तुति से मेल खाती है। इस प्रकार ऐसे मोनोइड्स और समुच्चयों के लिए [[शब्द समस्या (गणित)]] को हल करने के लिए प्राकृतिक रूपरेखा बनायी जाती हैं।
+इसके आधार पर किसी एसआरएस को सीधे [[अमूर्त पुनर्लेखन प्रणाली|स्यूडो पुनर्लेखन प्रणाली]] के रूप में परिभाषित किया जा सकता है। इसे प्रतिबंधित प्रकार की [[शब्द पुनर्लेखन]] प्रणाली के रूप में भी देखा जा सकता है। इसके आधार पर औपचारिकता रूप से किसी स्ट्रिंग की पुनर्लेखन प्रणालियाँ [[ट्यूरिंग पूर्ण]] पर आधारित होती हैं।<ref>See section "Undecidability of the word problem" in this article.</ref> इस प्रकार सेमी-थ्यू नाम नॉर्वेजियन गणितज्ञ एक्सल थ्यू से आया है, जिन्होंने 1914 के पेपर में स्ट्रिंग रीराइटिंग प्रणाली का व्यवस्थित उपचार प्रस्तुत किया था।<ref>Book and Otto, p. 36</ref> इस प्रकार थ्यू ने इस धारणा को इस उम्मीद से प्रस्तुत किया कि वह सीमित रूप से प्रस्तुत होने वाले सेमीसमुच्चयों के लिए शाब्दिक रूप से उत्पन्न होने वाली विभिन्न गणितीय समस्याओं को हल करने में सफल हो सके। इस प्रकार यह केवल 1947 में ही किसी समस्या को [[अनिर्णीत समस्या]] के रूप में दिखाया गया था - यह परिणाम [[एमिल पोस्ट]] और एंड्री मार्कोव के सोवियत गणितज्ञ या ए. मार्कोव जूनियर द्वारा स्वतंत्र रूप से प्राप्त किया गया था।<ref>Abramsky et al. p. 416</ref><ref>Salomaa et al., p.444</ref>
 ==परिभाषा==
-एक स्ट्रिंग पुनर्लेखन प्रणाली या सेमी-थ्यू प्रणाली एक [[टपल]] है <math>(\Sigma, R)</math> कहाँ
+किसी स्ट्रिंग के पुनर्लेखन प्रणाली या सेमी-थ्यू प्रणाली को [[टपल]] <math>(\Sigma, R)</math> कहा जाता है, जहाँ पर इन मुख्य बिंदुओं पर ध्यान दिया जाता हैं जो इस प्रकार हैं-
-* {{math|&Sigma;}} एक वर्णमाला है, जिसे आमतौर पर सीमित माना जाता है।<ref>In Book and Otto a semi-Thue system is defined over a finite alphabet through most of the book, except chapter 7 when monoid presentation are introduced, when this assumption is quietly dropped.</ref> सेट के तत्व <math>\Sigma^*</math> (* यहां क्लेन तारा है) परिमित (संभवतः खाली) तार हैं {{math|&Sigma;}}, जिसे कभी-कभी औपचारिक भाषाओं में शब्द भी कहा जाता है; हम यहां उन्हें बस स्ट्रिंग्स कहेंगे।
+* {{math|&Sigma;}} वर्णमाला है, जिसे सामान्यतः सीमित वर्णमाला माना जाता है।<ref>In Book and Otto a semi-Thue system is defined over a finite alphabet through most of the book, except chapter 7 when monoid presentation are introduced, when this assumption is quietly dropped.</ref> इस प्रकार के समुच्चयओं के लिए तत्व <math>\Sigma^*</math> का उपयोग किया जाता हैं, यहां पर क्लेन स्टार * का उपयोग किया जाता है, इस प्रकार परिमित संभवतः रिक्त स्ट्रिंग {{math|&Sigma;}} का उदाहरण हैं, जिसे कभी-कभी औपचारिक भाषाओं में शब्द भी कहा जाता है, हम यहाँ पर इन्हें बस स्ट्रिंग्स कहते हैं।
-* {{mvar|R}} स्ट्रिंग्स पर एक द्विआधारी संबंध है {{math|&Sigma;}}, अर्थात।, <math>R \subseteq \Sigma^* \times \Sigma^*.</math> प्रत्येक तत्व <math>(u,v) \in R</math> इसे (पुनर्लेखन) नियम कहा जाता है और इसे आमतौर पर लिखा जाता है <math>u \rightarrow v</math>.
+* {{mvar|R}} स्ट्रिंग्स पर बाइनरी संबंध {{math|&Sigma;}} द्वारा प्रदर्शित होता है, अर्थात <math>R \subseteq \Sigma^* \times \Sigma^*.</math> इसमें पाये जाने वाले प्रत्येक तत्व <math>(u,v) \in R</math> के लिए इसे उचित पुनर्लेखन नियम के रूप से जाना जाता है, और इसे सामान्यतः  <math>u \rightarrow v</math> इस प्रकार लिखा जाता है।
-यदि संबंध {{mvar|R}} [[सममित संबंध]] है, तो सिस्टम को थ्यू सिस्टम कहा जाता है।
+यदि संबंध {{mvar|R}} [[सममित संबंध]] को प्रदर्शित करता है, तो इस प्रणाली को थ्यू प्रणाली कहा जाता है।
-में पुनर्लेखन नियम {{mvar|R}} को स्वाभाविक रूप से अन्य स्ट्रिंग्स तक बढ़ाया जा सकता है <math>\Sigma^*</math> के अनुसार सबस्ट्रिंग को फिर से लिखने की अनुमति देकर {{mvar|R}}. अधिक औपचारिक रूप से, एक-चरण पुनर्लेखन संबंध संबंध <math>\xrightarrow[R]{}</math> प्रेरक {{mvar|R}} पर <math>\Sigma^*</math> किसी भी स्ट्रिंग के लिए <math>s, t \in \Sigma^*</math>:
+इसमें पुनर्लेखन नियम {{mvar|R}} को स्वाभाविक रूप से अन्य स्ट्रिंग्स  <math>\Sigma^*</math> तक बढ़ाया जा सकता है, जिसके अनुसार सबस्ट्रिंग को पुनः {{mvar|R}} द्वारा लिखने की अनुमति देकर इसे अधिकांशतः औपचारिक रूप से वन फेस पुनर्लेखन संबंध  <math>\xrightarrow[R]{}</math> प्रेरक {{mvar|R}} पर <math>\Sigma^*</math> किसी भी स्ट्रिंग <math>s, t \in \Sigma^*</math> के लिए इस प्रकार प्रदर्शित होता हैं :
-: <math>s \xrightarrow[R]{} t</math> यदि और केवल यदि अस्तित्व है <math>x, y, u, v \in \Sigma^*</math> ऐसा है कि <math>s = xuy</math>, <math>t = xvy</math>, और <math>u \rightarrow v</math>.
+: इस प्रकार <math>s \xrightarrow[R]{} t</math> होने पर यदि <math>x, y, u, v \in \Sigma^*</math> मान प्राप्त होता हैं जो इस प्रकार है कि- <math>s = xuy</math>, <math>t = xvy</math>, और <math>u \rightarrow v</math> के समान होता हैं।
-तब से <math>\xrightarrow[R]{}</math> पर एक रिश्ता है <math>\Sigma^*</math>, जोड़ी <math>(\Sigma^*, \xrightarrow[R]{})</math> एक अमूर्त पुनर्लेखन प्रणाली की परिभाषा में फिट बैठता है। ज़ाहिर तौर से {{mvar|R}} का एक उपसमुच्चय है <math>\xrightarrow[R]{}</math>. कुछ लेखक तीर के लिए एक अलग संकेतन का उपयोग करते हैं <math>\xrightarrow[R]{}</math> (उदा <math>\xrightarrow[R]{}</math>) इसे अलग करने के लिए {{mvar|R}} अपने आप (<math>\rightarrow</math>) क्योंकि वे बाद में सबस्क्रिप्ट को छोड़ने में सक्षम होना चाहते हैं और फिर भी बीच में भ्रम से बचना चाहते हैं {{mvar|R}} और एक-चरणीय पुनर्लेखन से प्रेरित {{mvar|R}}.
+इस स्थिति में <math>\xrightarrow[R]{}</math> पर रिलेशन <math>x, y, u, v \in \Sigma^*</math> प्राप्त होता हैं, यहाँ पर संयुग्म <math>(\Sigma^*, \xrightarrow[R]{})</math> स्यूडो पुनर्लेखन प्रणाली की परिभाषा में फिट बैठता है। सामान्यतः {{mvar|R}} का उपसमुच्चय <math>\xrightarrow[R]{}</math> है, इसके आधार पर यहाँ पर कुछ लेखक इन एरों के लिए  <math>\xrightarrow[R]{}</math> (उदा <math>\xrightarrow[R]{}</math>) संकेतन का उपयोग करते हैं, इसे अलग करने के लिए {{mvar|R}} स्वयं अपने आप (<math>\rightarrow</math>) द्वारा प्रदर्शित होता हैं। क्योंकि वे इसके पश्चात सबस्क्रिप्ट को छोड़ने में सक्षम होना चाहते हैं और फिर भी बीच में {{mvar|R}} से उत्पन्न होने वाले भ्रम से बचना चाहते हैं, और वन-फेस {{mvar|R}} वाले पुनर्लेखन से प्रेरित होते हैं।
-स्पष्ट रूप से सेमी-थ्यू सिस्टम में हम प्रारंभिक स्ट्रिंग से शुरू करके उत्पादित स्ट्रिंग्स का एक (परिमित या अनंत) अनुक्रम बना सकते हैं <math>s_0 \in \Sigma^*</math> और एक समय में एक सबस्ट्रिंग-प्रतिस्थापन करके इसे बार-बार दोबारा लिखना:
+स्पष्ट रूप से सेमी-थ्यू प्रणाली में हम प्रारंभिक स्ट्रिंग से प्रारंभ करके उत्पादित स्ट्रिंग्स का परिमित या अनंत अनुक्रम <math>s_0 \in \Sigma^*</math> बना सकते हैं, और इस समय सबस्ट्रिंग-प्रतिस्थापन करके इसे बार-बार दोबारा लिखा जाता हैं:
 :<math>s_0 \ \xrightarrow[R]{} \ s_1 \ \xrightarrow[R]{} \ s_2 \ \xrightarrow[R]{} \ \ldots </math>
-इस तरह के शून्य-या-अधिक-चरणों वाले पुनर्लेखन को [[ प्रतिवर्ती सकर्मक समापन ]] द्वारा कैप्चर किया जाता है <math>\xrightarrow[R]{}</math>, द्वारा चिह्नित <math>\xrightarrow[R]{*}</math> (सार पुनर्लेखन प्रणाली#बुनियादी धारणाएँ देखें)। इसे पुनर्लेखन संबंध या न्यूनीकरण संबंध कहा जाता है <math>\Sigma^*</math> प्रेरक {{mvar|R}}.
+इस प्रकार के शून्य-या-अधिक-चरणों वाले पुनर्लेखन को [[ प्रतिवर्ती सकर्मक समापन |प्रतिवर्ती सकर्मक समापन]] <math>\xrightarrow[R]{}</math> द्वारा कैप्चर किया जाता है, <math>\xrightarrow[R]{*}</math> द्वारा चिह्नित इस अर्थ को पुनर्लेखन प्रणाली में मौलिक धारणाओं पर देखा जा सकता हैं। इसे पुनर्लेखन संबंध या न्यूनीकरण संबंध <math>\Sigma^*</math> प्रेरक {{mvar|R}} कहा जाता है।
-== गुरु सर्वांगसमता ==
+== थ्यू सर्वांगसमता ==
-सामान्य तौर पर, सेट <math>\Sigma^*</math> वर्णमाला पर स्ट्रिंग्स की संख्या [[स्ट्रिंग संयोजन]] के [[बाइनरी ऑपरेशन]] के साथ मिलकर एक मुक्त मोनॉइड बनाती है (जिसे इस रूप में दर्शाया गया है)। <math>\cdot</math> और प्रतीक को हटाकर गुणनात्मक रूप से लिखा जाता है)। एसआरएस में, कमी संबंध <math>\xrightarrow[R]{*}</math> मोनॉइड ऑपरेशन के साथ संगत है, जिसका अर्थ है <math>x\xrightarrow[R]{*} y</math> तात्पर्य <math>uxv\xrightarrow[R]{*} uyv</math> सभी स्ट्रिंग के लिए <math>x, y, u, v \in \Sigma^*</math>. तब से <math>\xrightarrow[R]{*}</math> परिभाषा के अनुसार एक [[पूर्व आदेश]] है, <math>\left(\Sigma^*, \cdot, \xrightarrow[R]{*}\right)</math> एक मोनोइडल श्रेणी#मोनोइडल प्रीऑर्डर बनाता है।
+सामान्यतः समुच्चय <math>\Sigma^*</math> वर्णमाला पर स्ट्रिंग्स की संख्या में उपस्थित होने वाले [[स्ट्रिंग संयोजन]] के लिए उपयुक्त [[बाइनरी ऑपरेशन]] के साथ मिलकर मुक्त मोनॉइड बनाते है, जिसे इस रूप में दर्शाया गया है। यहाँ पर प्रतीक को हटाकर गुणनात्मक रूप से लिखा जाता है। इस प्रकार एसआरएस में होने वाली कमी <math>\xrightarrow[R]{*}</math> के संबंध को मोनॉइड ऑपरेशन के साथ संगत किया जाता है, जिसका अर्थ <math>x\xrightarrow[R]{*} y</math> है, जिसका तात्पर्य <math>uxv\xrightarrow[R]{*} uyv</math> के लिए इसमें पाये जाने वाले सभी स्ट्रिंग के लिए <math>x, y, u, v \in \Sigma^*</math> हैं। जहाँ पर <math>\xrightarrow[R]{*}</math> की परिभाषा के अनुसार [[पूर्व आदेश]] प्राप्त होते है, इस प्रकार <math>\left(\Sigma^*, \cdot, \xrightarrow[R]{*}\right)</math>के लिए मोनोइडल श्रेणी या मोनोइडल प्रीऑर्डर बनाया जाता है।
-इसी प्रकार, प्रतिवर्ती सकर्मक सममित समापन <math>\xrightarrow[R]{}</math>, निरूपित <math>\overset{*}{\underset R \leftrightarrow}</math> (सार पुनर्लेखन प्रणाली#बुनियादी धारणाएँ देखें), एक सर्वांगसमता संबंध है, जिसका अर्थ है कि यह एक तुल्यता संबंध है (परिभाषा के अनुसार) और यह स्ट्रिंग संयोजन के साथ भी संगत है। रिश्ता <math>\overset{*}{\underset R \leftrightarrow}</math> द्वारा उत्पन्न थ्यू सर्वांगसमता कहलाती है {{mvar|R}}. थ्यू प्रणाली में, यानी यदि {{mvar|R}} सममित है, पुनर्लेखन संबंध <math>\xrightarrow[R]{*}</math> थू सर्वांगसमता से मेल खाता है <math>\overset{*}{\underset R \leftrightarrow}</math>.
+यहाँ पर प्रतिवर्ती सकर्मक सममित समापन <math>\xrightarrow[R]{}</math>, को <math>\overset{*}{\underset R \leftrightarrow}</math> द्वारा निरूपित करते हैं।
+इस प्रकार पुनर्लेखन प्रणाली की मौलिक धारणाएँ इस प्रकार देखी जा सकती हैं, इसके आधार पर सर्वांगसमताओं का आपस में संबंध रहता है, जिसका अर्थ है कि यह तुल्यता से संबंधित है, इस प्रकार परिभाषा के अनुसार और यह स्ट्रिंग संयोजन के साथ भी संगत रहता है। यहाँ पर रिलेशन <math>\overset{*}{\underset R \leftrightarrow}</math> के द्वारा उत्पन्न होने वाले थ्यू सर्वांगसमता {{mvar|R}} कहलाती है, इस थ्यू प्रणाली में, अर्ताथ यदि {{mvar|R}} सममित है तो पुनर्लेखन संबंध <math>\xrightarrow[R]{*}</math> '''थ्यू सर्वांगसमता''' <math>\overset{*}{\underset R \leftrightarrow}</math> से मेल खाता है।
 == फ़ैक्टर मोनॉइड और मोनॉइड प्रस्तुतियाँ ==
-तब से <math>\overset{*}{\underset R \leftrightarrow}</math> एक सर्वांगसमता है, हम कारक मोनॉयड को परिभाषित कर सकते हैं <math>\mathcal{M}_R = \Sigma^*/\overset{*}{\underset R \leftrightarrow}</math> मुक्त मोनॉइड का <math>\Sigma^*</math> कारक मोनॉयड में थ्यू सर्वांगसमता द्वारा। यदि एक मोनोइड <math>\mathcal{M}</math> के साथ [[समरूपी]] है <math>\mathcal{M}_R</math>, फिर अर्ध-थ्यू प्रणाली <math>(\Sigma, R)</math> की [[मोनोइड प्रस्तुति]] कहलाती है <math>\mathcal{M}</math>.
+इस प्रकार <math>\overset{*}{\underset R \leftrightarrow}</math> रिलेशन के आधार पर यह सर्वांगसमता को प्रदर्शित करता है, यहाँ पर हम इस कारक के आधार पर मोनॉयड  <math>\mathcal{M}_R = \Sigma^*/\overset{*}{\underset R \leftrightarrow}</math> को परिभाषित कर सकते हैं, जिसमें मुक्त मोनॉइड का <math>\Sigma^*</math> कारक मोनॉयड में थ्यू सर्वांगसमता द्वारा प्रदर्शित होता हैं। इसके आधार पर यदि मोनोइड <math>\mathcal{M}</math> के साथ [[समरूपी]] अर्ताथ <math>\mathcal{M}_R</math> है, इसके पश्चात पुनः यह सेमी-थ्यू प्रणाली <math>(\Sigma, R)</math> की [[मोनोइड प्रस्तुति]] <math>\mathcal{M}</math> कहलाती है।
-हमें तुरंत बीजगणित के अन्य क्षेत्रों के साथ कुछ बहुत उपयोगी संबंध मिलते हैं। उदाहरण के लिए, वर्णमाला {a, b} नियमों के साथ {ab → ε, ba → ε }, जहां ε [[खाली स्ट्रिंग]] है, एक जनरेटर पर [[मुक्त समूह]] की प्रस्तुति है। यदि इसके बजाय नियम केवल { ab → ε } हैं, तो हमें [[बाइसिकल मोनोइड]] की एक प्रस्तुति प्राप्त होती है।
+इसके आधार पर हम इसे पुनः बीजगणित के अन्य क्षेत्रों के साथ कुछ बहुत उपयोगी संबंध मिलते हैं। उदाहरण के लिए, वर्णमाला {a, b} नियमों के साथ {ab → ε, ba → ε } इसका उपयोग किया जाता हैं, जहाँ पर ε [[खाली स्ट्रिंग|रिक्त स्ट्रिंग]] को प्रदर्शित करता है, इस प्रकार से जनरेटर पर [[मुक्त समूह]] को प्रस्तुत किया जाता है। यदि इसके अतिरिक्त इस नियम को केवल { ab → ε } पर स्थापित करते हैं, तो हमें [[बाइसिकल मोनोइड]] की प्राप्ति होती है।
-मोनोइड्स की प्रस्तुति के रूप में सेमी-थ्यू सिस्टम का महत्व निम्नलिखित द्वारा मजबूत किया गया है:
+मोनोइड्स की प्रस्तुति के रूप में सेमी-थ्यू प्रणाली का महत्व निम्नलिखित द्वारा मजबूत किया गया है:
-'प्रमेय': प्रत्येक मोनॉइड में रूप की एक प्रस्तुति होती है <math>(\Sigma, R)</math>, इस प्रकार इसे हमेशा अर्ध-थ्यू प्रणाली द्वारा प्रस्तुत किया जा सकता है, संभवतः एक अनंत वर्णमाला पर।<ref>Book and Otto, Theorem 7.1.7, p. 149</ref>
+'प्रमेय': प्रत्येक मोनॉइड में <math>(\Sigma, R)</math> रूप की प्रस्तुति होती है, इस प्रकार इसे हमेशा सेमी-थ्यू प्रणाली द्वारा प्रस्तुत किया जा सकता है, संभवतः अनंत वर्णमाला पर इसको प्रस्तुत किया जाता हैं।<ref>Book and Otto, Theorem 7.1.7, p. 149</ref> इस संदर्भ में, समुच्चय <math>\Sigma</math> के जनरेटरों का समुच्चय <math>\mathcal{M}</math> कहलाता है, और <math>R</math> संबंधों को परिभाषित करने वाले समुच्चय <math>\mathcal{M}</math> को कहा जाता है, हम मोनोइड्स को उनकी प्रस्तुति के आधार पर तुरंत वर्गीकृत कर सकते हैं। जिसे <math>\mathcal{M}</math> कहा जाता है
-इस संदर्भ में, सेट <math>\Sigma</math> के जनरेटरों का समुच्चय कहलाता है <math>\mathcal{M}</math>, और <math>R</math> संबंधों को परिभाषित करने वाले समुच्चय को कहा जाता है <math>\mathcal{M}</math>. हम मोनोइड्स को उनकी प्रस्तुति के आधार पर तुरंत वर्गीकृत कर सकते हैं। <math>\mathcal{M}</math> कहा जाता है
+* अंतिम रूप से उत्पन्न यदि <math>\Sigma</math> परिमित है।
-* अंतिम रूप से उत्पन्न यदि <math>\Sigma</math> परिमित है.
+* दोनों को अंतिम रूप से प्रस्तुत किया गया है, इस प्रकार <math>\Sigma</math> और <math>R</math> परिमित हैं।
-* दोनों को अंतिम रूप से प्रस्तुत किया गया है <math>\Sigma</math> और <math>R</math> परिमित हैं.
 == समस्या शब्द की अनिश्चयता ==
-पोस्ट ने शब्द समस्या (अर्धसमूहों के लिए) को सामान्य रूप से अनिर्णीत साबित कर दिया, अनिवार्य रूप से [[रुकने की समस्या]] को कम करके<ref>Post, following [[Turing's proof|Turing]], technically makes use of the undecidability of the ''printing problem'' (whether a Turing machine ever prints a particular symbol), but the two problems reduce to each other. Indeed, Post includes an extra step in his construction that effectively converts printing the watched symbol into halting.</ref> [[ ट्यूरिंग मशीनें ]] के लिए शब्द समस्या का एक उदाहरण।
+पोस्ट ने शब्द समस्या सेमीसमुच्चयों के लिए सामान्य रूप से अनिर्णीत प्रमाणित कर दिया गया हैं, इस प्रकार अनिवार्य रूप से [[रुकने की समस्या]] को कम करके<ref>Post, following [[Turing's proof|Turing]], technically makes use of the undecidability of the ''printing problem'' (whether a Turing machine ever prints a particular symbol), but the two problems reduce to each other. Indeed, Post includes an extra step in his construction that effectively converts printing the watched symbol into halting.</ref> [[ ट्यूरिंग मशीनें |ट्यूरिंग मशीनें]] के लिए शब्द समस्या का उदाहरण प्रकट किया गया हैं।
-सीधे तौर पर, पोस्ट ने ट्यूरिंग मशीन प्लस टेप की स्थिति की एक सीमित स्ट्रिंग के रूप में एक एन्कोडिंग तैयार की, जैसे कि इस मशीन की गतिविधियों को इस स्ट्रिंग एन्कोडिंग पर अभिनय करने वाले एक स्ट्रिंग रीराइट सिस्टम द्वारा किया जा सकता है। एन्कोडिंग की वर्णमाला में अक्षरों का एक सेट होता है <math> S_0, S_1, \dotsc, S_m </math> टेप पर प्रतीकों के लिए (जहाँ <math> S_0 </math> मतलब खाली), अक्षरों का एक और सेट <math> q_1, \dotsc, q_r </math> ट्यूरिंग मशीन की अवस्थाओं के लिए, और अंत में तीन अक्षर <math> q_{r+1}, q_{r+2}, h </math> जिनकी एन्कोडिंग में विशेष भूमिका होती है। <math> q_{r+1} </math> और <math> q_{r+2} </math> ट्यूरिंग मशीन की सहज रूप से अतिरिक्त आंतरिक अवस्थाएँ हैं जिनमें यह रुकते समय परिवर्तित हो जाती है, जबकि <math>h</math> टेप के गैर-रिक्त भाग के अंत को चिह्नित करता है; एक मशीन पहुंच रही है <math>h</math> वैसा ही व्यवहार करना चाहिए जैसे कि वहां कोई रिक्त स्थान था, और <math>h</math> अगली कोठरी में था. वे स्ट्रिंग जो ट्यूरिंग मशीन स्थिति की वैध एन्कोडिंग हैं, एक से शुरू होती हैं <math>h</math>, उसके बाद शून्य या अधिक प्रतीक अक्षर, उसके बाद ठीक एक आंतरिक स्थिति अक्षर <math>q_i</math> (जो मशीन की स्थिति को एन्कोड करता है), उसके बाद एक या अधिक प्रतीक अक्षर, उसके बाद अंत होता है <math>h</math>. प्रतीक अक्षर टेप की सामग्री से सीधे होते हैं, और आंतरिक राज्य पत्र सिर की स्थिति को चिह्नित करता है; आंतरिक स्थिति पत्र के बाद का प्रतीक वह सेल है जो वर्तमान में ट्यूरिंग मशीन के प्रमुख के अंतर्गत है।
+सीधे तौर पर पोस्ट ने ट्यूरिंग मशीन प्लस टेप की स्थिति की सीमित स्ट्रिंग के रूप में एन्कोडिंग तैयार की हैं, जैसे कि इस मशीन की गतिविधियों को इस स्ट्रिंग एन्कोडिंग पर अभिनय करने वाले स्ट्रिंग रीराइट प्रणाली द्वारा किया जा सकता है। इसके आधार पर एन्कोडिंग की वर्णमाला में अक्षरों का समुच्चय होता है, जहाँ पर <math> S_0, S_1, \dotsc, S_m </math> टेप पर प्रतीकों के लिए जहाँ <math> S_0 </math> का अर्थ रिक्त, अक्षरों का और समुच्चय <math> q_1, \dotsc, q_r </math> ट्यूरिंग मशीन की अवस्थाओं के लिए, और अंत में तीन अक्षर <math> q_{r+1}, q_{r+2}, h </math> जिनकी एन्कोडिंग में विशेष भूमिका होती है। इस प्रकार <math> q_{r+1} </math> और <math> q_{r+2} </math> ट्यूरिंग मशीन की सहज रूप से अतिरिक्त आंतरिक अवस्थाएँ हैं, जिनमें यह रुकते समय परिवर्तित हो जाती है, जबकि <math>h</math> टेप के गैर-रिक्त भाग के अंत को चिह्नित करता है, मशीन <math>h</math> पर पहुंच रही है, इसी प्रकार मशीन से उचित व्यवहार करना चाहिए, जैसे कि वहां कोई रिक्त स्थान था, और <math>h</math> अगले बाॅक्स में था, जिसमें वे स्ट्रिंग जो ट्यूरिंग मशीन स्थिति की वैध एन्कोडिंग हैं, वे <math>h</math> से प्रारंभ होती हैं , इसके बाद शून्य या अधिक प्रतीक अक्षर, उसके बाद ठीक आंतरिक स्थिति अक्षर <math>q_i</math> जो मशीन की स्थिति को एन्कोड करता है, उसके बाद या अधिक प्रतीक अक्षर, उसके बाद <math>h</math> का अंत होता है, इस प्रकार इस प्रतीक को उचित अक्षर द्वारा टेप करके इसकी सामग्री से सीधे संयोजित करते हैं, और आंतरिक स्थिति पत्र के ऊपर की स्थिति को चिह्नित किया जाता है, इस प्रकार आंतरिक स्थिति पत्र के बाद का प्रतीक वह सेल है, जो वर्तमान में ट्यूरिंग मशीन के प्रमुख के अंतर्गत है।
-एक संक्रमण जहां मशीन राज्य में होने पर <math> q_i </math> और प्रतीक देख रहे हैं <math>S_k</math> वापस प्रतीक लिखता है <math> S_l</math>, दाईं ओर चलता है, और स्थिति में परिवर्तित हो जाता है <math>q_j</math> पुनर्लेखन द्वारा कार्यान्वित किया जाता है
+एक संक्रमण जहां मशीन इस स्थिति में होने वाले <math> q_i </math> के मान और प्रतीक <math>S_k</math> को देख रहे हैं, जहाँ <math> S_l</math> को वापस से इसके प्रतीक के रूप में लिखा जाता है, यह इससे दाईं ओर चलता है, और स्थिति में परिवर्तित हो जाता है, इस प्रकार <math>q_j</math> की पुनर्लेखन द्वारा कार्यान्वित किया जाता है, जो इस प्रकार हैं-
 : <math> q_i S_k \to S_l q_j </math>
-जबकि वह संक्रमण बाईं ओर जाने के बजाय पुनर्लेखन द्वारा कार्यान्वित होता है
+जबकि वह संक्रमण बाईं ओर जाने के अतिरिक्त पुनर्लेखन द्वारा कार्यान्वित होता है।
 : <math> S_p q_i S_k \to q_j S_p S_l </math>
-प्रत्येक प्रतीक के लिए एक उदाहरण के साथ <math> S_p </math> बायीं ओर उस कक्ष में. यदि हम टेप के विज़िट किए गए भाग के अंत तक पहुँचते हैं, तो हम इसके बजाय उपयोग करते हैं
+प्रत्येक प्रतीक के लिए उदाहरण के साथ <math> S_p </math> बायीं ओर उस कक्ष में यदि हम टेप के विज़िट किए गए भाग के अंत तक पहुँचते हैं, तो हम इसके अतिरिक्त उपयोग करते हैं।
 : <math> h q_i S_k \to h q_j S_0 S_l </math>,
-स्ट्रिंग को एक अक्षर से लंबा करना। क्योंकि सभी पुनर्लेखन में एक आंतरिक स्थिति पत्र शामिल होता है <math>q_i</math>, वैध एन्कोडिंग में केवल एक ऐसा अक्षर होता है, और प्रत्येक पुनर्लेखन बिल्कुल एक ऐसा अक्षर उत्पन्न करता है, पुनर्लेखन प्रक्रिया बिल्कुल एन्कोडेड ट्यूरिंग मशीन के चलने का अनुसरण करती है। इससे साबित होता है कि स्ट्रिंग रीराइट सिस्टम ट्यूरिंग पूर्ण हैं।
+इस प्रकार किसी स्ट्रिंग को अक्षर से लंबा किया जाता हैं। क्योंकि सभी पुनर्लेखन में आंतरिक स्थिति पत्र <math>q_i</math> पर उपस्थित होता है, इस प्रकार किसी वैध एन्कोडिंग में केवल ऐसा अक्षर होता है, और प्रत्येक पुनर्लेखन बिल्कुल ऐसा अक्षर उत्पन्न करता है, जो पुनर्लेखन प्रक्रिया बिल्कुल एन्कोडेड ट्यूरिंग मशीन के चलने का अनुसरण करती है। इससे यह प्रमाणित होता है कि स्ट्रिंग रीराइट प्रणाली ट्यूरिंग पूर्ण हैं।
-दो रुके हुए चिन्ह होने का कारण <math> q_{r+1} </math> और <math> q_{r+2} </math> क्या हम चाहते हैं कि सभी रुकने वाली ट्यूरिंग मशीनें एक ही कुल स्थिति में समाप्त हों, न कि केवल एक विशेष आंतरिक स्थिति में। इसके लिए रुकने के बाद टेप को साफ़ करने की आवश्यकता होती है, इसलिए <math> q_{r+1} </math> तक पहुंचने तक उस पर बाईं ओर दिए गए चिह्न को खाता है <math>h</math>, जहां यह संक्रमण करता है <math> q_{r+2} </math> जो इसके बजाय अपने दाहिनी ओर के प्रतीक को खाता है। (इस चरण में स्ट्रिंग रीराइट सिस्टम अब ट्यूरिंग मशीन का अनुकरण नहीं करता है, क्योंकि वह टेप से कोशिकाओं को नहीं हटा सकता है।) सभी प्रतीकों के चले जाने के बाद, हम टर्मिनल स्ट्रिंग पर पहुंच गए हैं <math> h q_{r+2} h </math>.
+इस कारण दो रुके हुए चिन्ह <math> q_{r+1} </math> और <math> q_{r+2} </math> होने का कारण यह हो सकता हैं, कि क्या हम चाहते हैं कि सभी रुकने वाली ट्यूरिंग मशीनें ही कुल स्थिति में समाप्त हों, न कि केवल विशेष आंतरिक स्थिति में रहें। इसके लिए रुकने के बाद टेप को साफ़ करने की आवश्यकता होती है, इसलिए <math> q_{r+1} </math> तक पहुंचने तक उस पर बाईं ओर दिए गए चिह्न <math>h</math> को खत्म कर देता है, जहां यह संक्रमण <math> q_{r+2} </math> पर प्रभावित होता है, जो इसके अतिरिक्त अपने दाहिनी ओर के प्रतीक को खत्म करता है। इस प्रकार इस चरण में स्ट्रिंग रीराइट प्रणाली अब ट्यूरिंग मशीन का अनुकरण नहीं करता है, क्योंकि वह टेप से कोशिकाओं को नहीं हटा सकता है। इस प्रकार सभी प्रतीकों के चले जाने के बाद, हम टर्मिनल स्ट्रिंग <math> h q_{r+2} h </math> पर पहुंच गए हैं।
-शब्द समस्या के लिए निर्णय प्रक्रिया से यह निर्णय लेने की प्रक्रिया भी प्राप्त होगी कि दी गई ट्यूरिंग मशीन किसी विशेष कुल स्थिति में शुरू होने पर समाप्त हो जाती है या नहीं <math> t </math>, परीक्षण करके कि क्या <math> t </math> और <math> h q_{r+2} h </math> इस स्ट्रिंग पुनर्लेखन प्रणाली के संबंध में समान सर्वांगसमता वर्ग से संबंधित हैं। तकनीकी रूप से, हमारे पास निम्नलिखित हैं:
+शब्द समस्या के लिए निर्णय प्रक्रिया से यह निर्णय लेने की प्रक्रिया भी प्राप्त होगी कि दी गई ट्यूरिंग मशीन किसी विशेष कुल स्थिति में प्रारंभ होने पर समाप्त हो जाती है या <math> t </math> पर नहीं होती हैं, इसका परीक्षण करके कि क्या <math> t </math> और <math> h q_{r+2} h </math> इस स्ट्रिंग पुनर्लेखन प्रणाली के संबंध में समान सर्वांगसमता वर्ग से संबंधित हैं। इस तकनीकी के आधार पर हमारे पास निम्नलिखित बिंदु प्राप्त होते हैं:
-लेम्मा. होने देना <math>M</math> एक नियतात्मक ट्यूरिंग मशीन बनें और <math>R</math> स्ट्रिंग रीराइट सिस्टम को कार्यान्वित करें <math>M</math>, जैसा ऊपर वर्णित है। तब <math>M</math> के रूप में एन्कोड की गई कुल स्थिति से शुरू होने पर रुक जाएगा <math>t</math> अगर और केवल अगर <math> t \mathrel{\overset{*}{\underset{R}{\leftrightarrow}}} h q_{r+2} h </math> (अर्थात, यदि और केवल यदि <math>t</math> और <math> h q_{r+2} h </math> थू के सर्वांगसम हैं <math>R</math>).
+लेम्मा के आधार पर <math>M</math> नियतात्मक ट्यूरिंग मशीन बनें और <math>R</math> स्ट्रिंग रीराइट प्रणाली <math>M</math> को कार्यान्वित करते हैं, जैसा ऊपर वर्णित है। इसके पश्चात <math>M</math> के रूप में एन्कोड की गई कुल स्थिति से प्रारंभ होने पर रुक जाएगा, इस कारण <math>t</math> यदि <math> t \mathrel{\overset{*}{\underset{R}{\leftrightarrow}}} h q_{r+2} h </math> के लिए अर्थात, यदि <math>t</math> और <math> h q_{r+2} h </math> थ्यू के लिए सर्वांगसम मान <math>R</math> के समान हैं।
-वह <math> t \mathrel{\overset{*}{\underset{R}{\rightarrow}}} h q_{r+2} h </math> अगर <math>M</math> से प्रारंभ करने पर रुक जाता है <math>t</math> के निर्माण से तत्काल है <math>R</math> (बस चल रहा है <math>M</math> जब तक यह रुकता नहीं तब तक इसका प्रमाण बनता है <math> t \mathrel{\overset{*}{\underset{R}{\rightarrow}}} h q_{r+2} h </math>), लेकिन <math> \overset{*}{\underset{R}{\leftrightarrow}} </math> ट्यूरिंग मशीन को भी अनुमति देता है <math>M</math> पीछे की ओर कदम उठाना. यहाँ यह प्रासंगिक हो जाता है कि <math>M</math> नियतिवादी है, क्योंकि तब आगे के सभी चरण अद्वितीय होते हैं; में एक <math> \overset{*}{\underset{R}{\leftrightarrow}} </math> से चलना <math>t</math> को <math> h q_{r+2} h </math> अंतिम पिछड़े कदम को उसके समकक्ष द्वारा आगे के कदम के रूप में पालन किया जाना चाहिए, इसलिए ये दोनों रद्द हो जाते हैं, और प्रेरण द्वारा सभी पिछड़े कदमों को इस तरह की चाल से हटाया जा सकता है। इसलिए यदि <math>M</math> से शुरू होने पर रुकता नहीं है <math>t</math>, यानी, अगर हमारे पास नहीं है <math> t \mathrel{\overset{*}{\underset{R}{\rightarrow}}} h q_{r+2} h </math>, तो हमारे पास भी नहीं है <math> t \mathrel{\overset{*}{\underset{R}{\leftrightarrow}}} h q_{r+2} h </math>. इसलिए निर्णय ले रहे हैं <math> \overset{*}{\underset{R}{\leftrightarrow}} </math> हमें रुकने की समस्या का उत्तर बताता है <math>M</math>.
+इस प्रकार <math> t \mathrel{\overset{*}{\underset{R}{\rightarrow}}} h q_{r+2} h </math> पर यदि <math>M</math> से प्रारंभ करने पर रुक जाता है, तो <math>t</math> के निर्माण से तत्काल <math>R</math>  का मान प्राप्त होता है, जहाँ पर <math>M</math> को जब तक यह रुकता नहीं जाता तब तक इसका प्रमाण उत्पन्न करता है, इस प्रकार <math> t \mathrel{\overset{*}{\underset{R}{\rightarrow}}} h q_{r+2} h </math>) मान प्राप्त होता हैं, अपितु <math> \overset{*}{\underset{R}{\leftrightarrow}} </math> ट्यूरिंग मशीन को भी अनुमति देता है, जिसके लिए <math>M</math> के पीछे की ओर इस स्टेप को बढ़ाते हैं, इस प्रकार यहाँ यह प्रासंगिक हो जाता है कि <math>M</math> नियतिवादी है, क्योंकि तब आगे के सभी चरण अद्वितीय होते हैं, जिसमें <math> \overset{*}{\underset{R}{\leftrightarrow}} </math> से चलना प्रारंभ करके <math>t</math> को <math> h q_{r+2} h </math> के अंतिम पिछड़े कदम को उसके समकक्ष द्वारा आगे के कदम के रूप में पालन किया जाना आवश्यक होता हैं, इसलिए ये दोनों निरस्त हो जाते हैं, और प्रेरण द्वारा सभी पिछड़े कदमों को इस तरह की चाल से हटाया जा सकता है। इसलिए यदि <math>M</math> से प्रारंभ होने पर <math>t</math> पर रुकता नहीं है, अर्ताथ यदि हमारे पास <math> t \mathrel{\overset{*}{\underset{R}{\rightarrow}}} h q_{r+2} h </math> नहीं है, तो हमारे पास <math> t \mathrel{\overset{*}{\underset{R}{\leftrightarrow}}} h q_{r+2} h </math> भी नहीं है, इसलिए <math> \overset{*}{\underset{R}{\leftrightarrow}} </math> के द्वारा निर्णय लेकर हमें रुकने की समस्या का उत्तर <math>M</math> बताता है।
-इस तर्क की एक स्पष्ट सीमा यह है कि एक अर्धसमूह तैयार करना <math> \Sigma^*\big/\overset{*}{\underset{R}{\leftrightarrow}} </math> अनिर्णीत शब्द समस्या के साथ, सबसे पहले किसी के पास ट्यूरिंग मशीन का एक ठोस उदाहरण होना चाहिए <math>M</math> जिसके लिए रुकने की समस्या अनिर्णीत है, लेकिन सामान्य रुकने की समस्या की अनिर्णयता के प्रमाण में मौजूद विभिन्न ट्यूरिंग मशीनों में एक घटक के रूप में रुकने की समस्या को हल करने वाली एक काल्पनिक ट्यूरिंग मशीन होती है, इसलिए उनमें से कोई भी मशीन वास्तव में मौजूद नहीं हो सकती है; यह सब साबित करता है कि कुछ ट्यूरिंग मशीन है जिसके लिए निर्णय समस्या अनिर्णीत है। हालाँकि, कुछ ट्यूरिंग मशीनों में अनिर्णीत रुकने की समस्या है, इसका मतलब है कि एक सार्वभौमिक ट्यूरिंग मशीन के लिए रुकने की समस्या अनिर्णीत है (क्योंकि यह किसी भी ट्यूरिंग मशीन का अनुकरण कर सकती है), और सार्वभौमिक ट्यूरिंग मशीनों के ठोस उदाहरण बनाए गए हैं।
+इस तर्क की स्पष्ट सीमा यह है कि सेमीसमूह तैयार करना होता हैं, जिसके लिए <math> \Sigma^*\big/\overset{*}{\underset{R}{\leftrightarrow}} </math> के द्वारा अनिर्णीत शब्द समस्या के साथ, सबसे पहले किसी के पास ट्यूरिंग मशीन <math>M</math> का ठोस उदाहरण होना चाहिए, जिसके लिए रुकने की समस्या अनिर्णीत है, अपितु सामान्य रुकने की समस्या की अनिर्णयता के प्रमाण में सम्मिलित होने वाले विभिन्न ट्यूरिंग मशीनों में घटक के रूप में रुकने की समस्या को हल करने वाली काल्पनिक ट्यूरिंग मशीन होती है, इसलिए उनमें से कोई भी मशीन वास्तव में सम्मिलित नहीं हो सकती है, यह सब प्रमाणित करता है कि कुछ ट्यूरिंग मशीन है जिसके लिए निर्णय समस्या अनिर्णीत है। चूंकि, कुछ ट्यूरिंग मशीनों में अनिर्णीत रुकने की समस्या है, इसका अर्थ है कि सार्वभौमिक ट्यूरिंग मशीन के लिए रुकने की समस्या अनिर्णीत है, क्योंकि यह किसी भी ट्यूरिंग मशीन का अनुकरण कर सकती है, और सार्वभौमिक ट्यूरिंग मशीनों के ठोस उदाहरण बनाए गए हैं।
 == अन्य धारणाओं के साथ संबंध ==
-सेमी-थू प्रणाली भी एक [[शब्द-पुनर्लेखन]] प्रणाली है - जिसमें मोनैडिक (एरिटी) शब्द (फ़ंक्शन) होते हैं जो बाएँ और दाएँ हाथ के शब्दों के समान चर में समाप्त होते हैं,<ref>[[Nachum Dershowitz]] and [[Jean-Pierre Jouannaud]]. [http://citeseer.ist.psu.edu/dershowitz90rewrite.html Rewrite Systems] (1990) p. 6</ref> जैसे एक शब्द नियम <math>f_2(f_1(x)) \rightarrow g(x)</math> स्ट्रिंग नियम के समतुल्य है <math>f_1f_2 \rightarrow g</math>.
+सेमी-थू प्रणाली भी [[शब्द-पुनर्लेखन]] प्रणाली है - जिसमें मोनैडिक (एरिटी) शब्द वाले फलन उपलब्ध होते हैं, जो बाएँ और दाएँ हाथ के शब्दों के समान वैरियेबल में समाप्त होते हैं,<ref>[[Nachum Dershowitz]] and [[Jean-Pierre Jouannaud]]. [http://citeseer.ist.psu.edu/dershowitz90rewrite.html Rewrite Systems] (1990) p. 6</ref> जैसे इस प्रकार के शब्दों के लिए उचित नियम <math>f_2(f_1(x)) \rightarrow g(x)</math> दिया गया हैं जो स्ट्रिंग नियम <math>f_1f_2 \rightarrow g</math> के समतुल्य है।
-सेमी-थ्यू सिस्टम भी एक विशेष प्रकार का [[ पोस्ट विहित प्रणाली ]] है, लेकिन प्रत्येक पोस्ट कैनोनिकल सिस्टम को एसआरएस में भी कम किया जा सकता है। दोनों औपचारिकताएं ट्यूरिंग पूर्ण हैं, और इस प्रकार [[नोम चौमस्की]] के [[अप्रतिबंधित व्याकरण]] के बराबर हैं, जिन्हें कभी-कभी सेमी-थ्यू व्याकरण भी कहा जाता है।<ref>[[Daniel I. A. Cohen|D.I.A. Cohen]], Introduction to Computer Theory, 2nd ed., Wiley-India, 2007, {{isbn|81-265-1334-9}}, p.572</ref> एक [[औपचारिक व्याकरण]] सेमी-थ्यू प्रणाली से केवल वर्णमाला को [[टर्मिनल प्रतीक]]ों और गैर-टर्मिनलों में अलग करने और गैर-टर्मिनलों के बीच एक प्रारंभिक प्रतीक के निर्धारण से भिन्न होता है। लेखकों का एक अल्पसंख्यक वर्ग वास्तव में सेमी-थू प्रणाली को ट्रिपल के रूप में परिभाषित करता है <math>(\Sigma, A, R)</math>, कहाँ <math>A\subseteq\Sigma^*</math> स्वयंसिद्धों का समुच्चय कहलाता है। सेमी-थ्यू प्रणाली की इस उत्पादक परिभाषा के तहत, एक अप्रतिबंधित व्याकरण केवल एक एकल स्वयंसिद्ध के साथ एक अर्ध-थू प्रणाली है जिसमें कोई वर्णमाला को टर्मिनलों और गैर-टर्मिनलों में विभाजित करता है, और स्वयंसिद्ध को एक गैर-टर्मिनल बनाता है।<ref>Dan A. Simovici, Richard L. Tenney, ''Theory of formal languages with applications'', World Scientific, 1999 {{isbn|981-02-3729-4}}, chapter 4</ref> वर्णमाला को टर्मिनलों और गैर-टर्मिनलों में विभाजित करने की सरल कला शक्तिशाली है; यह नियमों में शामिल टर्मिनलों और गैर-टर्मिनलों के संयोजन के आधार पर [[चॉम्स्की पदानुक्रम]] की परिभाषा की अनुमति देता है। औपचारिक भाषाओं के सिद्धांत में यह एक महत्वपूर्ण विकास था।
+सेमी-थ्यू प्रणाली भी विशेष प्रकार की [[ पोस्ट विहित प्रणाली |पोस्ट विहित प्रणाली]] है, अपितु प्रत्येक पोस्ट कैनोनिकल प्रणाली को एसआरएस में भी कम किया जा सकता है। इस प्रकार इसकी दोनों औपचारिकताएं ट्यूरिंग पूर्ण हैं, और इस प्रकार [[नोम चौमस्की]] के [[अप्रतिबंधित व्याकरण]] के समान हैं, जिन्हें कभी-कभी सेमी-थ्यू व्याकरण भी कहा जाता है।<ref>[[Daniel I. A. Cohen|D.I.A. Cohen]], Introduction to Computer Theory, 2nd ed., Wiley-India, 2007, {{isbn|81-265-1334-9}}, p.572</ref> इस प्रकार [[औपचारिक व्याकरण]] सेमी-थ्यू प्रणाली से केवल वर्णमाला को [[टर्मिनल प्रतीक|टर्मिनल प्रतीकों]] और गैर-टर्मिनलों में अलग करने और गैर-टर्मिनलों के बीच प्रारंभिक प्रतीक के निर्धारण से भिन्न होता है। इस प्रकार लेखकों का अल्पसंख्यक वर्ग वास्तव में सेमी-थू प्रणाली को ट्रिपल <math>(\Sigma, A, R)</math> के रूप में परिभाषित करता है, जहाँ <math>A\subseteq\Sigma^*</math> स्वयंसिद्धों का समुच्चय कहलाता है। इसी प्रकार सेमी-थ्यू प्रणाली की इस उत्पादक परिभाषा के अनुसार अप्रतिबंधित व्याकरण केवल एकल स्वयंसिद्ध के साथ सेमी-थू प्रणाली है, जिसमें कोई वर्णमाला को टर्मिनलों और गैर-टर्मिनलों में विभाजित करता है, और स्वयंसिद्ध को गैर-टर्मिनल बनाता है।<ref>Dan A. Simovici, Richard L. Tenney, ''Theory of formal languages with applications'', World Scientific, 1999 {{isbn|981-02-3729-4}}, chapter 4</ref> इस वर्णमाला को टर्मिनलों और गैर-टर्मिनलों में विभाजित करने की कला सामान्यतः शक्तिशाली होती है, इस प्रकार के नियमों में उपस्थित टर्मिनलों और गैर-टर्मिनलों के संयोजन के आधार पर [[चॉम्स्की पदानुक्रम]] की परिभाषा की अनुमति देता है। इसकी औपचारिक भाषाओं के सिद्धांत में यह महत्वपूर्ण विकास था।
-क्वांटम कंप्यूटिंग में, क्वांटम थ्यू सिस्टम की धारणा विकसित की जा सकती है।<ref>J. Bausch, T. Cubitt, M. Ozols, ''The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension'', Ann. Henri Poincare 18(11), 2017 {{doi|10.1007/s00023-017-0609-7}} pp. 3449-3513</ref>
+क्वांटम कंप्यूटिंग में, क्वांटम थ्यू प्रणाली की धारणा विकसित की जा सकती है।<ref>J. Bausch, T. Cubitt, M. Ozols, ''The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension'', Ann. Henri Poincare 18(11), 2017 {{doi|10.1007/s00023-017-0609-7}} pp. 3449-3513</ref>
-चूँकि क्वांटम गणना आंतरिक रूप से प्रतिवर्ती है, पुनर्लेखन वर्णमाला पर नियम बनाता है <math>\Sigma</math> द्विदिश होना आवश्यक है (अर्थात अंतर्निहित प्रणाली एक थू प्रणाली है,{{dubious|Quantum semi-Thue systems|date=September 2022}} अर्ध-थ्यू प्रणाली नहीं)।
-वर्णमाला वर्णों के उपसमूह पर <math>Q\subseteq \Sigma</math> कोई हिल्बर्ट स्थान संलग्न कर सकता है <math>\mathbb C^d</math>, और एक सबस्ट्रिंग को दूसरे में ले जाने वाला एक पुनर्लेखन नियम स्ट्रिंग्स से जुड़े हिल्बर्ट स्पेस के टेंसर उत्पाद पर एक एकात्मक ऑपरेशन कर सकता है; इसका तात्पर्य यह है कि वे सेट से वर्णों की संख्या को सुरक्षित रखते हैं <math>Q</math>. शास्त्रीय मामले के समान कोई यह दिखा सकता है कि क्वांटम थू प्रणाली क्वांटम गणना के लिए एक सार्वभौमिक कम्प्यूटेशनल मॉडल है, इस अर्थ में कि निष्पादित क्वांटम संचालन एकसमान सर्किट कक्षाओं के अनुरूप हैं (जैसे कि [[बीक्यूपी]] में जब स्ट्रिंग पुनर्लेखन नियमों की समाप्ति की गारंटी होती है) इनपुट आकार में बहुपद के कई चरणों के भीतर), या समकक्ष रूप से एक [[क्वांटम ट्यूरिंग मशीन]]।
+चूँकि क्वांटम गणना आंतरिक रूप से प्रतिवर्ती है, पुनर्लेखन वर्णमाला पर नियम बनाता है, जिसमें <math>\Sigma</math> द्विदिश होना आवश्यक है, अर्थात अंतर्निहित प्रणाली थ्यू प्रणाली है,{{dubious|Quantum semi-Thue systems|date=September 2022}} इसके आधार पर सेमी-थ्यू प्रणाली नहीं होती हैं।
+इस प्रकार की वर्णमाला के वर्णों के उपसमूह पर <math>Q\subseteq \Sigma</math> कोई हिल्बर्ट स्थान <math>\mathbb C^d</math> संलग्न कर सकता है, और सबस्ट्रिंग को दूसरे में ले जाने वाला पुनर्लेखन नियम स्ट्रिंग्स से जुड़े हिल्बर्ट स्पेस के टेंसर उत्पाद पर एकात्मक ऑपरेशन कर सकता है, इसका तात्पर्य यह है कि वे समुच्चय से वर्णों की संख्या <math>Q</math> को सुरक्षित रखते हैं, मौलिक रूप से इसके समान कोई यह दिखा सकता है कि क्वांटम थ्यू प्रणाली क्वांटम गणना के लिए सार्वभौमिक कम्प्यूटेशनल प्रारूप है, इस अर्थ में कि निष्पादित क्वांटम संचालन एकसमान सर्किट कक्षाओं के अनुरूप हैं, जैसे कि [[बीक्यूपी]] में जब स्ट्रिंग पुनर्लेखन नियमों की समाप्ति की गारंटी होती है, इस प्रकार इस इनपुट के आधार पर उचित आकार वाले बहुपदों के लिए कई चरणों के भीतर या समकक्ष रूप से [[क्वांटम ट्यूरिंग मशीन]] का उपयोग करते हैं।
 ==इतिहास और महत्व==
-सेमी-थ्यू सिस्टम को [[तर्क]] में अतिरिक्त निर्माण जोड़ने के लिए एक कार्यक्रम के हिस्से के रूप में विकसित किया गया था, ताकि प्रस्ताव तर्क जैसे सिस्टम तैयार किए जा सकें, जो सामान्य गणितीय प्रमेयों को [[औपचारिक भाषा]] में व्यक्त करने की अनुमति देगा, और फिर स्वचालित रूप से सिद्ध और सत्यापित किया जाएगा , यांत्रिक फैशन। आशा यह थी कि प्रमेय सिद्ध करने के कार्य को स्ट्रिंग के सेट पर परिभाषित जोड़तोड़ के एक सेट तक कम किया जा सकता है। बाद में यह महसूस किया गया कि सेमी-थ्यू सिस्टम अप्रतिबंधित व्याकरण के लिए आइसोमोर्फिक हैं, जो बदले में [[ट्यूरिंग मशीन]]ों के लिए आइसोमोर्फिक के रूप में जाने जाते हैं। शोध की यह विधि सफल हुई और अब गणितीय और तार्किक प्रमेयों के प्रमाणों को सत्यापित करने के लिए कंप्यूटर का उपयोग किया जा सकता है।
+सेमी-थ्यू प्रणाली को [[तर्क]] में अतिरिक्त निर्माण संयोजित करने के लिए फलन के इस भाग को विकसित किया गया था, जिससे कि प्रस्तावित तर्क में उपयुक्त होने वाली इस प्रकार की प्रणाली को तैयार किए जा सकें, जो सामान्य गणितीय प्रमेयों को [[औपचारिक भाषा]] में व्यक्त करने की अनुमति देती हैं, और फिर स्वचालित रूप यांत्रिकी के आधार पर सिद्ध और सत्यापित की जाती हैं। आशा यह थी कि प्रमेय सिद्ध करने के कार्य को स्ट्रिंग के समुच्चय पर परिभाषित जोड़तोड़ के समुच्चय तक कम किया जा सकता है। इसके पश्चात यह महसूस किया गया कि सेमी-थ्यू प्रणाली अप्रतिबंधित व्याकरण के लिए आइसोमोर्फिक हैं, जो इसके स्थान पर [[ट्यूरिंग मशीन]] के लिए आइसोमोर्फिक के रूप में जाने जाते हैं। यहाँ पर शोध के आधार पर इसके लिए उपयुक्त होने वाली विधियों के सफल होने के प्रयास किए गए और अब गणितीय और तार्किक प्रमेयों के प्रमाणों को सत्यापित करने के लिए कंप्यूटर का उपयोग किया जा सकता है।
-[[अलोंजो चर्च]] के सुझाव पर, एमिल पोस्ट ने 1947 में प्रकाशित एक पेपर में पहली बार थ्यू की एक निश्चित समस्या को अघुलनशील साबित किया, जिसे [[मार्टिन डेविस (गणितज्ञ)]] कहते हैं...शास्त्रीय गणित से किसी समस्या के लिए पहला अघुलनशील प्रमाण - इस मामले में अर्धसमूहों के लिए शब्द समस्या (गणित)।<ref>[[Martin Davis (mathematician)|Martin Davis]] (editor) (1965), ''The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions'', after page 292, [[Raven Press]], New York</ref>
-डेविस का यह भी दावा है कि सबूत ए. ए. मार्कोव द्वारा स्वतंत्र रूप से पेश किया गया था।<ref>[[A. A. Markov]] (1947) [[Doklady Akademii Nauk SSSR (N.S.)]] 55: 583–586</ref>
+[[अलोंजो चर्च]] के सुझाव पर, एमिल पोस्ट ने 1947 में प्रकाशित पेपर में पहली बार थ्यू की निश्चित समस्या को अघुलनशील प्रमाणित किया था, जिसे [[मार्टिन डेविस (गणितज्ञ)]] कहते हैं, इसके आधार पर मौलिक गणित से किसी समस्या के लिए पहला अघुलनशील प्रमाणित हुए थे, इस स्थिति में सेमीसमुच्चयों के लिए शब्द गणितीय समस्या का उपयोग करते हैं।<ref>[[Martin Davis (mathematician)|Martin Davis]] (editor) (1965), ''The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions'', after page 292, [[Raven Press]], New York</ref>
+डेविस का यह भी प्रमाणित किया है कि यह उचित प्रमाण ए. ए. मार्कोव द्वारा स्वतंत्र रूप से प्रस्तुत किया गया था।<ref>[[A. A. Markov]] (1947) [[Doklady Akademii Nauk SSSR (N.S.)]] 55: 583–586</ref>
 == यह भी देखें ==
 * [[ एल प्रणाली ]]
-* [[मार्कोव एल्गोरिथ्म]] - स्ट्रिंग पुनर्लेखन प्रणाली का एक प्रकार
+* [[मार्कोव एल्गोरिथ्म]] - स्ट्रिंग पुनर्लेखन प्रणाली का प्रकार
-* [[एमयू पहेली]]
+* [[एमयू पहेली|एमयू पज़ल]]
 == टिप्पणियाँ ==
 {{reflist}}
 == संदर्भ ==
 === मोनोग्राफ ===
-* रोनाल्ड वी. बुक और फ्रेडरिक ओटो, स्ट्रिंग-रीराइटिंग सिस्टम्स, स्प्रिंगर, 1993, {{isbn|0-387-97965-4}}.
+* रोनाल्ड वी. बुक और फ्रेडरिक ओटो, स्ट्रिंग-रीराइटिंग प्रणाली्स, स्प्रिंगर, 1993, {{isbn|0-387-97965-4}}.
 * मैथियास जैंटज़ेन, कंफ्लुएंट स्ट्रिंग रीराइटिंग, बिरखौसर, 1988, {{isbn|0-387-13715-7}}.
@@ Line 109: / Line 103: @@
 * [[Martin Davis (mathematician)|Martin Davis]], Ron Sigal, Elaine J. Weyuker, ''Computability, complexity, and languages: fundamentals of theoretical computer science'', 2nd ed., Academic Press, 1994, {{isbn|0-12-206382-1}}, chapter 7
 * [[Elaine Rich]], ''Automata, computability and complexity: theory and applications'', Prentice Hall, 2007, {{isbn|0-13-228806-0}}, chapter 23.5.
 === सर्वेक्षण ===
+* सैमसन अब्रामस्की, डोव एम. गब्बे, थॉमस एस. ई. माईबौम (सं.), हैंडबुक ऑफ लॉजिक इन कंप्यूटर साइंस: सिमेंटिक प्रारूपिंग, ऑक्सफोर्ड यूनिवर्सिटी प्रेस, 1995, {{isbn|0-19-853780-8}}.
-<!--TODO: find article names/authors from the reflist above.-->
-* सैमसन अब्रामस्की, डोव एम. गब्बे, थॉमस एस. ई. माईबौम (सं.), हैंडबुक ऑफ लॉजिक इन कंप्यूटर साइंस: सिमेंटिक मॉडलिंग, ऑक्सफोर्ड यूनिवर्सिटी प्रेस, 1995, {{isbn|0-19-853780-8}}.
 * ग्रेज़गोर्ज़ रोज़ेनबर्ग, आर्टो सैलोमा (सं.), औपचारिक भाषाओं की पुस्तिका: शब्द, भाषा, व्याकरण, स्प्रिंगर, 1997, {{isbn|3-540-60420-0}}.
@@ Line 120: / Line 110: @@
 * {{cite journal |last1=Post |first1=Emil |title=थ्यू की एक समस्या की पुनरावर्ती असाध्यता|journal=[[The Journal of Symbolic Logic]] |date=1947 |volume=12 |issue=1 |pages=1–11 |doi=10.2307/2267170 |url=https://projecteuclid.org/euclid.jsl/1183395203 |url-status=dead |jstor=2267170|s2cid=30320278 }}
-<!-- Old formatting, with dead link. [[Emil Post]] (1947) [https://projecteuclid.org/euclid.jsl/1183395203 Recursive Unsolvability of a Problem of Thue], [[The Journal of Symbolic Logic]] 12: 1–11 via [[Project Euclid]]. -->
-{{Formal languages and grammars|state=collapsed}}
-श्रेणी: औपचारिक भाषाएँ
-श्रेणी: गणना का सिद्धांत
-श्रेणी: पुनर्लेखन प्रणालियाँ
-जेए: स्ट्रिंग पुनर्लेखन प्रणाली
-[[Category: Machine Translated Page]]
+[[Category:All accuracy disputes]]
+[[Category:Articles with disputed statements from September 2022]]
+[[Category:Articles with invalid date parameter in template]]
+[[Category:CS1 maint]]
 [[Category:Created On 20/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]

Anonymous

Search

सेमी-थू प्रणाली: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 09:49, 2 August 2023

Contents

परिभाषा

थ्यू सर्वांगसमता

फ़ैक्टर मोनॉइड और मोनॉइड प्रस्तुतियाँ

समस्या शब्द की अनिश्चयता

अन्य धारणाओं के साथ संबंध

इतिहास और महत्व

यह भी देखें

टिप्पणियाँ

संदर्भ

मोनोग्राफ

पाठ्यपुस्तकें

सर्वेक्षण

ऐतिहासिक कागजात

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

सेमी-थू प्रणाली: Difference between revisions

Latest revision as of 09:49, 2 August 2023

परिभाषा

थ्यू सर्वांगसमता

फ़ैक्टर मोनॉइड और मोनॉइड प्रस्तुतियाँ

समस्या शब्द की अनिश्चयता

अन्य धारणाओं के साथ संबंध

इतिहास और महत्व

यह भी देखें

टिप्पणियाँ

संदर्भ

मोनोग्राफ

पाठ्यपुस्तकें

सर्वेक्षण

ऐतिहासिक कागजात

Navigation

Wiki tools

Page tools

Other projects

Hidden categories