सेमी-थू प्रणाली

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

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

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

परिभाषा

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

• Σ वर्णमाला है, जिसे सामान्यतः सीमित वर्णमाला माना जाता है। इस प्रकार के समुच्चयओं के लिए तत्व $\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)$ रूप की प्रस्तुति होती है, इस प्रकार इसे हमेशा सेमी-थ्यू प्रणाली द्वारा प्रस्तुत किया जा सकता है, संभवतः अनंत वर्णमाला पर इसको प्रस्तुत किया जाता हैं। इस संदर्भ में, समुच्चय $\Sigma$ के जनरेटरों का समुच्चय ${\mathcal {M}}$ कहलाता है, और $R$ संबंधों को परिभाषित करने वाले समुच्चय ${\mathcal {M}}$ को कहा जाता है, हम मोनोइड्स को उनकी प्रस्तुति के आधार पर तुरंत वर्गीकृत कर सकते हैं। जिसे ${\mathcal {M}}$ कहा जाता है

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

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

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

सीधे तौर पर पोस्ट ने ट्यूरिंग मशीन प्लस टेप की स्थिति की सीमित स्ट्रिंग के रूप में एन्कोडिंग तैयार की हैं, जैसे कि इस मशीन की गतिविधियों को इस स्ट्रिंग एन्कोडिंग पर अभिनय करने वाले स्ट्रिंग रीराइट प्रणाली द्वारा किया जा सकता है। इसके आधार पर एन्कोडिंग की वर्णमाला में अक्षरों का समुच्चय होता है, जहाँ पर $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$ का ठोस उदाहरण होना चाहिए, जिसके लिए रुकने की समस्या अनिर्णीत है, अपितु सामान्य रुकने की समस्या की अनिर्णयता के प्रमाण में सम्मिलित होने वाले विभिन्न ट्यूरिंग मशीनों में घटक के रूप में रुकने की समस्या को हल करने वाली काल्पनिक ट्यूरिंग मशीन होती है, इसलिए उनमें से कोई भी मशीन वास्तव में सम्मिलित नहीं हो सकती है, यह सब प्रमाणित करता है कि कुछ ट्यूरिंग मशीन है जिसके लिए निर्णय समस्या अनिर्णीत है। चूंकि, कुछ ट्यूरिंग मशीनों में अनिर्णीत रुकने की समस्या है, इसका अर्थ है कि सार्वभौमिक ट्यूरिंग मशीन के लिए रुकने की समस्या अनिर्णीत है, क्योंकि यह किसी भी ट्यूरिंग मशीन का अनुकरण कर सकती है, और सार्वभौमिक ट्यूरिंग मशीनों के ठोस उदाहरण बनाए गए हैं।

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

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

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

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

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

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

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

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

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

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

यह भी देखें

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

संदर्भ

मोनोग्राफ

• रोनाल्ड वी. बुक और फ्रेडरिक ओटो, स्ट्रिंग-रीराइटिंग प्रणाली्स, स्प्रिंगर, 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)