शब्द समस्या (गणित): 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]

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

@@ 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> पूर्णांक # बीजगणितीय गुणों में एक शब्द समस्या है | पूर्णांक समूह ℤ,
+जबकि शब्द समस्या पूछती है कि क्या स्थिरांक (गणित) वाले दो शब्द समान हैं। शब्द समस्या का एक उचित विस्तार, जिसे [[एकीकरण (कंप्यूटर विज्ञान)]] के रूप में जाना जाता है, पूछता है कि क्या दो शब्द <math>t_1,t_2</math> वेरिएबल (गणित) वाले ऐसे उदाहरण हैं। जो बराबर हैं या दूसरे शब्दों में समीकरण <math>t_1 = t_2</math> हैं। एक सामान्य उदाहरण के रूप में <math>2 + 3 \stackrel{?}{=} 8 + (-3)</math> पूर्णांक बीजगणितीय गुणों में शब्द समस्या है। पूर्णांक समूह ℤ है।
-जबकि <math>2 + x \stackrel{?}{=} 8 + (-x)</math> एक ही समूह में एकीकरण की समस्या है; चूंकि पूर्व शर्तें ℤ में बराबर होती हैं, बाद की समस्या में [[प्रतिस्थापन (तर्क)]] होता है <math>\{x \mapsto 3\}</math> एक समाधान के रूप में।
+जबकि <math>2 + x \stackrel{?}{=} 8 + (-x)</math> एक ही समूह में एकीकरण की समस्या है। चूंकि पूर्व नियम ℤ में बराबर होती हैं। बाद की समस्या में [[प्रतिस्थापन (तर्क)]] <math>\{x \mapsto 3\}</math> एक समाधान के रूप में होता है।
 == इतिहास ==
-शब्द समस्या के सबसे गहन अध्ययन वाले स्थितियों में से एक [[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>
+शब्द समस्या के सबसे गहन अध्ययन वाले स्थितियों में से एक [[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={{Start date|1910}}|event=[[Axel Thue]] poses a general problem of term rewriting on tree-like structures. He states "A solution of this problem in the most general case may perhaps be connected with unsurmountable difficulties".<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=Trees and term rewriting in 1910: on a paper by Axel Thue |journal=Bulletin of the European Association for Theoretical Computer Science|volume=72|pages=256–269 |date=2000|mr=1798015|citeseerx=10.1.1.32.8993 |language=English}}</ref>}}
+* 1910: एक्सल थू ने पेड़ जैसी संरचनाओं पर शब्द पुनर्लेखन की एक सामान्य समस्या पेश की। वह कहते हैं कि "सबसे सामान्य स्थितियों में इस समस्या का समाधान संभवतः अनगिनत कठिनाइयों से जुड़ा हो सकता है"।
-* {{Timeline-event |date={{Start date|1911}}|event=[[Max Dehn]] poses the word problem for finitely presented groups.<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={{Start date|1912}}|event=Dehn presents [[Dehn's algorithm]], and proves it solves the word problem for the [[fundamental group]]s of closed orientable two-dimensional manifolds of genus greater than or equal to 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> Subsequent authors have greatly extended it to a wide range of group theoretic [[decision problem]]s.<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>}}
+* 1911: मैक्स डेह्न ने अंतिम रूप से प्रस्तुत समूहों के लिए शब्द समस्या प्रस्तुत की।
-* {{Timeline-event |date={{Start date|1914}}|event=[[Axel Thue]] poses the word problem for finitely presented semigroups.<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={{Start date|1930}}|end_date={{End date|1938}}|event=The [[Church-Turing thesis]] emerges, defining formal notions of computability and undecidability.<ref>See [[History of the Church–Turing thesis]]. The dates are based on [[On Formally Undecidable Propositions of Principia Mathematica and Related Systems]] and [[Systems of Logic Based on Ordinals]].</ref>}}
+* 1912: डेन के एल्गोरिथ्म को प्रस्तुत करता है और यह सिद्ध करता है कि यह 2 से अधिक या उसके बराबर जीनस के बंद उन्मुख द्वि-आयामी कई गुना के मौलिक समूहों के लिए शब्द समस्या को हल करता है। बाद के लेखकों ने समूह सैद्धांतिक निर्णय समस्याओं की एक विस्तृत श्रृंखला के लिए इसे अधिक विस्तारित किया है।
-* {{Timeline-event |date={{Start date|1947}}|event=[[Emil Post]] and [[Andrey Markov Jr.]] independently construct finitely presented semigroups with unsolvable word problem.<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=A. Markov. Névožmoinost' nékotoryh algoritmov v téorii associativnyh sistém (Impossibility of certain algorithms in the theory of associative systems). Doklady Akadémii Nauk SSSR, vol. 77 (1951), pp. 19–20. |journal=Journal of Symbolic Logic |date=September 1951 |volume=16 |issue=3 |pages=215 |doi=10.2307/2266407|jstor=2266407 }}</ref> Post's construction is built on Turing machines while Markov's uses Post's normal systems.<ref name=Miller/>}}
-* {{Timeline-event |date={{Start date|1950}}|event=[[Alan Turing]] shows the word problem for cancellation semigroups is unsolvable,<ref>{{cite journal |last1=Turing |first1=A. M. |title=The Word Problem in Semi-Groups With Cancellation |journal=The Annals of Mathematics |date=September 1950 |volume=52 |issue=2 |pages=491–505 |doi=10.2307/1969481|jstor=1969481 }}</ref> by furthering Post’s construction. The proof is difficult to follow but marks a turning point in the word problem for groups.{{r|Miller|p=342}}}}
+* 1914: एक्सल थू ने सूक्ष्म रूप से प्रस्तुत अर्धसमूहों के लिए शब्द समस्या प्रस्तुत की।
-* {{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>}}
+* 1930 - 1938: चर्च-ट्यूरिंग थीसिस उभरती है। संगणनीयता और अनिर्वचनीयता की औपचारिक धारणाओं को परिभाषित करती है।
-* {{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>}}
+* 1947: एमिल पोस्ट और एंड्री मार्कोव जूनियर स्वतंत्र रूप से अघुलनशील शब्द समस्या के साथ सूक्ष्म रूप से प्रस्तुत अर्धसमूहों का निर्माण करते हैं। पोस्ट का निर्माण ट्यूरिंग मशीनों पर किया गया है। जबकि मार्कोव पोस्ट के सामान्य प्रणाली का उपयोग करता है।
-* {{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>}}
+* 1950: पोस्ट के निर्माण को आगे बढ़ाकर एलन ट्यूरिंग दिखाते हैं कि नष्ट किए गए सेमीग्रुप्स के लिए शब्द समस्या अघुलनशील है। प्रमाणन का पालन करना कठिन है। किन्तु समूहों के लिए शब्द समस्या में एक महत्वपूर्ण मोड़ है।
-* {{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>}}
+* 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>
+इसी प्रकार (अनटाइप्ड) [[लैम्ब्डा कैलकुलस]] में अनिवार्य रूप से एक ही समस्या है। दो अलग-अलग लैम्ब्डा एक्सप्रेशन दिए गए हैं। कोई एल्गोरिथ्म नहीं है, जो यह बता सके कि वे समकक्ष हैं या नहीं। लैम्ब्डा कैलकुलस तुल्यता की अनिश्चितता लैम्ब्डा कैलकुस के कई टाइप किए गए रूपों के लिए सामान्य रूपों की तुलना करके समानता निर्णायक है।
 == सार पुनर्लेखन प्रणाली के लिए शब्द समस्या ==
-[[File:Solving the word problem without and with completion_svg.svg|thumb|शब्द समस्या को हल करना: यदि तय करना <math>x \stackrel{*}{\leftrightarrow} y</math> आमतौर पर अनुमानी खोज की आवश्यकता होती है ({{color|#c00000|red}}, {{color|#00c000|green}}), निर्णय लेते समय <math>x\downarrow = y\downarrow</math> सीधा है ({{color|#808080|grey}}).]]अमूर्त पुनर्लेखन प्रणाली (ARS) के लिए शब्द समस्या काफी संक्षिप्त है: दी गई वस्तुएँ 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> ARS के लिए शब्द समस्या सामान्य रूप से अनिर्णीत समस्या है। हालाँकि, विशिष्ट मामले में शब्द समस्या के लिए एक संगणनीय कार्य समाधान है जहाँ प्रत्येक वस्तु एक विशिष्ट सामान्य रूप में चरणों की एक सीमित संख्या में घट जाती है (अर्थात प्रणाली अभिसारी है): दो वस्तुएँ समतुल्य हैं <math>\stackrel{*}{\leftrightarrow}</math> अगर और केवल अगर वे एक ही सामान्य रूप में कम हो जाते हैं।<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>
-Knuth-Bendix पूर्णता एल्गोरिथम का उपयोग समीकरणों के एक समूह को अभिसरण [[शब्द पुनर्लेखन प्रणाली]] में बदलने के लिए किया जा सकता है।
+नुथ-बेंडिक्स पूर्णता एल्गोरिथम का उपयोग समीकरणों के एक समूह को अभिसरण [[शब्द पुनर्लेखन प्रणाली]] में बदलने के लिए किया जा सकता है।
 == [[सार्वभौमिक बीजगणित]] में शब्द समस्या ==
-सार्वभौमिक बीजगणित में एक बीजीय संरचनाओं का अध्ययन करता है जिसमें एक [[जनरेटिंग सेट|जनरेटिंग समूह]] A, परिमित arity (आमतौर पर बाइनरी ऑपरेशंस) के A पर संचालन का एक संग्रह होता है, और पहचान का एक परिमित समूह होता है जिसे इन ऑपरेशनों को पूरा करना चाहिए। एक बीजगणित के लिए शब्द समस्या तब निर्धारित करने के लिए है, दो भाव (शब्द) दिए गए हैं जिनमें जनरेटर और संचालन शामिल हैं, चाहे वे बीजगणित मॉड्यूलो के समान तत्व का प्रतिनिधित्व करते हों। समूहों और अर्धसमूहों के लिए शब्द समस्याओं को बीजगणित के लिए शब्द समस्याओं के रूप में अभिव्यक्त किया जा सकता है।<ref name=Evans/>
+सार्वभौमिक बीजगणित में बीजीय संरचनाओं का अध्ययन करता है। जिसमें एक [[जनरेटिंग सेट|जनरेटिंग समूह]] A, परिमित एरिटी (सामान्यतः बाइनरी ऑपरेशंस) के 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> एकमात्र ज्ञात परिणाम यह है कि एक जनरेटर पर मुफ्त हेटिंग बीजगणित अनंत है, और यह कि एक जनरेटर पर मुक्त पूर्ण हेटिंग बीजगणित मौजूद है (और मुक्त हेटिंग बीजगणित की तुलना में एक और तत्व है)।
+मुक्त हेटिंग बीजगणित पर शब्द समस्या कठिन है।<ref>Peter T. Johnstone, ''Stone Spaces'', (1982) Cambridge University Press, Cambridge, {{isbn|0-521-23893-5}}. ''(See chapter 1, paragraph 4.11)''</ref> एकमात्र ज्ञात परिणाम यह है कि एक जनरेटर पर मुफ्त हेटिंग बीजगणित अनंत है और यह कि एक जनरेटर पर मुक्त पूर्ण हेटिंग बीजगणित उपस्थित है (और मुक्त हेटिंग बीजगणित की तुलना में एक और तत्व है)।
-==मुक्त जाली के लिए शब्द समस्या==
+==मुक्त जालक के लिए शब्द समस्या==
 {| style="float:right; border: 1px solid #808080"
-|+ Example computation of ''x''∧''z'' ~ ''x''∧''z''∧(''x''∨''y'')
+|+ उदाहरण की गणना ''x''∧''z'' ~ ''x''∧''z''∧(''x''∨''y'')
 |-
 |
@@ Line 72: / Line 91: @@
 | align="right"|''x''∧''z''∧(''x''∨''y'') || ≤<sub>~</sub> || ''x''∧''z''
 |-
-| by 5.
+|5 के द्वारा
-| since
+|तब से
 | align="right"|''x''∧''z'' || ≤<sub>~</sub> || ''x''∧''z''
 |-
-| by 1.
+| 1के द्वारा
-| since
+|तब से
 | align="right"|''x''∧''z'' || = || ''x''∧''z''
 |-
@@ Line 91: / Line 110: @@
 | align="right"| ''x''∧''z'' || ≤<sub>~</sub> || ''x''∧''z''∧(''x''∨''y'')
 |-
-| by 7.
+| 7 के द्वारा
-| since
+|तब से
 | align="right"|''x''∧''z'' || ≤<sub>~</sub> || ''x''∧''z''
-| and
+| और
 |
 |
 | align="right"|''x''∧''z'' || ≤<sub>~</sub> || ''x''∨''y''
 |-
-| by 1.
+| 1 के द्वारा
-| since
+|तब से
 | align="right"|''x''∧''z'' || = || ''x''∧''z''
 |
-| by 6.
+| 6 के द्वारा
-| since
+|तब से
 | align="right"|''x''∧''z'' || ≤<sub>~</sub> || ''x''
 |-
@@ Line 111: / Line 130: @@
 |  ||   ||
 |
-| by 5.
+| 5 के द्वारा
-| since
+|तब से
 | align="right"|''x'' || ≤<sub>~</sub> || ''x''
 |-
@@ Line 119: / Line 138: @@
 |  ||   ||
 |
-| by 1.
+| 1 के द्वारा
-| since
+|तब से
 | align="right"|''x'' || = || ''x''
 |}
 |}
-[[मुक्त जाली]] और अधिक आम तौर पर मुक्त [[जाली (आदेश)]] पर शब्द समस्या का एक निर्णायक समाधान है। बाउंडेड लैटिस दो बाइनरी ऑपरेशंस ∨ और ∧ और दो स्थिरांक (शून्य संचालन) 0 और 1 के साथ बीजगणितीय संरचनाएं हैं। सभी अच्छी प्रकार से गठित शब्द (लॉजिक) का समूह जो दिए गए समूह से तत्वों पर इन ऑपरेशंस का उपयोग करके तैयार किया जा सकता है जेनरेटर एक्स को 'डब्ल्यू' (एक्स) कहा जाएगा। शब्दों के इस समूह में कई अभिव्यक्तियां होती हैं जो प्रत्येक जाली में समान मूल्यों को दर्शाती हैं। उदाहरण के लिए, यदि a, X का कोई अवयव है, तो a ∨ 1 = 1 और a∧ 1 =a। मुक्त परिबद्ध जाली के लिए शब्द समस्या यह निर्धारित करने की समस्या है कि 'डब्ल्यू' (एक्स) के इन तत्वों में से कौन सा तत्व मुक्त बाध्य जाली एफएक्स में समान तत्व को दर्शाता है, और इसलिए हर बाध्य जाली में।
+[[मुक्त जाली|मुक्त जालक]] और अधिक सामान्यतःमुक्त [[जाली (आदेश)|जालक (आदेश)]] पर शब्द समस्या का एक निर्णायक समाधान है। बाउंडेड लैटिस दो बाइनरी ऑपरेशंस ∨ और ∧ और दो स्थिरांक (शून्य संचालन) 0 और 1 के साथ बीजगणितीय संरचनाएं हैं। सभी अच्छी प्रकार से गठित शब्द (लॉजिक) का समूह जो दिए गए समूह से तत्वों पर इन ऑपरेशंस का उपयोग करके तैयार किया जा सकता है। जेनरेटर ''X'' को '''W'''(''X'') कहा जाएगा। शब्दों के इस समूह में कई अभिव्यक्तियां होती हैं जो प्रत्येक जालक में समान मूल्यों को दर्शाती हैं। उदाहरण के लिए यदि a, X का कोई अवयव है। तो a ∨ 1 = 1 और a∧ 1 =a मुक्त परिबद्ध जालक के लिए शब्द समस्या यह निर्धारित करने की समस्या है कि '''W'''(''X'') के इन तत्वों में से कौन सा तत्व मुक्त बाध्य जालक ''FX'' में समान तत्व को दर्शाता है और इसलिए प्रत्येक बाध्य जालक में उपस्थित होगा।
-शाब्दिक समस्या का समाधान इस प्रकार किया जा सकता है। एक रिश्ता ≤<sub>~</sub> W(''X'') पर ''w'' ≤ समूह करके गणितीय आगमन को परिभाषित किया जा सकता है<sub>~</sub> v यदि और केवल यदि निम्न में से कोई एक धारण करता है:
+शाब्दिक समस्या का समाधान इस प्रकार किया जा सकता है कि एक संबंध ≤<sub>~</sub> W(''X'') पर ''w'' ≤ समूह करके <sub>~</sub> v गणितीय आगमन को परिभाषित किया जा सकता है। यदि और केवल यदि निम्न में से कोई एक धारण करता है:
-#   w = v (इसे उस स्थिति तक सीमित रखा जा सकता है जहां w और v X के अवयव हैं),
+#   w = v (इसे उस स्थिति तक सीमित रखा जा सकता है। जहां w और v X के अवयव हैं),
-#   डब्ल्यू = 0,
+#   w = 0,
-#   वी = 1,
+#   v = 1,
-#   डब्ल्यू = डब्ल्यू<sub>1</sub> ∨ में<sub>2</sub> और दोनों डब्ल्यू<sub>1</sub> ≤<sub>~</sub> वी और डब्ल्यू<sub>2</sub> ≤<sub>~</sub> वी पकड़,
+#   w = ''w''<sub>1</sub> ∨ ''w''<sub>2</sub> और दोनों ''w''<sub>1</sub> ≤<sub>~</sub> ''v'' और ''w''<sub>2</sub> ≤<sub>~</sub> ''v'' पकड़ती है।
-#   डब्ल्यू = डब्ल्यू<sub>1</sub> ∧ में<sub>2</sub> और या तो डब्ल्यू<sub>1</sub> ≤<sub>~</sub> वी या डब्ल्यू<sub>2</sub> ≤<sub>~</sub> वी रखती है,
+#   w = ''w''<sub>1</sub> ∧ ''w''<sub>2</sub> और या ''w''<sub>1</sub> ≤<sub>~</sub> ''v'' या ''w''<sub>2</sub> ≤<sub>~</sub> ''v'' पकड़ती है।
-#   वी = वी<sub>1</sub> ∨ वि<sub>2</sub> और या तो डब्ल्यू ≤<sub>~</sub> v<sub>1</sub> या डब्ल्यू ≤<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> पकड़ती है।
-#   वी = वी<sub>1</sub> ∧ वि<sub>2</sub> और दोनों डब्ल्यू ≤<sub>~</sub> v<sub>1</sub> और डब्ल्यू ≤<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> पकड़ती है।
-यह एक [[पूर्व आदेश]] ≤ परिभाषित करता है<sub>~</sub> W(''X'') पर, इसलिए एक [[तुल्यता संबंध]] को ''w'' ~ ''v'' द्वारा परिभाषित किया जा सकता है जब ''w'' ≤<sub>~</sub> वी और वी ≤<sub>~</sub> डब्ल्यू तब कोई यह दिखा सकता है कि आंशिक रूप से आदेशित भागफल समुच्चय '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> वी और वी ≤<sub>~</sub> डब्ल्यू 'W'(X) में दो सुगठित शब्द v और w प्रत्येक बंधे हुए जाली में समान मान को दर्शाते हैं यदि और केवल यदि w ≤<sub>~</sub> वी और वी ≤<sub>~</sub> डब्ल्यू; उपरोक्त आगमनात्मक परिभाषा का उपयोग करके बाद की स्थितियों को प्रभावी ढंग से तय किया जा सकता है। तालिका यह दिखाने के लिए एक उदाहरण संगणना दिखाती है कि 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> उसी प्रकार से व्यवहार किया जाता है।
-== उदाहरण: मुक्त समूह == में शब्द समस्या तय करने के लिए एक शब्द पुनर्लेखन प्रणाली
-ब्लासियस और बर्कर्ट
+'''<big>उदाहरण: मुक्त समूह में शब्द समस्या निर्धारित करने के लिए एक शब्द पुनर्लेखन प्रणाली</big>'''
   <ref>{{cite book| title=कटौती प्रणाली| year=1992| pages=291| publisher=Oldenbourg| editor=K. H. Bläsius and H.-J. Bürckert}}; here: p.126, 134</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> पुनर्लेखन नियमों को अस्पष्ट रूप से क्रमांकित किया गया है क्योंकि कुछ नियम बेमानी हो गए थे और एल्गोरिथम रन के दौरान हटा दिए गए थे।
-दो शब्दों की समानता स्वयंसिद्धों से होती है यदि और केवल यदि दोनों शब्दों को शाब्दिक रूप से समान सामान्य रूप में रूपांतरित किया जाता है। उदाहरण के लिए, शर्तें
+एल्गोरिथ्म एक [[संगम (सार पुनर्लेखन)]] और सार पुनर्लेखन प्रणाली समाप्ति और अभिसरण पुनर्लेखन प्रणाली शब्द पुनर्लेखन प्रणाली उत्पन्न करता है। जो प्रत्येक शब्द को एक अद्वितीय [[सामान्य रूप (सार पुनर्लेखन)]] में बदल देता है।<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> पुनर्लेखन नियमों को अस्पष्ट रूप से क्रमांकित किया गया है क्योंकि कुछ नियम नष्ट हो गए थे और एल्गोरिथम रन के समय हटा दिए गए थे।
+दो शब्दों की समानता स्वयंसिद्धों से होती है। यदि और केवल यदि दोनों शब्दों को शाब्दिक रूप से समान सामान्य रूप में रूपांतरित किया जाता है। उदाहरण के लिए, नियम
 :<math>((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</math>, और
 :<math>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</math>
-समान सामान्य रूप साझा करें, अर्थात। <math>1</math>; इसलिए दोनों शब्द हर समूह में समान हैं।
+समान सामान्य रूप साझा करें अर्थात। <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;"
-|+ Group axioms used in Knuth–Bendix completion
+|+ नुथ-बेंडिक्स पूर्णता में प्रयुक्त समूह अभिगृहीत
 |-
 | '''A1''' || <math>1 \cdot x</math> || <math>= x</math>
@@ Line 160: / Line 182: @@
 |}
 {| style="border: 1px solid grey; float: left; margin: 1em 1em;"
-|+ Term rewrite system obtained from Knuth–Bendix completion
+|+ नुथ-बेंडिक्स पूर्णता से प्राप्त शब्द पुनर्लेखन प्रणाली
 |-
 | '''R1''' || <math>1 \cdot x </math> || <math>\rightsquigarrow  x</math>
@@ Line 180: / 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>
 |}
-{{clear}}
 == यह भी देखें ==
 *[[संयुग्मन समस्या]]
@@ Line 192: / Line 212: @@
 {{Authority control}}
-[[Category: सार बीजगणित]] [[Category: शब्दों पर कॉम्बिनेटरिक्स]] [[Category: पुनर्लेखन प्रणाली]] [[Category: कम्प्यूटेशनल समस्याएं]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:CS1 English-language sources (en)]]
+[[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

Latest revision as of 18:41, 21 April 2023

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

इतिहास

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

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories