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

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\}$ एक समाधान के रूप में।

इतिहास

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

• 1910 (1910): 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".
• 1911 (1911): Max Dehn poses the word problem for finitely presented groups.
• 1912 (1912): Dehn presents Dehn's algorithm, and proves it solves the word problem for the fundamental groups of closed orientable two-dimensional manifolds of genus greater than or equal to 2. Subsequent authors have greatly extended it to a wide range of group theoretic decision problems.
• 1914 (1914): Axel Thue poses the word problem for finitely presented semigroups.
• 1930 (1930) – 1938 (1938): The Church-Turing thesis emerges, defining formal notions of computability and undecidability.
• 1947 (1947): Emil Post and Andrey Markov Jr. independently construct finitely presented semigroups with unsolvable word problem. Post's construction is built on Turing machines while Markov's uses Post's normal systems.
• 1950 (1950): Alan Turing shows the word problem for cancellation semigroups is unsolvable, by furthering Post’s construction. The proof is difficult to follow but marks a turning point in the word problem for groups.
• 1955 (1955): Pyotr Novikov gives the first published proof that the word problem for groups is unsolvable, using Turing’s cancellation semigroup result. The proof contains a "Principal Lemma" equivalent to Britton's Lemma.
• 1954 (1954) – 1957 (1957): William Boone independently shows the word problem for groups is unsolvable, using Post's semigroup construction.
• 1957 (1957) – 1958 (1958): 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. An early version of Britton's Lemma appears.
• 1958 (1958) – 1959 (1959): Boone publishes a simplified version of his construction.
• 1961 (1961): Graham Higman characterises the subgroups of finitely presented groups with Higman's embedding theorem, connecting recursion theory with group theory in an unexpected way and giving a very different proof of the unsolvability of the word problem.
• 1961 (1961) – 1963 (1963): Britton presents a greatly simplified version of Boone's 1959 proof that the word problem for groups is unsolvable. 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.
• 1977 (1977): Gennady Makanin proves that the existential theory of equations over free monoids is solvable.

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

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

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

Main article: Word problem for groups

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

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

Main article: Combinatory logic § Undecidability of combinatorial calculus

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Group axioms used in Knuth–Bendix completion

A1	$1\cdot x$	$=x$
A2	$x^{-1}\cdot x$	$=1$
A3	$(x\cdot y)\cdot z$	$=x\cdot (y\cdot z)$

Term rewrite system obtained from Knuth–Bendix completion

R1	$1\cdot x$	$\rightsquigarrow x$
R2	$x^{-1}\cdot x$	$\rightsquigarrow 1$
R3	$(x\cdot y)\cdot z$	$\rightsquigarrow x\cdot (y\cdot z)$
R4	$x^{-1}\cdot (x\cdot y)$	$\rightsquigarrow y$
R8	$1^{-1}$	$\rightsquigarrow 1$
R11	$x\cdot 1$	$\rightsquigarrow x$
R12	$(x^{-1})^{-1}$	$\rightsquigarrow x$
R13	$x\cdot x^{-1}$	$\rightsquigarrow 1$
R14	$x\cdot (x^{-1}\cdot y)$	$\rightsquigarrow y$
R17	$(x\cdot y)^{-1}$	$\rightsquigarrow y^{-1}\cdot x^{-1}$

यह भी देखें

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