शब्द समस्या (गणित): Difference between revisions

Revision as of 22:40, 28 March 2023

कम्प्यूटरीकृत गणित में शब्द समस्या यह निर्णय समस्या है कि क्या दो दिए गए भाव पुनर्लेखन पहचान (गणित) के एक समूह के संबंध में समान हैं। प्रोटोटाइपिक उदाहरण समूहों के लिए शब्द समस्या है। किन्तु कई अन्य उदाहरण भी हैं। कम्प्यूटरीकृत सिद्धांत का अच्छा परिणाम यह है कि इस प्रश्न का उत्तर देना कई महत्वपूर्ण स्थितियों में अनिर्णीत समस्या है।^[1]

पृष्ठभूमि और प्रेरणा

कंप्यूटर बीजगणित में अधिकांशतः अभिव्यक्ति ट्री का उपयोग करके गणितीय अभिव्यक्तियों को एन्कोड करना चाहता है। किन्तु अधिकांशतः कई समान अभिव्यक्ति ट्री होते हैं। स्वाभाविक रूप से यह प्रश्न है कि क्या कोई एल्गोरिथम है। जो दो भावों के इनपुट के रूप में दिया गया है। यह निर्णय करता है कि क्या वे एक ही तत्व का प्रतिनिधित्व करते हैं। इस प्रकार के एल्गोरिदम को शब्द समस्या का समाधान कहा जाता है। उदाहरण के लिए, माना कि $x,y,z$ वास्तविक संख्याओं का प्रतिनिधित्व करने वाले प्रतीक हैं। तो इनपुट दिए जाने पर शब्द समस्या का एक प्रासंगिक समाधान $(x\cdot y)/z\mathrel {\overset {?}{=}} (x/z)\cdot y$ होगा और EQUAL उत्पाद है। इसी प्रकार NOT_EQUAL से $(x\cdot y)/z\mathrel {\overset {?}{=}} (x/x)\cdot y$ . उत्पादन करते हैं।

शब्द समस्या का सबसे सीधा एवं सरल समाधान सामान्य प्रमेय और एल्गोरिथ्म का रूप लेता है। जो प्रत्येक तत्व को भावों के समतुल्य वर्ग में नियम फॉर्म के रूप में ज्ञात एकल एन्कोडिंग में मैप करता है। शब्द समस्या तब इन सामान्य रूपों की तुलना वाक्यगत समानता करके हल की जाती है।^[1] उदाहरण के लिए कोई यह सुनिश्चित कर सकता है कि $x\cdot y\cdot z^{-1}$ का सामान्य रूप है। $(x\cdot y)/z$ , $(x/z)\cdot y$ , और $(y/z)\cdot x$ और उन भावों को उस रूप में फिर से लिखने के लिए एक परिवर्तन प्रणाली तैयार करें। इस प्रक्रिया में यह सिद्ध करते हुए कि सभी समान भावों को उसी सामान्य रूप में फिर से लिखा जाएगा।^[2] किन्तु शब्द समस्या के सभी समाधान सामान्य रूप प्रमेय का उपयोग नहीं करते हैं। ऐसे बीजीय गुण हैं, जो अप्रत्यक्ष रूप से एल्गोरिथम के प्रमाण का संकेत देते हैं।^[1]

जबकि शब्द समस्या पूछती है कि क्या स्थिरांक (गणित) वाले दो शब्द समान हैं। शब्द समस्या का एक उचित विस्तार, जिसे एकीकरण (कंप्यूटर विज्ञान) के रूप में जाना जाता है, पूछता है कि क्या दो शब्द $t_{1},t_{2}$ वेरिएबल (गणित) वाले ऐसे उदाहरण हैं। जो बराबर हैं या दूसरे शब्दों में समीकरण $t_{1}=t_{2}$ हैं। एक सामान्य उदाहरण के रूप में $2+3{\stackrel {?}{=}}8+(-3)$ पूर्णांक बीजगणितीय गुणों में शब्द समस्या है। पूर्णांक समूह ℤ है।

जबकि $2+x{\stackrel {?}{=}}8+(-x)$ एक ही समूह में एकीकरण की समस्या है। चूंकि पूर्व नियम ℤ में बराबर होती हैं। बाद की समस्या में प्रतिस्थापन (तर्क) $\{x\mapsto 3\}$ एक समाधान के रूप में होता है।

इतिहास

शब्द समस्या के सबसे गहन अध्ययन वाले स्थितियों में से एक सेमीग्रुप और समूह (गणित) के सिद्धांत में है। नोविकोव-बूने सिद्धांत से संबंधित कागज की एक समयरेखा इस प्रकार है:^[3]^[4]

1910: एक्सल थू ने पेड़ जैसी संरचनाओं पर शब्द पुनर्लेखन की एक सामान्य समस्या पेश की। वह कहते हैं, "सबसे सामान्य मामले में इस समस्या का समाधान शायद असाध्य कठिनाइयों से जुड़ा हो सकता है"।

1911: मैक्स डेह्न ने अंतिम रूप से प्रस्तुत समूहों के लिए शब्द समस्या प्रस्तुत की।

1912: डेन के एल्गोरिथ्म को प्रस्तुत करता है, और यह साबित करता है कि यह 2 से अधिक या उसके बराबर जीनस के बंद उन्मुख द्वि-आयामी कई गुना के मौलिक समूहों के लिए शब्द समस्या को हल करता है। बाद के लेखकों ने समूह सैद्धांतिक निर्णय समस्याओं की एक विस्तृत श्रृंखला के लिए इसे काफी विस्तारित किया है।

1914: एक्सल थू ने सूक्ष्म रूप से प्रस्तुत अर्धसमूहों के लिए शब्द समस्या प्रस्तुत की।

1930 - 1938: चर्च-ट्यूरिंग थीसिस उभरती है, संगणनीयता और अनिर्वचनीयता की औपचारिक धारणाओं को परिभाषित करती है।

1947: एमिल पोस्ट और एंड्री मार्कोव जूनियर स्वतंत्र रूप से अघुलनशील शब्द समस्या के साथ सूक्ष्म रूप से प्रस्तुत अर्धसमूहों का निर्माण करते हैं। पोस्ट का निर्माण ट्यूरिंग मशीनों पर किया गया है जबकि मार्कोव पोस्ट के सामान्य सिस्टम का उपयोग करता है।

1950: पोस्ट के निर्माण को आगे बढ़ाकर एलन ट्यूरिंग दिखाते हैं कि रद्द किए गए सेमीग्रुप्स के लिए शब्द समस्या अघुलनशील है। सबूत का पालन करना मुश्किल है लेकिन समूहों के लिए शब्द समस्या में एक महत्वपूर्ण मोड़ है।

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

1954 - 1957: पोस्ट के सेमीग्रुप निर्माण का उपयोग करते हुए विलियम बून स्वतंत्र रूप से समूहों के लिए शब्द समस्या को हल करने योग्य नहीं दिखाते हैं।

1957 - 1958: जॉन ब्रिटन ने एक और प्रमाण दिया कि समूहों के लिए शब्द समस्या अघुलनशील है, जो ट्यूरिंग के निरस्तीकरण सेमिग्रुप परिणाम और ब्रिटन के कुछ पहले के काम पर आधारित है। [20] ब्रिटन के लेम्मा का एक प्रारंभिक संस्करण प्रकट होता है।

1958 - 1959: बूने ने अपने निर्माण का एक सरलीकृत संस्करण प्रकाशित किया।

1961: ग्राहम हिगमैन, हिगमैन के एम्बेडिंग प्रमेय के साथ अंतिम रूप से प्रस्तुत समूहों के उपसमूहों की विशेषता बताता है। समूह सिद्धांत के साथ पुनरावर्तन सिद्धांत को अप्रत्याशित तरीके से जोड़ता है और शब्द समस्या की असम्बद्धता का एक बहुत अलग प्रमाण देता है।

1961 - 1963: ब्रिटन ने बूने के 1959 के प्रमाण का एक बहुत ही सरलीकृत संस्करण प्रस्तुत किया कि समूहों के लिए शब्द समस्या हल नहीं हो सकती है। यह एक समूह-सैद्धांतिक दृष्टिकोण का उपयोग करता है, विशेष रूप से ब्रिटन की लेम्मा में। इस प्रमाण का उपयोग स्नातक पाठ्यक्रम में किया गया है, हालांकि अधिक आधुनिक और संघनित प्रमाण उपस्थित हैं।

1977: गेन्नेडी माकानिन ने साबित किया कि मुक्त मोनोइड्स पर समीकरणों का अस्तित्व सिद्धांत हल करने योग्य है।

सेमी-थ्यू प्रणाली के लिए शब्द समस्या

स्ट्रिंग पुनर्लेखन प्रणाली (सेमी-थ्यू प्रणाली या सेमीग्रुप) के लिए एक्सेसिबिलिटी समस्या निम्नानुसार बताई जा सकती है: एक सेमी-थ्यू प्रणाली $T:=(\Sigma ,R)$ दिया गया और दो शब्द (तार) $u,v\in \Sigma ^{*}$ $u$ में बदलकर $v$ से $R$ नियम लागू करें। ध्यान दें कि यहाँ पुनर्लेखन एक ओर है। शब्द समस्या सममित पुनर्लेखन संबंधों, अर्थात् थ्यू प्रणाली के लिए अभिगम्यता समस्या है।^[5]

अभिगम्यता और शब्द समस्याएँ अनिर्णीत समस्याएँ हैं, अर्थात इस समस्या को हल करने के लिए कोई सामान्य एल्गोरिद्म नहीं है।^[6] यह तब भी होता है, जब हम प्रणाली को सीमित प्रस्तुतियों तक सीमित करते हैं, अर्थात् प्रतीकों का एक सीमित समूह और उन प्रतीकों पर संबंधों का एक सीमित समूह^[5]यहां तक कि निचले शब्दों तक सीमित शब्द समस्या भी निश्चित रूप से प्रस्तुत अर्धसमूहों के लिए निर्णायक नहीं है।^[7]^[8]

समूहों के लिए शब्द समस्या

$\langle S\mid {\mathcal {R}}\rangle$ समूह G के लिए प्रस्तुति दी। शब्द समस्या निर्णय लेने की एल्गोरिथम समस्या है। जो S में इनपुट दो शब्दों के रूप में दी गई है। क्या वे G के समान तत्व का प्रतिनिधित्व करते हैं। शब्द समस्या 1911 में मैक्स डेहन द्वारा प्रस्तावित समूहों के लिए तीन एल्गोरिथम समस्याओं में से एक है। यह 1955 में पीटर नोविकोव द्वारा दिखाया गया था कि एक सूक्ष्म रूप से प्रस्तुत समूह G उपस्थित है। जैसे कि G के लिए शब्द समस्या अनिर्णीत समस्या है।^[9]

कॉम्बिनेटरियल कैलकुलस और लैम्ब्डा कैलकुलस में वर्ड प्रॉब्लम =

सबसे प्रारम्भिकप्रमाणों में से एक है कि एक शब्द समस्या अनिर्णीत है। जो संयोजन तर्क के लिए थी। कॉम्बिनेटर के दो तार कब बराबर होते हैं? क्योंकि कॉम्बिनेटर सभी संभव ट्यूरिंग मशीनों को एनकोड करते हैं और दो ट्यूरिंग मशीनों की समानता अनिर्णीत है। यह इस प्रकार है कि कॉम्बिनेटर के दो स्ट्रिंग्स की समानता अनिर्णीत है। 1936 में अलोंजो चर्च ने इसका अवलोकन किया।^[10]

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

सार पुनर्लेखन प्रणाली के लिए शब्द समस्या

शब्द समस्या को हल करना: यदि तय करना

x{\stackrel {*}{\leftrightarrow }}y

आमतौर पर अनुमानी खोज की आवश्यकता होती है (red, green), निर्णय लेते समय

x\downarrow =y\downarrow

सीधा है (grey).

अमूर्त पुनर्लेखन प्रणाली (ARS) के लिए शब्द समस्या काफी संक्षिप्त है: दी गई वस्तुएँ x और y के अंतर्गत वे समतुल्य हैं ${\stackrel {*}{\leftrightarrow }}$ ?^[7] ARS के लिए शब्द समस्या सामान्य रूप से अनिर्णीत समस्या है। हालाँकि, विशिष्ट मामले में शब्द समस्या के लिए एक संगणनीय कार्य समाधान है जहाँ प्रत्येक वस्तु एक विशिष्ट सामान्य रूप में चरणों की एक सीमित संख्या में घट जाती है (अर्थात प्रणाली अभिसारी है): दो वस्तुएँ समतुल्य हैं ${\stackrel {*}{\leftrightarrow }}$ अगर और केवल अगर वे एक ही सामान्य रूप में कम हो जाते हैं।^[11]

Knuth-Bendix पूर्णता एल्गोरिथम का उपयोग समीकरणों के एक समूह को अभिसरण शब्द पुनर्लेखन प्रणाली में बदलने के लिए किया जा सकता है।

सार्वभौमिक बीजगणित में शब्द समस्या

सार्वभौमिक बीजगणित में एक बीजीय संरचनाओं का अध्ययन करता है जिसमें एक जनरेटिंग समूह A, परिमित arity (आमतौर पर बाइनरी ऑपरेशंस) के A पर संचालन का एक संग्रह होता है, और पहचान का एक परिमित समूह होता है जिसे इन ऑपरेशनों को पूरा करना चाहिए। एक बीजगणित के लिए शब्द समस्या तब निर्धारित करने के लिए है, दो भाव (शब्द) दिए गए हैं जिनमें जनरेटर और संचालन शामिल हैं, चाहे वे बीजगणित मॉड्यूलो के समान तत्व का प्रतिनिधित्व करते हों। समूहों और अर्धसमूहों के लिए शब्द समस्याओं को बीजगणित के लिए शब्द समस्याओं के रूप में अभिव्यक्त किया जा सकता है।^[1]

मुक्त Heyting बीजगणित पर शब्द समस्या कठिन है।^[12] एकमात्र ज्ञात परिणाम यह है कि एक जनरेटर पर मुफ्त हेटिंग बीजगणित अनंत है, और यह कि एक जनरेटर पर मुक्त पूर्ण हेटिंग बीजगणित उपस्थित है (और मुक्त हेटिंग बीजगणित की तुलना में एक और तत्व है)।

मुक्त जाली के लिए शब्द समस्या

Example computation of x∧z ~ x∧z∧(x∨y)

		x∧z∧(x∨y)	≤_~	x∧z
by 5.	since	x∧z	≤_~	x∧z
by 1.	since	x∧z	=	x∧z

		x∧z	≤_~	x∧z∧(x∨y)
by 7.	since	x∧z	≤_~	x∧z	and			x∧z	≤_~	x∨y
by 1.	since	x∧z	=	x∧z		by 6.	since	x∧z	≤_~	x
						by 5.	since	x	≤_~	x
						by 1.	since	x	=	x

मुक्त जाली और अधिक आम तौर पर मुक्त जाली (आदेश) पर शब्द समस्या का एक निर्णायक समाधान है। बाउंडेड लैटिस दो बाइनरी ऑपरेशंस ∨ और ∧ और दो स्थिरांक (शून्य संचालन) 0 और 1 के साथ बीजगणितीय संरचनाएं हैं। सभी अच्छी प्रकार से गठित शब्द (लॉजिक) का समूह जो दिए गए समूह से तत्वों पर इन ऑपरेशंस का उपयोग करके तैयार किया जा सकता है जेनरेटर एक्स को 'डब्ल्यू' (एक्स) कहा जाएगा। शब्दों के इस समूह में कई अभिव्यक्तियां होती हैं जो प्रत्येक जाली में समान मूल्यों को दर्शाती हैं। उदाहरण के लिए, यदि a, X का कोई अवयव है, तो a ∨ 1 = 1 और a∧ 1 =a। मुक्त परिबद्ध जाली के लिए शब्द समस्या यह निर्धारित करने की समस्या है कि 'डब्ल्यू' (एक्स) के इन तत्वों में से कौन सा तत्व मुक्त बाध्य जाली एफएक्स में समान तत्व को दर्शाता है, और इसलिए हर बाध्य जाली में।

शाब्दिक समस्या का समाधान इस प्रकार किया जा सकता है। एक रिश्ता ≤_~ W(X) पर w ≤ समूह करके गणितीय आगमन को परिभाषित किया जा सकता है_~ v यदि और केवल यदि निम्न में से कोई एक धारण करता है:

w = v (इसे उस स्थिति तक सीमित रखा जा सकता है जहां w और v X के अवयव हैं),
डब्ल्यू = 0,
वी = 1,
डब्ल्यू = डब्ल्यू₁ ∨ में₂ और दोनों डब्ल्यू₁ ≤_~ वी और डब्ल्यू₂ ≤_~ वी पकड़,
डब्ल्यू = डब्ल्यू₁ ∧ में₂ और या तो डब्ल्यू₁ ≤_~ वी या डब्ल्यू₂ ≤_~ वी रखती है,
वी = वी₁ ∨ वि₂ और या तो डब्ल्यू ≤_~ v₁ या डब्ल्यू ≤_~ v₂ रखता है,
वी = वी₁ ∧ वि₂ और दोनों डब्ल्यू ≤_~ v₁ और डब्ल्यू ≤_~ v₂ पकड़ना।

यह एक पूर्व आदेश ≤ परिभाषित करता है_~ W(X) पर, इसलिए एक तुल्यता संबंध को w ~ v द्वारा परिभाषित किया जा सकता है जब w ≤_~ वी और वी ≤_~ डब्ल्यू तब कोई यह दिखा सकता है कि आंशिक रूप से आदेशित भागफल समुच्चय 'W'(X)/~ मुक्त परिबद्ध जालक FX है।^[13]^[14] W(X)/~ के समतुल्य वर्ग सभी शब्दों w और v के साथ w ≤ के समुच्चय हैं_~ वी और वी ≤_~ डब्ल्यू 'W'(X) में दो सुगठित शब्द v और w प्रत्येक बंधे हुए जाली में समान मान को दर्शाते हैं यदि और केवल यदि w ≤_~ वी और वी ≤_~ डब्ल्यू; उपरोक्त आगमनात्मक परिभाषा का उपयोग करके बाद की स्थितियों को प्रभावी ढंग से तय किया जा सकता है। तालिका यह दिखाने के लिए एक उदाहरण संगणना दिखाती है कि x∧z और x∧z∧(x∨y) शब्द प्रत्येक बंधे हुए जाली में समान मान को दर्शाते हैं। जाली के मामले जो बंधे नहीं हैं, उसी प्रकार से व्यवहार किया जाता है, ऊपर के निर्माण में नियम 2 और 3 को छोड़कर ≤_~.

== उदाहरण: मुक्त समूह == में शब्द समस्या तय करने के लिए एक शब्द पुनर्लेखन प्रणाली

ब्लासियस और बर्कर्ट

^[15]

समूहों के लिए एक स्वयंसिद्ध समूह पर नुथ-बेंडिक्स एल्गोरिथम प्रदर्शित करें। एल्गोरिथ्म एक संगम (सार पुनर्लेखन) और सार पुनर्लेखन प्रणाली # समाप्ति और अभिसरण पुनर्लेखन प्रणाली # शब्द पुनर्लेखन प्रणाली उत्पन्न करता है जो प्रत्येक शब्द को एक अद्वितीय सामान्य रूप (सार पुनर्लेखन) में बदल देता है।^[16] पुनर्लेखन नियमों को अस्पष्ट रूप से क्रमांकित किया गया है क्योंकि कुछ नियम बेमानी हो गए थे और एल्गोरिथम रन के दौरान हटा दिए गए थे। दो शब्दों की समानता स्वयंसिद्धों से होती है यदि और केवल यदि दोनों शब्दों को शाब्दिक रूप से समान सामान्य रूप में रूपांतरित किया जाता है। उदाहरण के लिए, शर्तें

((a^{-1}\cdot a)\cdot (b\cdot b^{-1}))^{-1}{\stackrel {R2}{\rightsquigarrow }}(1\cdot (b\cdot b^{-1}))^{-1}{\stackrel {R13}{\rightsquigarrow }}(1\cdot 1)^{-1}{\stackrel {R1}{\rightsquigarrow }}1^{-1}{\stackrel {R8}{\rightsquigarrow }}1

, और

b\cdot ((a\cdot b)^{-1}\cdot a){\stackrel {R17}{\rightsquigarrow }}b\cdot ((b^{-1}\cdot a^{-1})\cdot a){\stackrel {R3}{\rightsquigarrow }}b\cdot (b^{-1}\cdot (a^{-1}\cdot a)){\stackrel {R2}{\rightsquigarrow }}b\cdot (b^{-1}\cdot 1){\stackrel {R11}{\rightsquigarrow }}b\cdot b^{-1}{\stackrel {R13}{\rightsquigarrow }}1

समान सामान्य रूप साझा करें, अर्थात। $1$ ; इसलिए दोनों शब्द हर समूह में समान हैं। एक अन्य उदाहरण के रूप में, शब्द $1\cdot (a\cdot b)$ और $b\cdot (1\cdot a)$ सामान्य रूप है $a\cdot b$ और $b\cdot a$ , क्रमश। चूँकि सामान्य रूप वस्तुतः भिन्न होते हैं, मूल शब्द प्रत्येक समूह में समान नहीं हो सकते। वास्तव में, वे आम तौर पर एबेलियन समूह | गैर-एबेलियन समूहों में भिन्न होते हैं।

Group axioms used in Knuth–Bendix completion
A1	$1\cdot x$	$=x$
A2	$x^{-1}\cdot x$	$=1$
A3	$(x\cdot y)\cdot z$	$=x\cdot (y\cdot z)$

Term rewrite system obtained from Knuth–Bendix completion
R1	$1\cdot x$	$\rightsquigarrow x$
R2	$x^{-1}\cdot x$	$\rightsquigarrow 1$
R3	$(x\cdot y)\cdot z$	$\rightsquigarrow x\cdot (y\cdot z)$
R4	$x^{-1}\cdot (x\cdot y)$	$\rightsquigarrow y$
R8	$1^{-1}$	$\rightsquigarrow 1$
R11	$x\cdot 1$	$\rightsquigarrow x$
R12	$(x^{-1})^{-1}$	$\rightsquigarrow x$
R13	$x\cdot x^{-1}$	$\rightsquigarrow 1$
R14	$x\cdot (x^{-1}\cdot y)$	$\rightsquigarrow y$
R17	$(x\cdot y)^{-1}$	$\rightsquigarrow y^{-1}\cdot x^{-1}$

यह भी देखें

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 Evans, Trevor (1978). "शब्द की समस्याएं". Bulletin of the American Mathematical Society. 84 (5): 790. doi:10.1090/S0002-9904-1978-14516-9.
↑ Cohen, Joel S. (2002). Computer algebra and symbolic computation: elementary algorithms. Natick, Mass.: A K Peters. pp. 90–92. ISBN 1568811586.
↑ Miller, Charles F. (2014). Downey, Rod (ed.). "शब्द समस्याओं के लिए ट्यूरिंग मशीन" (PDF). Turing's Legacy: 330. doi:10.1017/CBO9781107338579.010. hdl:11343/51723. ISBN 9781107338579. Retrieved 6 December 2021.
↑ Stillwell, John (1982). "समूहों के लिए शब्द समस्या और समरूपता समस्या". Bulletin of the American Mathematical Society. 6 (1): 33–56. doi:10.1090/S0273-0979-1982-14963-1.
↑ ^5.0 ^5.1 Matiyasevich, Yuri; Sénizergues, Géraud (January 2005). "कुछ नियमों के साथ अर्ध-थू सिस्टम के लिए निर्णय समस्याएँ". Theoretical Computer Science. 330 (1): 145–169. doi:10.1016/j.tcs.2004.09.016.
↑ Davis, Martin (1978). "What is a Computation?" (PDF). Mathematics Today Twelve Informal Essays: 257–259. doi:10.1007/978-1-4613-9435-8_10. ISBN 978-1-4613-9437-2. Retrieved 5 December 2021.
↑ ^7.0 ^7.1 Baader, Franz; Nipkow, Tobias (5 August 1999). टर्म पुनर्लेखन और वह सब (in English). Cambridge University Press. pp. 59–60. ISBN 978-0-521-77920-3.
↑
*Matiyasevich, Yu. V. (1967). "Простые примеры неразрешимых ассоциативных исчислений" [Simple examples of undecidable associative calculi]. Doklady Akademii Nauk SSSR (in Russian). 173 (6): 1264–1266. ISSN 0869-5652.{{cite journal}}: CS1 maint: unrecognized language (link)
- Matiyasevich, Yu. V. (1967). "Simple examples of undecidable associative calculi". Soviet Mathematics. 8 (2): 555–557. ISSN 0197-6788.
↑ Novikov, P. S. (1955). "समूह सिद्धांत में शब्द समस्या की एल्गोरिदमिक असम्बद्धता पर". Trudy Mat. Inst. Steklov (in русский). 44: 1–143.
↑ Statman, Rick (2000). "कॉम्बिनेटर्स के लिए वर्ड प्रॉब्लम पर". Rewriting Techniques and Applications. Lecture Notes in Computer Science. 1833: 203–213. doi:10.1007/10721975_14. ISBN 978-3-540-67778-9.
↑ Beke, Tibor (May 2011). "Categorification, term rewriting and the Knuth–Bendix procedure". Journal of Pure and Applied Algebra. 215 (5): 730. doi:10.1016/j.jpaa.2010.06.019.
↑ Peter T. Johnstone, Stone Spaces, (1982) Cambridge University Press, Cambridge, ISBN 0-521-23893-5. (See chapter 1, paragraph 4.11)
↑ Whitman, Philip M. (January 1941). "मुक्त जाली". The Annals of Mathematics. 42 (1): 325–329. doi:10.2307/1969001. JSTOR 1969001.
↑ Whitman, Philip M. (1942). "मुक्त जाली II". Annals of Mathematics. 43 (1): 104–115. doi:10.2307/1968883. JSTOR 1968883.
↑ K. H. Bläsius and H.-J. Bürckert, ed. (1992). कटौती प्रणाली. Oldenbourg. p. 291.; here: p.126, 134
↑ Apply rules in any order to a term, as long as possible; the result doesn't depend on the order; it is the term's normal form.

[Evans-1] 1.0 ^1.1 ^1.2 ^1.3 Evans, Trevor (1978). "शब्द की समस्याएं". Bulletin of the American Mathematical Society. 84 (5): 790. doi:10.1090/S0002-9904-1978-14516-9.

[2] Cohen, Joel S. (2002). Computer algebra and symbolic computation: elementary algorithms. Natick, Mass.: A K Peters. pp. 90–92. ISBN 1568811586.

[Miller-3] Miller, Charles F. (2014). Downey, Rod (ed.). "शब्द समस्याओं के लिए ट्यूरिंग मशीन" (PDF). Turing's Legacy: 330. doi:10.1017/CBO9781107338579.010. hdl:11343/51723. ISBN 9781107338579. Retrieved 6 December 2021.

[4] Stillwell, John (1982). "समूहों के लिए शब्द समस्या और समरूपता समस्या". Bulletin of the American Mathematical Society. 6 (1): 33–56. doi:10.1090/S0273-0979-1982-14963-1.

[Matiyasevich-5] 5.0 ^5.1 Matiyasevich, Yuri; Sénizergues, Géraud (January 2005). "कुछ नियमों के साथ अर्ध-थू सिस्टम के लिए निर्णय समस्याएँ". Theoretical Computer Science. 330 (1): 145–169. doi:10.1016/j.tcs.2004.09.016.

[6] Davis, Martin (1978). "What is a Computation?" (PDF). Mathematics Today Twelve Informal Essays: 257–259. doi:10.1007/978-1-4613-9435-8_10. ISBN 978-1-4613-9437-2. Retrieved 5 December 2021.

[Nipkow-7] 7.0 ^7.1 Baader, Franz; Nipkow, Tobias (5 August 1999). टर्म पुनर्लेखन और वह सब (in English). Cambridge University Press. pp. 59–60. ISBN 978-0-521-77920-3.

[8] *Matiyasevich, Yu. V. (1967). "Простые примеры неразрешимых ассоциативных исчислений" [Simple examples of undecidable associative calculi]. Doklady Akademii Nauk SSSR (in Russian). 173 (6): 1264–1266. ISSN 0869-5652.{{cite journal}}: CS1 maint: unrecognized language (link)
Matiyasevich, Yu. V. (1967). "Simple examples of undecidable associative calculi". Soviet Mathematics. 8 (2): 555–557. ISSN 0197-6788.

[9] Matiyasevich, Yu. V. (1967). "Simple examples of undecidable associative calculi". Soviet Mathematics. 8 (2): 555–557. ISSN 0197-6788.

[9] Novikov, P. S. (1955). "समूह सिद्धांत में शब्द समस्या की एल्गोरिदमिक असम्बद्धता पर". Trudy Mat. Inst. Steklov (in русский). 44: 1–143.

[10] Statman, Rick (2000). "कॉम्बिनेटर्स के लिए वर्ड प्रॉब्लम पर". Rewriting Techniques and Applications. Lecture Notes in Computer Science. 1833: 203–213. doi:10.1007/10721975_14. ISBN 978-3-540-67778-9.

[11] Beke, Tibor (May 2011). "Categorification, term rewriting and the Knuth–Bendix procedure". Journal of Pure and Applied Algebra. 215 (5): 730. doi:10.1016/j.jpaa.2010.06.019.

[12] Peter T. Johnstone, Stone Spaces, (1982) Cambridge University Press, Cambridge, ISBN 0-521-23893-5. (See chapter 1, paragraph 4.11)

[13] Whitman, Philip M. (January 1941). "मुक्त जाली". The Annals of Mathematics. 42 (1): 325–329. doi:10.2307/1969001. JSTOR 1969001.

[14] Whitman, Philip M. (1942). "मुक्त जाली II". Annals of Mathematics. 43 (1): 104–115. doi:10.2307/1968883. JSTOR 1968883.

[15] K. H. Bläsius and H.-J. Bürckert, ed. (1992). कटौती प्रणाली. Oldenbourg. p. 291.; here: p.126, 134

[16] Apply rules in any order to a term, as long as possible; the result doesn't depend on the order; it is the term's normal form.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

@@ Line 18: / Line 18: @@
 शब्द समस्या के सबसे गहन अध्ययन वाले स्थितियों में से एक [[semigroup|सेमीग्रुप]] और [[समूह (गणित)]] के सिद्धांत में है। [[नोविकोव-बूने सिद्धांत]] से संबंधित कागज की एक समयरेखा इस प्रकार है:<ref name=Miller>{{cite journal |last1=Miller |first1=Charles F. |editor1-first=Rod |editor1-last=Downey |title=शब्द समस्याओं के लिए ट्यूरिंग मशीन|journal=Turing's Legacy |date=2014 |pages=330 |doi=10.1017/CBO9781107338579.010 |hdl=11343/51723 |isbn=9781107338579 |url=http://minerva-access.unimelb.edu.au/bitstream/11343/51723/1/cfm-lnl42-turings-legacy-pp329-385-2014.pdf |access-date=6 December 2021}}</ref><ref>{{cite journal |last1=Stillwell |first1=John |title=समूहों के लिए शब्द समस्या और समरूपता समस्या|journal=Bulletin of the American Mathematical Society |date=1982 |volume=6 |issue=1 |pages=33–56 |doi=10.1090/S0273-0979-1982-14963-1|doi-access=free }}</ref>
-* {{Timeline-event |date={{आरंभ तिथि|1910}}|event=[[एक्सल थू]] पेड़ जैसी संरचनाओं पर शब्द पुनर्लेखन की एक सामान्य समस्या है। वह कहते हैं, "सबसे सामान्य मामले में इस समस्या का समाधान शायद असाध्य कठिनाइयों से जुड़ा हो सकता है".<ref name=Muller>{{cite arXiv  |last1=Müller-Stach |first1=Stefan |title=Max Dehn, Axel Thue, and the Undecidable |date=12 September 2021 |eprint=1703.09750 |page=13|class=math.HO }}</ref><ref>{{cite journal |last1=Steinby |first1=Magnus |last2=Thomas |first2=Wolfgang |title=1910 में ट्रीज़ एंड टर्म रीराइटिंग: एक्सल थू द्वारा एक पेपर पर |journal=बुलेटिन ऑफ़ द यूरोपियन एसोसिएशन फॉर थ्योरेटिकल कंप्यूटर साइंस|volume=72|pages=256–269 |date=2000|mr=1798015|citeseerx=10.1.1.32.8993 |language=English}}</ref>}}
+* 1910: एक्सल थू ने पेड़ जैसी संरचनाओं पर शब्द पुनर्लेखन की एक सामान्य समस्या पेश की। वह कहते हैं, "सबसे सामान्य मामले में इस समस्या का समाधान शायद असाध्य कठिनाइयों से जुड़ा हो सकता है"।
-* {{Timeline-event |date={{आरम्भ तिथि|1911}}|event=[[मैक्स देह]] सूक्ष्म रूप से प्रस्तुत किए गए समूहों के लिए शब्द समस्या प्रस्तुत करता है.<ref>{{cite journal  | last1=Dehn | first1=Max | author1-link=Max Dehn | title=Über unendliche diskontinuierliche Gruppen | doi=10.1007/BF01456932 | mr=1511645  | year=1911 | journal=[[Mathematische Annalen]] | issn=0025-5831 | volume=71 | issue=1 | pages=116–144| s2cid=123478582 |url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0071&DMDID=DMDLOG_0013&L=1}}</ref>}}
-* {{Timeline-event |date={{आरम्भ तिथि|1912}}|event=Dehn प्रस्तुत करता है [[Dehn का एल्गोरिथ्म]], और यह साबित करता है कि यह 2 से अधिक या उसके बराबर जीनस के बंद ओरिएंटेबल द्वि-आयामी कई गुना [[मूल समूह]] के लिए शब्द समस्या को हल करता है।.<ref>{{cite journal | last1=Dehn | first1=Max | author1-link=Max Dehn | title=Transformation der Kurven auf zweiseitigen Flächen | doi=10.1007/BF01456725 | mr=1511705  | year=1912 | journal=[[Mathematische Annalen]] | issn=0025-5831 | volume=72 | issue=3 | pages=413–421| s2cid=122988176 |url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0072&DMDID=DMDLOG_0039&L=1}}</ref> बाद के लेखकों ने इसे समूह सिद्धांत [[निर्णय समस्या]] की एक विस्तृत श्रृंखला तक विस्तारित किया है।<ref>{{cite journal|last=Greendlinger|first=Martin|date=June 1959|title=Dehn's algorithm for the word problem|journal=Communications on Pure and Applied Mathematics|volume=13|issue=1|pages=67–83|doi=10.1002/cpa.3160130108}}</ref><ref>{{cite journal|last=Lyndon|first=Roger C.|author-link=Roger Lyndon|date=September 1966|title=On Dehn's algorithm|journal=Mathematische Annalen|volume=166|issue=3|pages=208–228|doi=10.1007/BF01361168|hdl=2027.42/46211|s2cid=36469569|url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002296799&L=1|hdl-access=free}}</ref><ref>{{cite journal|author-link1=Paul Schupp|last1=Schupp|first1=Paul E.|date=June 1968|title=On Dehn's algorithm and the conjugacy problem|journal=Mathematische Annalen|volume=178|issue=2|pages=119–130|doi=10.1007/BF01350654|s2cid=120429853|url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002300036&L=1}}</ref>}}
-* {{Timeline-event |date={{आरम्भ तिथि1914}}|event=[[एक्सल थू]] बारीकी से प्रस्तुत अर्धसमूहों के लिए शब्द समस्या प्रस्तुत करता है.<ref>{{cite arXiv |last1=Power |first1=James F. |title=Thue's 1914 paper: a translation |date=27 August 2013 |class=cs.FL |eprint=1308.5858}}</ref>}}
-* {{Timeline-event |date={{आरम्भ तिथि|1930}}|end_date={{अन्तिम तिथि|1938}}|event=[[चर्च-ट्यूरिंग थीसिस]] उभरती है, संगणनीयता और अनिर्णीतता की औपचारिक धारणाओं को परिभाषित करती है।<ref>देखें [[चर्च का इतिहास-ट्यूरिंग थीसिस]]। तारीखें [[प्रिंसिपिया मैथेमेटिका और संबंधित प्रणालियों के औपचारिक रूप से अनिर्णायक प्रस्तावों पर]] और [[ऑर्डिनल्स पर आधारित तर्क की प्रणाली]] पर आधारित हैं।.</ref>}}
-* {{Timeline-event |date={{आरम्भ तिथि|1947}}|event=[[एमिल पोस्ट]] और [[एंड्री मार्कोव जूनियर]] स्वतंत्र रूप से अघुलनशील शब्द समस्या के साथ सूक्ष्म रूप से प्रस्तुत अर्धसमूहों का निर्माण करते हैं।<ref>{{cite journal |last1=Post |first1=Emil L. |title=Recursive Unsolvability of a problem of Thue |journal=Journal of Symbolic Logic |date=March 1947 |volume=12 |issue=1 |pages=1–11 |doi=10.2307/2267170 |jstor=2267170 |s2cid=30320278 |url=https://www.wolframscience.com/prizes/tm23/images/Post2.pdf |access-date=6 December 2021}}</ref><ref>{{cite journal |last1=Mostowski |first1=Andrzej |title=ए मार्कोव। नेवोज़्मोइनोस्ट 'नेकोटोरिह एल्गोरिटमोव वी टेओरी एसोसिएटिवनिह सिस्टम (सहयोगी प्रणालियों के सिद्धांत में कुछ एल्गोरिदम की असंभवता)। डोकलाडी अकादमी नौका एसएसएसआर, खंड। 77 (1951), पीपी. 19-20. |journal=Journal of Symbolic Logic |date=September 1951 |volume=16 |issue=3 |pages=215 |doi=10.2307/2266407|jstor=2266407 }}</ref> पोस्ट का निर्माण ट्यूरिंग मशीनों पर बनाया गया है जबकि मार्कोव पोस्ट के सामान्य सिस्टम का उपयोग करता है।<ref name=Miller/>}}
-* {{Timeline-event |date={{आरम्भ तिथि|1950}}|event=[[एलन ट्यूरिंग]] दिखाता है कि रद्दीकरण अर्धसमूहों के लिए शब्द समस्या हल नहीं हो सकती है,<ref>{{cite journal |last1=Turing |first1=A. M. |title=रद्दीकरण के साथ अर्ध-समूहों में शब्द समस्या |journal=The Annals of Mathematics |date=September 1950 |volume=52 |issue=2 |pages=491–505 |doi=10.2307/1969481|jstor=1969481 }}</ref> पोस्ट के निर्माण को आगे बढ़ाकर। सबूत का पालन करना मुश्किल है। लेकिन समूहों के लिए शब्द समस्या में एक महत्वपूर्ण मोड़ है.{{r|Miller|p=342}}}}
-* {{Timeline-event |date={{Start date|1955}}|event=[[Pyotr Novikov]] gives the first published proof that the word problem for groups is unsolvable, using Turing’s cancellation semigroup result.<ref>{{cite journal |last=Novikov|first=P. S.|author-link=Pyotr Novikov|year=1955|title=On the algorithmic unsolvability of the word problem in group theory|language=ru| zbl=0068.01301 | journal=[[Proceedings of the Steklov Institute of Mathematics]]|volume=44|pages=1–143}}</ref>{{r|Miller|p=354}} The proof contains a "Principal Lemma" equivalent to [[Britton's Lemma]].{{r|Miller|p=355}}}}
-* {{Timeline-event |date={{Start date|1954}}|end_date={{End date|1957}}|event=[[William Boone (mathematician)|William Boone]] independently shows the word problem for groups is unsolvable, using Post's semigroup construction.<ref>{{cite journal |last1=Boone |first1=William W. |title=Certain Simple, Unsolvable Problems of Group Theory. I|journal=Indagationes Mathematicae (Proceedings) |date=1954 |volume=57 |pages=231–237 |doi=10.1016/S1385-7258(54)50033-8}}</ref><ref>{{cite journal |last1=Boone |first1=William W. |title=Certain Simple, Unsolvable Problems of Group Theory. VI |journal=Indagationes Mathematicae (Proceedings) |date=1957 |volume=60 |pages=227–232 |doi=10.1016/S1385-7258(57)50030-9|doi-access=free }}</ref>}}
-* {{Timeline-event |date={{Start date|1957}}|end_date={{End date|1958}}|event=[[John Britton (mathematician)|John Britton]] gives another proof that the word problem for groups is unsolvable, based on Turing's cancellation semigroups result and some of Britton's earlier work.<ref>{{cite journal |last1=Britton |first1=J. L. |title=The Word Problem for Groups |journal=Proceedings of the London Mathematical Society |date=October 1958 |volume=s3-8 |issue=4 |pages=493–506 |doi=10.1112/plms/s3-8.4.493}}</ref> An early version of Britton's Lemma appears.{{r|Miller|p=355}}}}
-* {{Timeline-event |date={{Start date|1958}}|end_date={{End date|1959}}|event=Boone publishes a simplified version of his construction.<ref>{{cite journal |last=Boone|first=William W.| author-link=William Boone (mathematician) | year=1958|title=The word problem|journal=Proceedings of the National Academy of Sciences|volume=44|issue=10|pages=1061–1065|url=http://www.pnas.org/cgi/reprint/44/10/1061.pdf|doi=10.1073/pnas.44.10.1061|zbl=0086.24701 |pmc=528693|pmid=16590307|bibcode=1958PNAS...44.1061B|doi-access=free}}</ref><ref>{{cite journal |last1=Boone |first1=William W. |title=The Word Problem |journal=The Annals of Mathematics |date=September 1959 |volume=70 |issue=2 |pages=207–265 |doi=10.2307/1970103|jstor=1970103 }}</ref>}}
-* {{Timeline-event |date={{Start date|1961}}|event=[[Graham Higman]] characterises the subgroups of finitely presented groups with [[Higman's embedding theorem]],<ref>{{cite journal |title=Subgroups of finitely presented groups |journal=Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences |date=8 August 1961 |volume=262 |issue=1311 |pages=455–475 |doi=10.1098/rspa.1961.0132|bibcode=1961RSPSA.262..455H |last1=Higman |first1=G. |s2cid=120100270 }}</ref> connecting recursion theory with group theory in an unexpected way and giving a very different proof of the unsolvability of the word problem.{{r|Miller}}}}
-* {{Timeline-event |date={{Start date|1961}} |end_date={{End date|1963}}|event=Britton presents a greatly simplified version of Boone's 1959 proof that the word problem for groups is unsolvable.<ref>{{cite journal |last1=Britton |first1=John L. |title=The Word Problem |journal=The Annals of Mathematics |date=January 1963 |volume=77 |issue=1 |pages=16–32 |doi=10.2307/1970200|jstor=1970200 }}</ref> It uses a group-theoretic approach, in particular [[Britton's Lemma]]. This proof has been used in a graduate course, although more modern and condensed proofs exist.<ref>{{cite web |last1=Simpson |first1=Stephen G. |title=A Slick Proof of the Unsolvability of the Word Problem for Finitely Presented Groups |url=http://www.personal.psu.edu/t20/logic/seminar/050517.pdf |access-date=6 December 2021 |date=18 May 2005}}</ref>}}
-* {{Timeline-event |date={{Start date|1977}}|event=Gennady Makanin proves that the existential theory of equations over free monoids is solvable.<ref>{{cite journal |title=Subgroups of finitely presented groups |journal=Mathematics of the USSR-Sbornik |date=13 February 1977 |volume=103 |issue=145 |pages=147–236 |doi=10.1070/SM1977v032n02ABEH002376}}</ref>}}
-== सेमी-थ्यू सिस्टम के लिए शब्द समस्या ==
+* 1911: मैक्स डेह्न ने अंतिम रूप से प्रस्तुत समूहों के लिए शब्द समस्या प्रस्तुत की।
+* 1912: डेन के एल्गोरिथ्म को प्रस्तुत करता है, और यह साबित करता है कि यह 2 से अधिक या उसके बराबर जीनस के बंद उन्मुख द्वि-आयामी कई गुना के मौलिक समूहों के लिए शब्द समस्या को हल करता है।  बाद के लेखकों ने समूह सैद्धांतिक निर्णय समस्याओं की एक विस्तृत श्रृंखला के लिए इसे काफी विस्तारित किया है।
+* 1914: एक्सल थू ने सूक्ष्म रूप से प्रस्तुत अर्धसमूहों के लिए शब्द समस्या प्रस्तुत की।
+* 1930 - 1938: चर्च-ट्यूरिंग थीसिस उभरती है, संगणनीयता और अनिर्वचनीयता की औपचारिक धारणाओं को परिभाषित करती है।
+* 1947: एमिल पोस्ट और एंड्री मार्कोव जूनियर स्वतंत्र रूप से अघुलनशील शब्द समस्या के साथ सूक्ष्म रूप से प्रस्तुत अर्धसमूहों का निर्माण करते हैं।  पोस्ट का निर्माण ट्यूरिंग मशीनों पर किया गया है जबकि मार्कोव पोस्ट के सामान्य सिस्टम का उपयोग करता है।
+* 1950: पोस्ट के निर्माण को आगे बढ़ाकर एलन ट्यूरिंग दिखाते हैं कि रद्द किए गए सेमीग्रुप्स के लिए शब्द समस्या अघुलनशील है। सबूत का पालन करना मुश्किल है लेकिन समूहों के लिए शब्द समस्या में एक महत्वपूर्ण मोड़ है।
+* 1955: प्योत्र नोविकोव ने पहला प्रकाशित प्रमाण दिया कि ट्यूरिंग के रद्दीकरण सेमीग्रुप परिणाम का उपयोग करते हुए समूहों के लिए शब्द समस्या अघुलनशील है।  सबूत में ब्रिटन के लेम्मा के बराबर एक "प्रिंसिपल लेम्मा" है।
+* 1954 - 1957: पोस्ट के सेमीग्रुप निर्माण का उपयोग करते हुए विलियम बून स्वतंत्र रूप से समूहों के लिए शब्द समस्या को हल करने योग्य नहीं दिखाते हैं।
+* 1957 - 1958: जॉन ब्रिटन ने एक और प्रमाण दिया कि समूहों के लिए शब्द समस्या अघुलनशील है, जो ट्यूरिंग के निरस्तीकरण सेमिग्रुप परिणाम और ब्रिटन के कुछ पहले के काम पर आधारित है। [20] ब्रिटन के लेम्मा का एक प्रारंभिक संस्करण प्रकट होता है।
+* 1958 - 1959: बूने ने अपने निर्माण का एक सरलीकृत संस्करण प्रकाशित किया।
+* 1961: ग्राहम हिगमैन, हिगमैन के एम्बेडिंग प्रमेय के साथ अंतिम रूप से प्रस्तुत समूहों के उपसमूहों की विशेषता बताता है। समूह सिद्धांत के साथ पुनरावर्तन सिद्धांत को अप्रत्याशित तरीके से जोड़ता है और शब्द समस्या की असम्बद्धता का एक बहुत अलग प्रमाण देता है।
+* 1961 - 1963: ब्रिटन ने बूने के 1959 के प्रमाण का एक बहुत ही सरलीकृत संस्करण प्रस्तुत किया कि समूहों के लिए शब्द समस्या हल नहीं हो सकती है। यह एक समूह-सैद्धांतिक दृष्टिकोण का उपयोग करता है, विशेष रूप से ब्रिटन की लेम्मा में। इस प्रमाण का उपयोग स्नातक पाठ्यक्रम में किया गया है, हालांकि अधिक आधुनिक और संघनित प्रमाण उपस्थित हैं।
+* 1977: गेन्नेडी माकानिन ने साबित किया कि मुक्त मोनोइड्स पर समीकरणों का अस्तित्व सिद्धांत हल करने योग्य है।
+== सेमी-थ्यू प्रणाली के लिए शब्द समस्या ==
+[[स्ट्रिंग पुनर्लेखन प्रणाली]] (सेमी-थ्यू प्रणाली या सेमीग्रुप) के लिए एक्सेसिबिलिटी समस्या निम्नानुसार बताई जा सकती है: एक सेमी-थ्यू प्रणाली <math>T:=(\Sigma, R)</math> दिया गया  और दो शब्द (तार) <math>u, v \in \Sigma^*</math><math>u</math> में बदलकर <math>v</math> से <math>R</math> नियम लागू करें।  ध्यान दें कि यहाँ पुनर्लेखन एक ओर है। शब्द समस्या सममित पुनर्लेखन संबंधों, अर्थात् थ्यू प्रणाली के लिए अभिगम्यता समस्या है।<ref name="Matiyasevich">{{cite journal |last1=Matiyasevich |first1=Yuri |last2=Sénizergues |first2=Géraud |title=कुछ नियमों के साथ अर्ध-थू सिस्टम के लिए निर्णय समस्याएँ|journal=Theoretical Computer Science |date=January 2005 |volume=330 |issue=1 |pages=145–169 |doi=10.1016/j.tcs.2004.09.016|doi-access=free }}</ref>
+अभिगम्यता और शब्द समस्याएँ अनिर्णीत समस्याएँ हैं, अर्थात इस समस्या को हल करने के लिए कोई सामान्य एल्गोरिद्म नहीं है।<ref>{{cite journal |last1=Davis |first1=Martin |title=What is a Computation? |journal=Mathematics Today Twelve Informal Essays |date=1978 |pages=257–259 |doi=10.1007/978-1-4613-9435-8_10 |isbn=978-1-4613-9437-2 |url=https://www.cs.princeton.edu/courses/archive/spring11/cos116/handouts/daviscomputation.pdf |access-date=5 December 2021}}</ref> यह तब भी होता है, जब हम प्रणाली को सीमित प्रस्तुतियों तक सीमित करते हैं, अर्थात् प्रतीकों का एक सीमित समूह और उन प्रतीकों पर संबंधों का एक सीमित समूह<ref name="Matiyasevich" />यहां तक कि निचले शब्दों तक सीमित शब्द समस्या भी निश्चित रूप से प्रस्तुत अर्धसमूहों के लिए निर्णायक नहीं है।<ref name="Nipkow" /><ref>*{{cite journal |last1=Matiyasevich |first1=Yu. V.|title= Простые примеры неразрешимых ассоциативных исчислений  |trans-title=Simple examples of undecidable associative calculi |journal=[[Proceedings of the USSR Academy of Sciences|Doklady Akademii Nauk SSSR]] |date=1967 |volume=173|issue=6|pages=1264–1266|url=http://mi.mathnet.ru/eng/dan/v173/i6/p1264 |language=Russian |issn=0869-5652}}
+*{{cite journal |last1=Matiyasevich |first1=Yu. V. |title=Simple examples of undecidable associative calculi |journal=Soviet Mathematics |date=1967 |volume=8|issue=2 |pages=555–557|issn=0197-6788}}</ref>
-[[स्ट्रिंग पुनर्लेखन प्रणाली]] (सेमी-थ्यू सिस्टम या सेमीग्रुप) के लिए एक्सेसिबिलिटी समस्या निम्नानुसार बताई जा सकती है: एक सेमी-थ्यू सिस्टम दिया गया <math>T:=(\Sigma, R)</math> और दो शब्द (तार) <math>u, v \in \Sigma^*</math>, कर सकना <math>u</math> में तब्दील हो <math>v</math> से नियम लागू करके <math>R</math>? ध्यान दें कि यहाँ पुनर्लेखन एक तरफ़ा है। शब्द समस्या सममित पुनर्लेखन संबंधों, यानी थ्यू सिस्टम के लिए अभिगम्यता समस्या है।<ref name=Matiyasevich>{{cite journal |last1=Matiyasevich |first1=Yuri |last2=Sénizergues |first2=Géraud |title=कुछ नियमों के साथ अर्ध-थू सिस्टम के लिए निर्णय समस्याएँ|journal=Theoretical Computer Science |date=January 2005 |volume=330 |issue=1 |pages=145–169 |doi=10.1016/j.tcs.2004.09.016|doi-access=free }}</ref>
-अभिगम्यता और शब्द समस्याएँ अनिर्णीत समस्याएँ हैं, अर्थात इस समस्या को हल करने के लिए कोई सामान्य एल्गोरिद्म नहीं है।<ref>{{cite journal |last1=Davis |first1=Martin |title=What is a Computation? |journal=Mathematics Today Twelve Informal Essays |date=1978 |pages=257–259 |doi=10.1007/978-1-4613-9435-8_10 |isbn=978-1-4613-9437-2 |url=https://www.cs.princeton.edu/courses/archive/spring11/cos116/handouts/daviscomputation.pdf |access-date=5 December 2021}}</ref> यह तब भी होता है जब हम सिस्टम को सीमित प्रस्तुतियों तक सीमित करते हैं, यानी प्रतीकों का एक सीमित समूह और उन प्रतीकों पर संबंधों का एक सीमित समूह।<ref name=Matiyasevich/>यहां तक कि जमीनी शब्दों तक सीमित शब्द समस्या भी निश्चित रूप से प्रस्तुत अर्धसमूहों के लिए निर्णायक नहीं है।<ref name=Nipkow/><ref>
-* {{cite journal |last1=Matiyasevich |first1=Yu. V.|title= Простые примеры неразрешимых ассоциативных исчислений  |trans-title=Simple examples of undecidable associative calculi |journal=[[Proceedings of the USSR Academy of Sciences|Doklady Akademii Nauk SSSR]] |date=1967 |volume=173|issue=6|pages=1264–1266|url=http://mi.mathnet.ru/eng/dan/v173/i6/p1264 |language=Russian |issn=0869-5652}}
-* {{cite journal |last1=Matiyasevich |first1=Yu. V. |title=Simple examples of undecidable associative calculi |journal=Soviet Mathematics |date=1967 |volume=8|issue=2 |pages=555–557|issn=0197-6788}}</ref>
 == समूहों के लिए शब्द समस्या ==
-{{main|Word problem for groups}}
+{{main|समूहों के लिए शब्द समस्या}}
-प्रस्तुति दी <math>\langle S\mid \mathcal{R} \rangle</math> समूह G के लिए, शब्द समस्या निर्णय लेने की एल्गोरिथम समस्या है, जो S में इनपुट दो शब्दों के रूप में दी गई है, क्या वे G के समान तत्व का प्रतिनिधित्व करते हैं। शब्द समस्या 1911 में [[मैक्स डेहन]] द्वारा प्रस्तावित समूहों के लिए तीन एल्गोरिथम समस्याओं में से एक है। यह 1955 में [[ पीटर नोविकोव ]] द्वारा दिखाया गया था कि एक सूक्ष्म रूप से प्रस्तुत समूह G मौजूद है जैसे कि G के लिए शब्द समस्या अनिर्णीत समस्या है।<ref>{{Cite journal|last1=Novikov|first1=P. S.|author1-link=Pyotr Novikov|title=समूह सिद्धांत में शब्द समस्या की एल्गोरिदमिक असम्बद्धता पर|journal=Trudy Mat. Inst. Steklov|volume=44|year=1955|pages=1–143|language=ru}}</ref>
+<math>\langle S\mid \mathcal{R} \rangle</math> समूह G के लिए प्रस्तुति दी। शब्द समस्या निर्णय लेने की एल्गोरिथम समस्या है। जो S में इनपुट दो शब्दों के रूप में दी गई है। क्या वे G के समान तत्व का प्रतिनिधित्व करते हैं। शब्द समस्या 1911 में [[मैक्स डेहन]] द्वारा प्रस्तावित समूहों के लिए तीन एल्गोरिथम समस्याओं में से एक है। यह 1955 में [[ पीटर नोविकोव ]] द्वारा दिखाया गया था कि एक सूक्ष्म रूप से प्रस्तुत समूह G उपस्थित है। जैसे कि G के लिए शब्द समस्या अनिर्णीत समस्या है।<ref>{{Cite journal|last1=Novikov|first1=P. S.|author1-link=Pyotr Novikov|title=समूह सिद्धांत में शब्द समस्या की एल्गोरिदमिक असम्बद्धता पर|journal=Trudy Mat. Inst. Steklov|volume=44|year=1955|pages=1–143|language=ru}}</ref>
 कॉम्बिनेटरियल कैलकुलस और लैम्ब्डा कैलकुलस में वर्ड प्रॉब्लम =
-{{main | Combinatory logic#Undecidability of combinatorial calculus}}
+{{main |कॉम्बिनेटर लॉजिक  कॉम्बिनेटरियल कैलकुलस की अनिश्चितता}}
-सबसे शुरुआती प्रमाणों में से एक है कि एक शब्द समस्या अनिर्णीत है जो [[संयोजन तर्क]] के लिए थी: कॉम्बिनेटर के दो तार कब बराबर होते हैं? क्योंकि कॉम्बिनेटर सभी संभव [[ट्यूरिंग मशीन]]ों को एनकोड करते हैं, और दो ट्यूरिंग मशीनों की समानता अनिर्णीत है, यह इस प्रकार है कि कॉम्बिनेटर के दो स्ट्रिंग्स की समानता अनिर्णीत है। 1936 में [[अलोंजो चर्च]] ने इसका अवलोकन किया।<ref>{{cite journal |last1=Statman |first1=Rick |title=कॉम्बिनेटर्स के लिए वर्ड प्रॉब्लम पर|journal=Rewriting Techniques and Applications |series=Lecture Notes in Computer Science |date=2000 |volume=1833 |pages=203–213 |doi=10.1007/10721975_14|isbn=978-3-540-67778-9 }}</ref>
-इसी प्रकार, (अनटाइप्ड) [[लैम्ब्डा कैलकुलस]] में अनिवार्य रूप से एक ही समस्या है: दो अलग-अलग लैम्ब्डा एक्सप्रेशन दिए गए हैं, कोई एल्गोरिथ्म नहीं है जो यह बता सके कि वे समकक्ष हैं या नहीं; लैम्ब्डा कैलकुलस#तुल्यता की अनिश्चितता। लैम्ब्डा कैलकुस के कई टाइप किए गए रूपों के लिए, सामान्य रूपों की तुलना करके समानता निर्णायक है।
+सबसे प्रारम्भिकप्रमाणों में से एक है कि एक शब्द समस्या अनिर्णीत है। जो [[संयोजन तर्क]] के लिए थी। कॉम्बिनेटर के दो तार कब बराबर होते हैं? क्योंकि कॉम्बिनेटर सभी संभव [[ट्यूरिंग मशीन|ट्यूरिंग मशीनों]] को एनकोड करते हैं और दो ट्यूरिंग मशीनों की समानता अनिर्णीत है। यह इस प्रकार है कि कॉम्बिनेटर के दो स्ट्रिंग्स की समानता अनिर्णीत है। 1936 में [[अलोंजो चर्च]] ने इसका अवलोकन किया।<ref>{{cite journal |last1=Statman |first1=Rick |title=कॉम्बिनेटर्स के लिए वर्ड प्रॉब्लम पर|journal=Rewriting Techniques and Applications |series=Lecture Notes in Computer Science |date=2000 |volume=1833 |pages=203–213 |doi=10.1007/10721975_14|isbn=978-3-540-67778-9 }}</ref>
+इसी प्रकार (अनटाइप्ड) [[लैम्ब्डा कैलकुलस]] में अनिवार्य रूप से एक ही समस्या है। दो अलग-अलग लैम्ब्डा एक्सप्रेशन दिए गए हैं। कोई एल्गोरिथ्म नहीं है, जो यह बता सके कि वे समकक्ष हैं या नहीं। लैम्ब्डा कैलकुलस तुल्यता की अनिश्चितता लैम्ब्डा कैलकुस के कई टाइप किए गए रूपों के लिए सामान्य रूपों की तुलना करके समानता निर्णायक है।
 == सार पुनर्लेखन प्रणाली के लिए शब्द समस्या ==
@@ Line 59: / Line 77: @@
 सार्वभौमिक बीजगणित में एक बीजीय संरचनाओं का अध्ययन करता है जिसमें एक [[जनरेटिंग सेट|जनरेटिंग समूह]] A, परिमित arity (आमतौर पर बाइनरी ऑपरेशंस) के A पर संचालन का एक संग्रह होता है, और पहचान का एक परिमित समूह होता है जिसे इन ऑपरेशनों को पूरा करना चाहिए। एक बीजगणित के लिए शब्द समस्या तब निर्धारित करने के लिए है, दो भाव (शब्द) दिए गए हैं जिनमें जनरेटर और संचालन शामिल हैं, चाहे वे बीजगणित मॉड्यूलो के समान तत्व का प्रतिनिधित्व करते हों। समूहों और अर्धसमूहों के लिए शब्द समस्याओं को बीजगणित के लिए शब्द समस्याओं के रूप में अभिव्यक्त किया जा सकता है।<ref name=Evans/>
-मुक्त Heyting बीजगणित पर शब्द समस्या कठिन है।<ref>Peter T. Johnstone, ''Stone Spaces'', (1982) Cambridge University Press, Cambridge, {{isbn|0-521-23893-5}}. ''(See chapter 1, paragraph 4.11)''</ref> एकमात्र ज्ञात परिणाम यह है कि एक जनरेटर पर मुफ्त हेटिंग बीजगणित अनंत है, और यह कि एक जनरेटर पर मुक्त पूर्ण हेटिंग बीजगणित मौजूद है (और मुक्त हेटिंग बीजगणित की तुलना में एक और तत्व है)।
+मुक्त Heyting बीजगणित पर शब्द समस्या कठिन है।<ref>Peter T. Johnstone, ''Stone Spaces'', (1982) Cambridge University Press, Cambridge, {{isbn|0-521-23893-5}}. ''(See chapter 1, paragraph 4.11)''</ref> एकमात्र ज्ञात परिणाम यह है कि एक जनरेटर पर मुफ्त हेटिंग बीजगणित अनंत है, और यह कि एक जनरेटर पर मुक्त पूर्ण हेटिंग बीजगणित उपस्थित है (और मुक्त हेटिंग बीजगणित की तुलना में एक और तत्व है)।
 ==मुक्त जाली के लिए शब्द समस्या==

Anonymous

Search

शब्द समस्या (गणित): Difference between revisions

Namespaces

More

Page actions

Revision as of 22:40, 28 March 2023

Contents

पृष्ठभूमि और प्रेरणा

इतिहास

सेमी-थ्यू प्रणाली के लिए शब्द समस्या

समूहों के लिए शब्द समस्या

सार पुनर्लेखन प्रणाली के लिए शब्द समस्या

सार्वभौमिक बीजगणित में शब्द समस्या

मुक्त जाली के लिए शब्द समस्या

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

शब्द समस्या (गणित): Difference between revisions

Revision as of 22:40, 28 March 2023

पृष्ठभूमि और प्रेरणा

इतिहास

सेमी-थ्यू प्रणाली के लिए शब्द समस्या

समूहों के लिए शब्द समस्या

सार पुनर्लेखन प्रणाली के लिए शब्द समस्या

सार्वभौमिक बीजगणित में शब्द समस्या

मुक्त जाली के लिए शब्द समस्या

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories