शब्द समस्या (गणित)

This article is about गणित और कंप्यूटर विज्ञान में एल्गोरिथम शब्द समस्याएँ. For अन्य प्रयोग, see शब्द समस्या.

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

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

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

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

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

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

इतिहास

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

• 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$ नियम लागू करें। ध्यान दें कि यहाँ पुनर्लेखन एक ओर है। शब्द समस्या सममित पुनर्लेखन संबंधों, अर्थात् थ्यू प्रणाली के लिए अभिगम्यता समस्या है।

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

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

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

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

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

Main article: कॉम्बिनेटर लॉजिक कॉम्बिनेटरियल कैलकुलस की अनिश्चितता

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

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

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

शब्द समस्या को हल करना: यदि निर्धारित करना $x{\stackrel {*}{\leftrightarrow }}y$ सामान्यतः अनुमानी खोज की आवश्यकता होती है। (लाल, हरा), निर्णय लेते समय $x\downarrow =y\downarrow$(ग्रे) सीधा है।

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

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

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

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

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

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

उदाहरण की गणना 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 गणितीय आगमन को परिभाषित किया जा सकता है। यदि और केवल यदि निम्न में से कोई एक धारण करता है:

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

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

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

ब्लासियस और बर्कर्ट समूहों के लिए एक स्वयंसिद्ध समूह पर नुथ-बेंडिक्स एल्गोरिथम प्रदर्शित करें।

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

दो शब्दों की समानता स्वयंसिद्धों से होती है। यदि और केवल यदि दोनों शब्दों को शाब्दिक रूप से समान सामान्य रूप में रूपांतरित किया जाता है। उदाहरण के लिए, नियम

$((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}$

यह भी देखें

• संयुग्मन समस्या
• समूह समरूपता समस्या