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

Latest revision as of 18:41, 21 April 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

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

x\downarrow =y\downarrow

(ग्रे) सीधा है।

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

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

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

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

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

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

उदाहरण की गणना x∧z ~ x∧z∧(x∨y)

		x∧z∧(x∨y)	≤_~	x∧z
5 के द्वारा	तब से	x∧z	≤_~	x∧z
1के द्वारा	तब से	x∧z	=	x∧z

		x∧z	≤_~	x∧z∧(x∨y)
7 के द्वारा	तब से	x∧z	≤_~	x∧z	और			x∧z	≤_~	x∨y
1 के द्वारा	तब से	x∧z	=	x∧z		6 के द्वारा	तब से	x∧z	≤_~	x
						5 के द्वारा	तब से	x	≤_~	x
						1 के द्वारा	तब से	x	=	x

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

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

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

यह एक पूर्व आदेश ≤ W(X) पर परिभाषित करता है। इसलिए एक तुल्यता संबंध को w ~ v द्वारा परिभाषित किया जा सकता है। जब w ≤_~ v and v ≤_~ w तब कोई यह दिखा सकता है कि आंशिक रूप से आदेशित भागफल समुच्चय 'W'(X)/~ मुक्त परिबद्ध जालक FX है।^[13]^[14] W(X)/~ के समतुल्य वर्ग सभी शब्दों w और v के साथ w ≤_~ v और v ≤_~ w के समुच्चय हैं। 'W'(X) में दो सुगठित शब्द v और w प्रत्येक बंधे हुए जालक में समान मान को दर्शाते हैं। यदि और केवल यदि w ≤_~ v और v ≤_~ 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$ , है । चूँकि सामान्य रूप वस्तुतः भिन्न होते हैं। मूल शब्द प्रत्येक समूह में समान नहीं हो सकते। वास्तविक रूप में वे सामान्यतःएबेलियन समूह गैर-एबेलियन समूहों में भिन्न होते हैं।

नुथ-बेंडिक्स पूर्णता में प्रयुक्त समूह अभिगृहीत
A1	$1\cdot x$	$=x$
A2	$x^{-1}\cdot x$	$=1$
A3	$(x\cdot y)\cdot z$	$=x\cdot (y\cdot z)$

नुथ-बेंडिक्स पूर्णता से प्राप्त शब्द पुनर्लेखन प्रणाली
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 7: / Line 7: @@
 == पृष्ठभूमि और प्रेरणा ==
-[[कंप्यूटर बीजगणित]] में अधिकांशतः अभिव्यक्ति ट्री का उपयोग करके गणितीय अभिव्यक्तियों को एन्कोड करना चाहता है। किन्तु अधिकांशतः कई समान अभिव्यक्ति ट्री होते हैं। स्वाभाविक रूप से यह प्रश्न  है कि क्या कोई एल्गोरिथम है। जो दो भावों के इनपुट के रूप में दिया गया है। यह निर्णय करता है कि क्या वे एक ही तत्व का प्रतिनिधित्व करते हैं। इस प्रकार के एल्गोरिदम को शब्द समस्या का समाधान कहा जाता है। उदाहरण के लिए, माना कि <math>x,y,z</math> [[वास्तविक संख्या]]ओं का प्रतिनिधित्व करने वाले प्रतीक हैं। तो इनपुट दिए जाने पर शब्द समस्या का एक प्रासंगिक समाधान <math>(x \cdot y)/z \mathrel{\overset{?}{=}} (x/z)\cdot y</math> होगा और <code>EQUAL</code> उत्पाद है। इसी प्रकार <code>NOT_EQUAL</code> से <math>(x \cdot y)/z \mathrel{\overset{?}{=}} (x/x)\cdot y</math>. उत्पादन करते हैं।
+[[कंप्यूटर बीजगणित]] में अधिकांशतः अभिव्यक्ति ट्री का उपयोग करके गणितीय अभिव्यक्तियों को एन्कोड करना चाहता है। किन्तु अधिकांशतः कई समान अभिव्यक्ति ट्री होते हैं। स्वाभाविक रूप से यह प्रश्न है कि क्या कोई एल्गोरिथम है। जो दो भावों के इनपुट के रूप में दिया गया है। यह निर्णय करता है कि क्या वे एक ही तत्व का प्रतिनिधित्व करते हैं। इस प्रकार के एल्गोरिदम को शब्द समस्या का समाधान कहा जाता है। उदाहरण के लिए, माना कि <math>x,y,z</math> [[वास्तविक संख्या]]ओं का प्रतिनिधित्व करने वाले प्रतीक हैं। तो इनपुट दिए जाने पर शब्द समस्या का एक प्रासंगिक समाधान <math>(x \cdot y)/z \mathrel{\overset{?}{=}} (x/z)\cdot y</math> होगा और <code>EQUAL</code> उत्पाद है। इसी प्रकार <code>NOT_EQUAL</code> से <math>(x \cdot y)/z \mathrel{\overset{?}{=}} (x/x)\cdot y</math>. उत्पादन करते हैं।
-शब्द समस्या का सबसे सीधा एवं सरल समाधान सामान्य प्रमेय और एल्गोरिथ्म का रूप लेता है। जो प्रत्येक तत्व को भावों के समतुल्य वर्ग में [[कानूनी फॉर्म|नियम फॉर्म]] के रूप में ज्ञात एकल एन्कोडिंग में मैप करता है। शब्द समस्या तब इन सामान्य रूपों की तुलना [[वाक्यगत समानता]] करके हल की जाती है।<ref name=Evans>{{cite journal |last1=Evans |first1=Trevor |title=शब्द की समस्याएं|journal=Bulletin of the American Mathematical Society |date=1978 |volume=84 |issue=5 |pages=790 |doi=10.1090/S0002-9904-1978-14516-9|doi-access=free }}</ref> उदाहरण के लिए कोई यह सुनिश्चित कर सकता है कि <math>x \cdot y \cdot z^{-1}</math> का सामान्य रूप है। <math>(x \cdot y)/z</math>, <math>(x/z)\cdot y</math>, और <math>(y/z)\cdot x</math> और उन भावों को उस रूप में फिर से लिखने के लिए एक परिवर्तन प्रणाली तैयार करें। इस प्रक्रिया में यह  सिद्ध करते हुए कि सभी समान भावों को उसी सामान्य रूप में फिर से लिखा जाएगा।<ref>{{cite book |last1=Cohen |first1=Joel S. |title=Computer algebra and symbolic computation: elementary algorithms |date=2002 |publisher=A K Peters |location=Natick, Mass. |isbn=1568811586 |pages=90–92}}</ref> किन्तु शब्द समस्या के सभी समाधान सामान्य रूप प्रमेय का उपयोग नहीं करते हैं। ऐसे बीजीय गुण हैं, जो अप्रत्यक्ष रूप से एल्गोरिथम के प्रमाण का संकेत देते हैं।<ref name=Evans/>
+शब्द समस्या का सबसे सीधा एवं सरल समाधान सामान्य प्रमेय और एल्गोरिथ्म का रूप लेता है। जो प्रत्येक तत्व को भावों के समतुल्य वर्ग में [[कानूनी फॉर्म|नियम फॉर्म]] के रूप में ज्ञात एकल एन्कोडिंग में मैप करता है। शब्द समस्या तब इन सामान्य रूपों की तुलना [[वाक्यगत समानता]] करके हल की जाती है।<ref name=Evans>{{cite journal |last1=Evans |first1=Trevor |title=शब्द की समस्याएं|journal=Bulletin of the American Mathematical Society |date=1978 |volume=84 |issue=5 |pages=790 |doi=10.1090/S0002-9904-1978-14516-9|doi-access=free }}</ref> उदाहरण के लिए कोई यह सुनिश्चित कर सकता है कि <math>x \cdot y \cdot z^{-1}</math> का सामान्य रूप है। <math>(x \cdot y)/z</math>, <math>(x/z)\cdot y</math>, और <math>(y/z)\cdot x</math> और उन भावों को उस रूप में फिर से लिखने के लिए एक परिवर्तन प्रणाली तैयार करें। इस प्रक्रिया में यह सिद्ध करते हुए कि सभी समान भावों को उसी सामान्य रूप में फिर से लिखा जाएगा।<ref>{{cite book |last1=Cohen |first1=Joel S. |title=Computer algebra and symbolic computation: elementary algorithms |date=2002 |publisher=A K Peters |location=Natick, Mass. |isbn=1568811586 |pages=90–92}}</ref> किन्तु शब्द समस्या के सभी समाधान सामान्य रूप प्रमेय का उपयोग नहीं करते हैं। ऐसे बीजीय गुण हैं, जो अप्रत्यक्ष रूप से एल्गोरिथम के प्रमाण का संकेत देते हैं।<ref name=Evans/>
 जबकि शब्द समस्या पूछती है कि क्या स्थिरांक (गणित) वाले दो शब्द समान हैं। शब्द समस्या का एक उचित विस्तार, जिसे [[एकीकरण (कंप्यूटर विज्ञान)]] के रूप में जाना जाता है, पूछता है कि क्या दो शब्द <math>t_1,t_2</math> वेरिएबल (गणित) वाले ऐसे उदाहरण हैं। जो बराबर हैं या दूसरे शब्दों में समीकरण <math>t_1 = t_2</math> हैं। एक सामान्य उदाहरण के रूप में <math>2 + 3 \stackrel{?}{=} 8 + (-3)</math> पूर्णांक बीजगणितीय गुणों में शब्द समस्या है। पूर्णांक समूह ℤ है।
@@ 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>
-* 1910: एक्सल थू ने पेड़ जैसी संरचनाओं पर शब्द पुनर्लेखन की एक सामान्य समस्या पेश की। वह कहते हैं, "सबसे सामान्य स्थितियों में इस समस्या का समाधान शायद असाध्य कठिनाइयों से जुड़ा हो सकता है"।
+* 1910: एक्सल थू ने पेड़ जैसी संरचनाओं पर शब्द पुनर्लेखन की एक सामान्य समस्या पेश की। वह कहते हैं कि "सबसे सामान्य स्थितियों में इस समस्या का समाधान संभवतः अनगिनत कठिनाइयों से जुड़ा हो सकता है"।
 * 1911: मैक्स डेह्न ने अंतिम रूप से प्रस्तुत समूहों के लिए शब्द समस्या प्रस्तुत की।
-* 1912: डेन के एल्गोरिथ्म को प्रस्तुत करता है, और यह साबित करता है कि यह 2 से अधिक या उसके बराबर जीनस के बंद उन्मुख द्वि-आयामी कई गुना के मौलिक समूहों के लिए शब्द समस्या को हल करता है।  बाद के लेखकों ने समूह सैद्धांतिक निर्णय समस्याओं की एक विस्तृत श्रृंखला के लिए इसे अधिक विस्तारित किया है।
+* 1912: डेन के एल्गोरिथ्म को प्रस्तुत करता है और यह सिद्ध करता है कि यह 2 से अधिक या उसके बराबर जीनस के बंद उन्मुख द्वि-आयामी कई गुना के मौलिक समूहों के लिए शब्द समस्या को हल करता है। बाद के लेखकों ने समूह सैद्धांतिक निर्णय समस्याओं की एक विस्तृत श्रृंखला के लिए इसे अधिक विस्तारित किया है।
 * 1914: एक्सल थू ने सूक्ष्म रूप से प्रस्तुत अर्धसमूहों के लिए शब्द समस्या प्रस्तुत की।
-* 1930 - 1938: चर्च-ट्यूरिंग थीसिस उभरती है, संगणनीयता और अनिर्वचनीयता की औपचारिक धारणाओं को परिभाषित करती है।
+* 1930 - 1938: चर्च-ट्यूरिंग थीसिस उभरती है। संगणनीयता और अनिर्वचनीयता की औपचारिक धारणाओं को परिभाषित करती है।
-* 1947: एमिल पोस्ट और एंड्री मार्कोव जूनियर स्वतंत्र रूप से अघुलनशील शब्द समस्या के साथ सूक्ष्म रूप से प्रस्तुत अर्धसमूहों का निर्माण करते हैं।  पोस्ट का निर्माण ट्यूरिंग मशीनों पर किया गया है जबकि मार्कोव पोस्ट के सामान्य सिस्टम का उपयोग करता है।
+* 1947: एमिल पोस्ट और एंड्री मार्कोव जूनियर स्वतंत्र रूप से अघुलनशील शब्द समस्या के साथ सूक्ष्म रूप से प्रस्तुत अर्धसमूहों का निर्माण करते हैं। पोस्ट का निर्माण ट्यूरिंग मशीनों पर किया गया है। जबकि मार्कोव पोस्ट के सामान्य प्रणाली का उपयोग करता है।
-* 1950: पोस्ट के निर्माण को आगे बढ़ाकर एलन ट्यूरिंग दिखाते हैं कि रद्द किए गए सेमीग्रुप्स के लिए शब्द समस्या अघुलनशील है। सबूत का पालन करना मुश्किल है लेकिन समूहों के लिए शब्द समस्या में एक महत्वपूर्ण मोड़ है।
+* 1950: पोस्ट के निर्माण को आगे बढ़ाकर एलन ट्यूरिंग दिखाते हैं कि नष्ट किए गए सेमीग्रुप्स के लिए शब्द समस्या अघुलनशील है। प्रमाणन का पालन करना कठिन है। किन्तु समूहों के लिए शब्द समस्या में एक महत्वपूर्ण मोड़ है।
-* 1955: प्योत्र नोविकोव ने पहला प्रकाशित प्रमाण दिया कि ट्यूरिंग के रद्दीकरण सेमीग्रुप परिणाम का उपयोग करते हुए समूहों के लिए शब्द समस्या अघुलनशील है।  सबूत में ब्रिटन के लेम्मा के बराबर एक "प्रिंसिपल लेम्मा" है।
+* 1955: प्योत्र नोविकोव ने पहला प्रकाशित प्रमाण दिया कि ट्यूरिंग के नष्ट करने के सेमीग्रुप परिणाम का उपयोग करते हुए समूहों के लिए शब्द समस्या अघुलनशील है। प्रमाण में ब्रिटन के लेम्मा के बराबर एक "प्रिंसिपल लेम्मा" है।
 * 1954 - 1957: पोस्ट के सेमीग्रुप निर्माण का उपयोग करते हुए विलियम बून स्वतंत्र रूप से समूहों के लिए शब्द समस्या को हल करने योग्य नहीं दिखाते हैं।
-* 1957 - 1958: जॉन ब्रिटन ने एक और प्रमाण दिया कि समूहों के लिए शब्द समस्या अघुलनशील है, जो ट्यूरिंग के निरस्तीकरण सेमिग्रुप परिणाम और ब्रिटन के कुछ पहले के काम पर आधारित है। [20] ब्रिटन के लेम्मा का एक प्रारंभिक संस्करण प्रकट होता है।
+* 1957 - 1958: जॉन ब्रिटन ने एक और प्रमाण दिया कि समूहों के लिए शब्द समस्या अघुलनशील है। जो ट्यूरिंग के निरस्तीकरण सेमिग्रुप परिणाम और ब्रिटन के कुछ पहले के काम पर आधारित है। [20] ब्रिटन के लेम्मा का एक प्रारंभिक संस्करण प्रकट होता है।
 * 1958 - 1959: बूने ने अपने निर्माण का एक सरलीकृत संस्करण प्रकाशित किया।
-* 1961: ग्राहम हिगमैन, हिगमैन के एम्बेडिंग प्रमेय के साथ अंतिम रूप से प्रस्तुत समूहों के उपसमूहों की विशेषता बताता है। समूह सिद्धांत के साथ पुनरावर्तन सिद्धांत को अप्रत्याशित तरीके से जोड़ता है और शब्द समस्या की असम्बद्धता का एक बहुत अलग प्रमाण देता है।
+* 1961: ग्राहम हिगमैन, हिगमैन के एम्बेडिंग प्रमेय के साथ अंतिम रूप से प्रस्तुत समूहों के उपसमूहों की विशेषता बताता है। समूह सिद्धांत के साथ पुनरावर्तन सिद्धांत को अप्रत्याशित उपायों से जोड़ता है और शब्द समस्या की असम्बद्धता का एक बहुत अलग प्रमाण देता है।
-* 1961 - 1963: ब्रिटन ने बूने के 1959 के प्रमाण का एक बहुत ही सरलीकृत संस्करण प्रस्तुत किया कि समूहों के लिए शब्द समस्या हल नहीं हो सकती है। यह एक समूह-सैद्धांतिक दृष्टिकोण का उपयोग करता है, विशेष रूप से ब्रिटन की लेम्मा में। इस प्रमाण का उपयोग स्नातक पाठ्यक्रम में किया गया है, हालांकि अधिक आधुनिक और संघनित प्रमाण उपस्थित हैं।
+* 1961 - 1963: ब्रिटन ने बूने के 1959 के प्रमाण का एक बहुत ही सरलीकृत संस्करण प्रस्तुत किया कि समूहों के लिए शब्द समस्या हल नहीं हो सकती है। यह एक समूह-सैद्धांतिक दृष्टिकोण का उपयोग करता है, विशेष रूप से ब्रिटन की लेम्मा में। इस प्रमाण का उपयोग स्नातक पाठ्यक्रम में किया गया है। चूंकि अधिक आधुनिक और संघनित प्रमाण उपस्थित हैं।
-* 1977: गेन्नेडी माकानिन ने साबित किया कि मुक्त मोनोइड्स पर समीकरणों का अस्तित्व सिद्धांत हल करने योग्य है।
+* 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>
+[[स्ट्रिंग पुनर्लेखन प्रणाली]] (सेमी-थ्यू प्रणाली या सेमीग्रुप) के लिए एक्सेसिबिलिटी समस्या निम्नानुसार बताई जा सकती है: एक सेमी-थ्यू प्रणाली <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}}
@@ Line 58: / Line 58: @@
 {{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>
@@ Line 70: / Line 70: @@
 == सार पुनर्लेखन प्रणाली के लिए शब्द समस्या ==
-[[File:Solving the word problem without and with completion_svg.svg|thumb|शब्द समस्या को हल करना: यदि निर्धारित करना <math>x \stackrel{*}{\leftrightarrow} y</math> सामान्यतः अनुमानी खोज की आवश्यकता होती है। ({{color|#c00000|लाल}}, {{color|#00c000|हरा}}), निर्णय लेते समय <math>x\downarrow = y\downarrow</math>({{color|#808080|ग्रे}}) सीधा है। ]]सार पुनर्लेखन प्रणाली (एआरएस) के लिए शब्द समस्या अधिक संक्षिप्त है। दी गई वस्तुएँ x और y के अंतर्गत वे समतुल्य हैं <math>\stackrel{*}{\leftrightarrow}</math>?<ref name=Nipkow>{{cite book |last1=Baader |first1=Franz |last2=Nipkow |first2=Tobias |title=टर्म पुनर्लेखन और वह सब|date=5 August 1999 |publisher=Cambridge University Press |isbn=978-0-521-77920-3 |pages=59–60 |url=https://www.google.com/books/edition/Term_Rewriting_and_All_That/N7BvXVUCQk8C?hl=en&gbpv=1&pg=PA59 |language=en}}</ref> एआरएस के लिए शब्द समस्या सामान्य रूप से अनिर्णीत समस्या है। चूंकि विशिष्ट स्थितियों में शब्द समस्या के लिए एक संगणनीय कार्य समाधान है। जहाँ प्रत्येक वस्तु एक विशिष्ट सामान्य रूप में चरणों की एक सीमित संख्या में घट जाती है (अर्थात प्रणाली अभिसारी है)। दो वस्तुएँ समतुल्य हैं।  यदि और केवल यदि वे एक ही सामान्य रूप में कम हो जाते हैं।<ref>{{cite journal |last1=Beke |first1=Tibor |title=Categorification, term rewriting and the Knuth–Bendix procedure |journal=Journal of Pure and Applied Algebra |date=May 2011 |volume=215 |issue=5 |page=730 |doi=10.1016/j.jpaa.2010.06.019|doi-access=free }}</ref>
+[[File:Solving the word problem without and with completion_svg.svg|thumb|शब्द समस्या को हल करना: यदि निर्धारित करना <math>x \stackrel{*}{\leftrightarrow} y</math> सामान्यतः अनुमानी खोज की आवश्यकता होती है। ({{color|#c00000|लाल}}, {{color|#00c000|हरा}}), निर्णय लेते समय <math>x\downarrow = y\downarrow</math>({{color|#808080|ग्रे}}) सीधा है। ]]सार पुनर्लेखन प्रणाली (एआरएस) के लिए शब्द समस्या अधिक संक्षिप्त है। दी गई वस्तुएँ x और y के अंतर्गत वे समतुल्य हैं <math>\stackrel{*}{\leftrightarrow}</math>?<ref name=Nipkow>{{cite book |last1=Baader |first1=Franz |last2=Nipkow |first2=Tobias |title=टर्म पुनर्लेखन और वह सब|date=5 August 1999 |publisher=Cambridge University Press |isbn=978-0-521-77920-3 |pages=59–60 |url=https://www.google.com/books/edition/Term_Rewriting_and_All_That/N7BvXVUCQk8C?hl=en&gbpv=1&pg=PA59 |language=en}}</ref> एआरएस के लिए शब्द समस्या सामान्य रूप से अनिर्णीत समस्या है। चूंकि विशिष्ट स्थितियों में शब्द समस्या के लिए एक संगणनीय कार्य समाधान है। जहाँ प्रत्येक वस्तु एक विशिष्ट सामान्य रूप में चरणों की एक सीमित संख्या में घट जाती है (अर्थात प्रणाली अभिसारी है)। दो वस्तुएँ समतुल्य हैं। यदि और केवल यदि वे एक ही सामान्य रूप में कम हो जाते हैं।<ref>{{cite journal |last1=Beke |first1=Tibor |title=Categorification, term rewriting and the Knuth–Bendix procedure |journal=Journal of Pure and Applied Algebra |date=May 2011 |volume=215 |issue=5 |page=730 |doi=10.1016/j.jpaa.2010.06.019|doi-access=free }}</ref>
 नुथ-बेंडिक्स पूर्णता एल्गोरिथम का उपयोग समीकरणों के एक समूह को अभिसरण [[शब्द पुनर्लेखन प्रणाली]] में बदलने के लिए किया जा सकता है।
@@ Line 152: / Line 152: @@
 #   w = ''w''<sub>1</sub> ∨ ''w''<sub>2</sub> और दोनों ''w''<sub>1</sub> ≤<sub>~</sub> ''v'' और ''w''<sub>2</sub> ≤<sub>~</sub> ''v'' पकड़ती है।
 #   w = ''w''<sub>1</sub> ∧ ''w''<sub>2</sub> और या ''w''<sub>1</sub> ≤<sub>~</sub> ''v'' या ''w''<sub>2</sub> ≤<sub>~</sub> ''v'' पकड़ती है।
-#   v =  ''v''<sub>1</sub> ∨ ''v''<sub>2</sub> और या ''w'' ≤<sub>~</sub> ''v''<sub>1</sub> या ''w'' ≤<sub>~</sub> ''v''<sub>2</sub> पकड़ती है।
+#   v = ''v''<sub>1</sub> ∨ ''v''<sub>2</sub> और या ''w'' ≤<sub>~</sub> ''v''<sub>1</sub> या ''w'' ≤<sub>~</sub> ''v''<sub>2</sub> पकड़ती है।
-#  v =  ''v''<sub>1</sub> ∧ ''v''<sub>2</sub> और दोनों ''w'' ≤<sub>~</sub> ''v''<sub>1</sub> और ''w'' ≤<sub>~</sub> ''v''<sub>2</sub> पकड़ती है।
+#  v = ''v''<sub>1</sub> ∧ ''v''<sub>2</sub> और दोनों ''w'' ≤<sub>~</sub> ''v''<sub>1</sub> और ''w'' ≤<sub>~</sub> ''v''<sub>2</sub> पकड़ती है।
-यह एक [[पूर्व आदेश]] ≤  W(''X'') पर परिभाषित करता है। इसलिए एक [[तुल्यता संबंध]] को ''w'' ~ ''v'' द्वारा परिभाषित किया जा सकता है। जब ''w'' ≤<sub>~</sub> ''v'' and ''v'' ≤<sub>~</sub> ''w'' तब कोई यह दिखा सकता है कि आंशिक रूप से आदेशित भागफल समुच्चय 'W'(X)/~ मुक्त परिबद्ध जालक FX है।<ref>{{cite journal |last1=Whitman |first1=Philip M.|author-link=Philip M. Whitman |title=मुक्त जाली|journal=The Annals of Mathematics |date=January 1941 |volume=42 |issue=1 |pages=325–329 |doi=10.2307/1969001|jstor=1969001}}</ref><ref>{{Cite journal|doi = 10.2307/1968883|jstor = 1968883|last1 = Whitman|first1 = Philip M.|title = मुक्त जाली II|journal = Annals of Mathematics|year = 1942|volume = 43|issue = 1|pages = 104–115}}</ref> W(''X'')/~ के समतुल्य वर्ग सभी शब्दों ''w'' और ''v'' के साथ ''w'' ≤<sub>~</sub> ''v'' और ''v'' ≤<sub>~</sub> ''w'' के समुच्चय हैं। 'W'(X) में दो सुगठित शब्द v और w प्रत्येक बंधे हुए जालक में समान मान को दर्शाते हैं। यदि और केवल यदि ''w'' ≤<sub>~</sub> ''v'' और ''v'' ≤<sub>~</sub> ''w'' उपरोक्त आगमनात्मक परिभाषा का उपयोग करके बाद की स्थितियों को प्रभावी ढंग से तैयार किया जा सकता है। सारणी यह दिखाने के लिए एक उदाहरण संगणना दिखाती है कि x∧z और x∧z∧(x∨y) शब्द प्रत्येक बंधे हुए जालक में समान मान को दर्शाते हैं। जालक के स्थितियों ऊपर के निर्माण में, जो बंधे नहीं हैं, नियम 2 और 3 को छोड़कर ≤<sub>~</sub> उसी प्रकार से व्यवहार किया जाता है।
+यह एक [[पूर्व आदेश]] ≤ W(''X'') पर परिभाषित करता है। इसलिए एक [[तुल्यता संबंध]] को ''w'' ~ ''v'' द्वारा परिभाषित किया जा सकता है। जब ''w'' ≤<sub>~</sub> ''v'' and ''v'' ≤<sub>~</sub> ''w'' तब कोई यह दिखा सकता है कि आंशिक रूप से आदेशित भागफल समुच्चय 'W'(X)/~ मुक्त परिबद्ध जालक FX है।<ref>{{cite journal |last1=Whitman |first1=Philip M.|author-link=Philip M. Whitman |title=मुक्त जाली|journal=The Annals of Mathematics |date=January 1941 |volume=42 |issue=1 |pages=325–329 |doi=10.2307/1969001|jstor=1969001}}</ref><ref>{{Cite journal|doi = 10.2307/1968883|jstor = 1968883|last1 = Whitman|first1 = Philip M.|title = मुक्त जाली II|journal = Annals of Mathematics|year = 1942|volume = 43|issue = 1|pages = 104–115}}</ref> W(''X'')/~ के समतुल्य वर्ग सभी शब्दों ''w'' और ''v'' के साथ ''w'' ≤<sub>~</sub> ''v'' और ''v'' ≤<sub>~</sub> ''w'' के समुच्चय हैं। 'W'(X) में दो सुगठित शब्द v और w प्रत्येक बंधे हुए जालक में समान मान को दर्शाते हैं। यदि और केवल यदि ''w'' ≤<sub>~</sub> ''v'' और ''v'' ≤<sub>~</sub> ''w'' उपरोक्त आगमनात्मक परिभाषा का उपयोग करके बाद की स्थितियों को प्रभावी ढंग से तैयार किया जा सकता है। सारणी यह दिखाने के लिए एक उदाहरण संगणना दिखाती है कि x∧z और x∧z∧(x∨y) शब्द प्रत्येक बंधे हुए जालक में समान मान को दर्शाते हैं। जालक के स्थितियों ऊपर के निर्माण में, जो बंधे नहीं हैं, नियम 2 और 3 को छोड़कर ≤<sub>~</sub> उसी प्रकार से व्यवहार किया जाता है।
@@ Line 163: / Line 163: @@
 ब्लासियस और बर्कर्ट समूहों के लिए एक स्वयंसिद्ध समूह पर नुथ-बेंडिक्स एल्गोरिथम प्रदर्शित करें।
-एल्गोरिथ्म एक [[संगम (सार पुनर्लेखन)]] और सार पुनर्लेखन प्रणाली समाप्ति और अभिसरण पुनर्लेखन प्रणाली  शब्द पुनर्लेखन प्रणाली उत्पन्न करता है। जो प्रत्येक शब्द को एक अद्वितीय [[सामान्य रूप (सार पुनर्लेखन)]] में बदल देता है।<ref>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.</ref> पुनर्लेखन नियमों को अस्पष्ट रूप से क्रमांकित किया गया है क्योंकि कुछ नियम नष्ट हो गए थे और एल्गोरिथम रन के समय हटा दिए गए थे।
+एल्गोरिथ्म एक [[संगम (सार पुनर्लेखन)]] और सार पुनर्लेखन प्रणाली समाप्ति और अभिसरण पुनर्लेखन प्रणाली शब्द पुनर्लेखन प्रणाली उत्पन्न करता है। जो प्रत्येक शब्द को एक अद्वितीय [[सामान्य रूप (सार पुनर्लेखन)]] में बदल देता है।<ref>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.</ref> पुनर्लेखन नियमों को अस्पष्ट रूप से क्रमांकित किया गया है क्योंकि कुछ नियम नष्ट हो गए थे और एल्गोरिथम रन के समय हटा दिए गए थे।
 दो शब्दों की समानता स्वयंसिद्धों से होती है। यदि और केवल यदि दोनों शब्दों को शाब्दिक रूप से समान सामान्य रूप में रूपांतरित किया जाता है। उदाहरण के लिए, नियम
@@ Line 170: / Line 170: @@
 समान सामान्य रूप साझा करें अर्थात। <math>1</math>। इसलिए दोनों शब्द प्रत्येक समूह में समान हैं।
-एक अन्य उदाहरण के रूप में शब्द <math>1 \cdot (a \cdot b)</math> और <math>b \cdot (1 \cdot a)</math> सामान्य रूप  क्रमश <math>a \cdot b</math> और <math>b \cdot a</math>, है । चूँकि सामान्य रूप वस्तुतः भिन्न होते हैं। मूल शब्द प्रत्येक समूह में समान नहीं हो सकते। वास्तविक रूप में वे सामान्यतः[[एबेलियन समूह]] गैर-एबेलियन समूहों में भिन्न होते हैं।
+एक अन्य उदाहरण के रूप में शब्द <math>1 \cdot (a \cdot b)</math> और <math>b \cdot (1 \cdot a)</math> सामान्य रूप क्रमश <math>a \cdot b</math> और <math>b \cdot a</math>, है । चूँकि सामान्य रूप वस्तुतः भिन्न होते हैं। मूल शब्द प्रत्येक समूह में समान नहीं हो सकते। वास्तविक रूप में वे सामान्यतः[[एबेलियन समूह]] गैर-एबेलियन समूहों में भिन्न होते हैं।
 {| style="border: 1px solid grey; float: left; margin: 1em 1em;"
@@ Line 202: / Line 202: @@
 | '''R14''' || <math>x \cdot (x^{-1} \cdot y) </math> || <math>\rightsquigarrow  y</math>
 |-
-| '''R17'''  &nbsp; &nbsp; || <math>(x \cdot y)^{-1} </math> || <math>\rightsquigarrow  y^{-1} \cdot x^{-1}</math>
+| '''R17''' &nbsp; &nbsp; || <math>(x \cdot y)^{-1} </math> || <math>\rightsquigarrow  y^{-1} \cdot x^{-1}</math>
 |}
 == यह भी देखें ==
@@ Line 212: / Line 212: @@
 {{Authority control}}
-[[Category: सार बीजगणित]] [[Category: शब्दों पर कॉम्बिनेटरिक्स]] [[Category: पुनर्लेखन प्रणाली]] [[Category: कम्प्यूटेशनल समस्याएं]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:CS1 English-language sources (en)]]
-[[Category: Machine Translated Page]]
+[[Category:CS1 maint]]
+[[Category:CS1 русский-language sources (ru)]]
 [[Category:Created On 21/03/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]]
+[[Category:कम्प्यूटेशनल समस्याएं]]
+[[Category:पुनर्लेखन प्रणाली]]
+[[Category:शब्दों पर कॉम्बिनेटरिक्स]]
+[[Category:सार बीजगणित]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 18:41, 21 April 2023

Contents

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

इतिहास

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

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 18:41, 21 April 2023

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

इतिहास

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

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories