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

सैद्धांतिक कंप्यूटर विज्ञान और गणितीय तर्क में एक स्ट्रिंग पुनर्लेखन प्रणाली (एसआरएस), जिसे ऐतिहासिक रूप से सेमी-एक्सल थ्यू सिस्टम कहा जाता है, एक (आमतौर पर परिमित सेट) वर्णमाला (कंप्यूटर विज्ञान) से स्ट्रिंग (कंप्यूटर विज्ञान) पर एक पुनर्लेखन प्रणाली है। एक द्विआधारी संबंध दिया गया है $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}]{}}$ पर एक रिश्ता है $\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 ^{*}$ वर्णमाला पर स्ट्रिंग्स की संख्या स्ट्रिंग संयोजन के बाइनरी ऑपरेशन के साथ मिलकर एक मुक्त मोनॉइड बनाती है (जिसे इस रूप में दर्शाया गया है)। $\cdot$ और प्रतीक को हटाकर गुणनात्मक रूप से लिखा जाता है)। एसआरएस में, कमी संबंध ${\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)

श्रेणी: औपचारिक भाषाएँ श्रेणी: गणना का सिद्धांत श्रेणी: पुनर्लेखन प्रणालियाँ

जेए: स्ट्रिंग पुनर्लेखन प्रणाली