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

गणित में, विशेष रूप से सामान्य बीजगणित के क्षेत्र में जिसे संयोजक समूह सिद्धांत के रूप में जाना जाता है, एक अंतिम रूप से उत्पन्न समूह 'G' के लिए शब्द समस्या यह तय करने की एल्गोरिथम समस्या है कि जनरेटर में दो शब्द एक ही तत्व का प्रतिनिधित्व करते हैं या नहीं। अधिक सटीक रूप से, यदि A, G के लिए एक समूह के जनरेटिंग समुच्चय का एक परिमित समुच्चय है, तो शब्द समस्या A में सभी शब्दों की औपचारिक भाषा और एक औपचारिक समुच्चय के लिए सदस्यता समस्या है।व्युत्क्रमों का एक औपचारिक समुच्चय है जो मुक्त मोनोइड से प्राकृतिक मानचित्र के तहत पहचान के लिए मैप करता है। A पर समूह G में सम्मिलित होना। यदि B G के लिए एक और परिमित जनरेटिंग समुच्चय है, तो जनरेटिंग समुच्चय B पर शब्द समस्या उत्पन्न समुच्चय A पर शब्द समस्या के बराबर है। इस प्रकार कोई भी स्पष्ट रूप से उत्पन्न समूह 'G' के लिए शब्द समस्या की निर्णायकता के बारे में बात कर सकता है।

पुनरावर्ती प्रस्तुत समूहों के एक वर्ग 'K' के लिए संबंधित लेकिन अलग समान शब्द समस्या निर्णय लेने की एल्गोरिथम समस्या है, जिसे इनपुट के रूप में कक्षा में 'G' समूह के लिए समूह 'P' की प्रस्तुति के रूप में दिया गया है। K और G के जनरेटर में दो शब्द, क्या शब्द G के समान तत्व का प्रतिनिधित्व करते हैं। कुछ लेखकों को प्रस्तुतियों के पुनरावर्ती गणनीय समुच्चय द्वारा वर्ग K को परिभाषित करने की आवश्यकता होती है।

इतिहास

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

यह 1955 में पीटर नोविकोव द्वारा दिखाया गया था कि एक सूक्ष्म रूप से प्रस्तुत समूह G मौजूद है जैसे कि G के लिए शब्द समस्या अनिर्णीत समस्या है। यह तुरंत इस प्रकार है कि समान शब्द समस्या भी अनिर्णीत है। ध्यान दें कि संयुग्मन समस्या और शब्द समस्या के बीच एक साधारण संबंध है। यदि कोई एक विशेष समूह में संयुग्मन समस्या को हल कर सकता है तो कोई शब्द समस्या को हल कर सकता है। क्योंकि यदि कोई शब्द w सर्वसमिका के साथ संयुग्मित है, तो यह समूह की पहचान के बराबर है। देहान ने 1911 के इस पत्र में यह भी साबित किया कि एक अंतिम रूप से प्रस्तुत समूह का एक उपसमूह हो सकता है जो अंतिम रूप से प्रस्तुत नहीं किया गया हो। उन्होंने आइसोमोर्फिज्म समस्या और संपत्ति के साथ सूक्ष्म रूप से प्रस्तुत समूहों के लिए संयुग्मन समस्या को भी हल किया है कि प्रत्येक परिभाषित संबंधों में प्रत्येक जनरेटर अधिकतम दो बार होता है। 1958 में विलियम बून (गणितज्ञ) द्वारा एक अलग प्रमाण प्राप्त किया गया था।

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

यह महसूस करना महत्वपूर्ण है कि शब्द समस्या वास्तव में कई समूहों जी के लिए हल करने योग्य है। उदाहरण के लिए, बहुचक्रीय समूहों में हल करने योग्य शब्द समस्याएं हैं क्योंकि बहुचक्रीय प्रस्तुति में मनमाने शब्द का सामान्य रूप आसानी से गणना योग्य है; समूहों के लिए अन्य एल्गोरिदम, उपयुक्त परिस्थितियों में, शब्द समस्या को भी हल कर सकते हैं, टॉड-कॉक्सेटर एल्गोरिथम देखें और नुथ-बेंडिक्स पूर्णता एल्गोरिथम। दूसरी ओर, तथ्य यह है कि एक विशेष एल्गोरिथ्म किसी विशेष समूह के लिए शब्द समस्या को हल नहीं करता है, यह नहीं दर्शाता है कि समूह में एक अघुलनशील शब्द समस्या है। उदाहरण के लिए, देह का एल्गोरिथ्म टोरस्र्स के मौलिक समूह के लिए शब्द समस्या का समाधान नहीं करता है। हालाँकि यह समूह दो अनंत चक्रीय समूहों का प्रत्यक्ष उत्पाद है और इसलिए इसमें एक हल करने योग्य शब्द समस्या है।

एक अधिक ठोस विवरण

अधिक ठोस शब्दों में, शाब्दिक स्ट्रिंग्स के लिए समान शब्द समस्या को पुनर्लेखन प्रश्न के रूप में व्यक्त किया जा सकता है। एक समूह G की प्रस्तुति P के लिए, P एक निश्चित संख्या में जनरेटर निर्दिष्ट करेगा

x, y, z, ..

G के लिए। हमें x के लिए एक अक्षर और दूसरे (सुविधा के लिए) को x−1 द्वारा दर्शाए गए समूह तत्व के लिए प्रस्तुत करने की आवश्यकता है इन अक्षरों को (जनरेटरों से दुगुना) वर्णमाला कहें $\Sigma$ हमारी समस्या के लिए। तब G में प्रत्येक तत्व को किसी उत्पाद द्वारा किसी तरह से दर्शाया जाता है

abc....pqr

से प्रतीकों का $\Sigma$, कुछ लंबाई का, G में गुणा किया गया। लंबाई 0 की स्ट्रिंग (शून्य स्ट्रिंग) G के पहचान तत्व e के लिए है। पूरी समस्या का सार उन सभी तरीकों को पहचानने में सक्षम होना है, जिन्हें कुछ संबंधों को देखते हुए ई का प्रतिनिधित्व किया जा सकता है। .

G में संबंधों का प्रभाव ऐसे विभिन्न स्ट्रिंग्स को बनाना है जो G के समान तत्व का प्रतिनिधित्व करते हैं। वास्तव में संबंध स्ट्रिंग्स की एक सूची प्रदान करते हैं जिन्हें या तो जहां हम चाहते हैं वहां प्रस्तुत किया जा सकता है, या जब भी हम उन्हें देखते हैं, निरस्त कर सकते हैं, बिना 'बदले' मूल्य', अर्थात समूह तत्व जो गुणन का परिणाम है।

एक सरल उदाहरण के लिए, प्रस्तुति {a | a3} के व्युत्क्रम के लिए A लिखने पर, हमारे पास किसी भी संख्या के प्रतीकों a और A को मिलाने वाली संभावित स्ट्रिंग्स हैं। जब भी हम aa, या aA या Aa देखते हैं तो हम इन्हें हटा सकते हैं। हमें AAA को खत्म करना भी याद रखना चाहिए; यह कहता है कि चूँकि a का घन G का तत्समक तत्व है, इसलिए a के व्युत्क्रम का घन भी है। इन परिस्थितियों में शब्द समस्या आसान हो जाती है। पहले स्ट्रिंग्स को खाली स्ट्रिंग, A, AA, A या AA में कम करें। फिर ध्यान दें कि हम aaa से गुणा भी कर सकते हैं, इसलिए हम A को a में बदल सकते हैं और AA को a में बदल सकते हैं। परिणाम यह है कि शब्द समस्या, यहाँ क्रम तीन के चक्रीय समूह के लिए, हल करने योग्य है।

हालाँकि, यह विशिष्ट स्थिति नहीं है। उदाहरण के लिए, हमारे पास एक कैनोनिकल रूप उपलब्ध है जो किसी भी स्ट्रिंग को लम्बाई को कम से कम तीन तक कम कर देता है, लंबाई को मोनोटोनिक रूप से घटाकर। सामान्य तौर पर, यह सच नहीं है कि चरणबद्ध निरस्तीकरण द्वारा तत्वों के लिए एक विहित रूप प्राप्त किया जा सकता है। किसी को स्ट्रिंग को कई गुना बढ़ाने के लिए संबंधों का उपयोग करना पड़ सकता है, अंत में एक निरस्तीकरण खोजने के लिए जो लंबाई को नीचे लाता है।

परिणाम यह है कि सबसे खराब स्थिति में, स्ट्रिंग्स के बीच का संबंध जो कहता है कि वे G में बराबर हैं, एक अनिर्णीत समस्या है।

उदाहरण

निम्नलिखित समूहों में एक हल करने योग्य शब्द समस्या है:

• स्वचालित समूह, जिनमें सम्मिलित हैं:
  • परिमित समूह
  • नकारात्मक रूप से घुमावदार समूह|नकारात्मक रूप से घुमावदार (उर्फ हाइपरबोलिक) समूह
  • यूक्लिडियन समूह
  • कॉक्सेटर समूह
  • चोटी समूह
  • ज्यामितीय रूप से परिमित समूह
• निश्चित रूप से मुक्त समूह उत्पन्न हुए
• पूरी तरह से मुक्त एबेलियन समूह उत्पन्न हुए
• बहुचक्रीय समूह
• एक समूह की पूरी तरह से उत्पन्न पुनरावर्ती पूर्ण प्रस्तुति, शामिल:
  • सरल समूहों को सूक्ष्म रूप से प्रस्तुत किया गया।
• अंतिम रूप से अवशिष्ट रूप से परिमित समूहों को प्रस्तुत किया गया
• एक संबंधक समूह (यह मैग्नस का एक प्रमेय है), जिसमें सम्मिलित हैं:
  • बंद उन्मुख द्वि-आयामी कई गुना के मौलिक समूह।
• जुझारू समूह
• ऑटोस्टैकेबल समूह

अघुलनशील शब्द समस्याओं के उदाहरण भी जाने जाते हैं:

• सकारात्मक पूर्णांकों का पुनरावर्ती गणनीय समुच्चय A दिया गया है जिसमें अघुलनशील सदस्यता समस्या है, ⟨a,b,c,d | ए^{क्या?एन </सुप> = सीएनडीसीn : n ∈ A⟩ एक पुनरावर्ती गणना योग्य प्रस्तुति वाला एक अंतिम रूप से उत्पन्न समूह है जिसकी शब्द समस्या अघुलनशील है}
• पुनरावर्ती गणनीय प्रस्तुति और अघुलनशील शब्द समस्या के साथ प्रत्येक परिमित रूप से उत्पन्न समूह, अघुलनशील शब्द समस्या वाले सूक्ष्म रूप से प्रस्तुत समूह का एक उपसमूह है
• अघुलनशील शब्द समस्या वाले सूक्ष्म रूप से प्रस्तुत समूह में रिलेटर्स की संख्या 14 जितनी कम हो सकती है या 12 भी।
• कोलिन्स 1986 में अघुलनशील शब्द समस्या के साथ एक उचित लघु प्रस्तुति का एक स्पष्ट उदाहरण दिया गया है:

शब्द समस्या का आंशिक समाधान

पुनरावर्ती रूप से प्रस्तुत समूह के लिए शब्द समस्या को निम्नलिखित अर्थों में आंशिक रूप से हल किया जा सकता है:

एक समूह G के लिए एक पुनरावर्ती प्रस्तुति P = ⟨X|R⟩ को देखते हुए, परिभाषित करें:

$S=\{\langle u,v\rangle :u{\text{ and }}v{\text{ are words in }}X{\text{ and }}u=v{\text{ in }}G\ \}$

तो एक आंशिक पुनरावर्ती कार्य f है_Pऐसा है कि:

$f_{P}(\langle u,v\rangle )={\begin{cases}0&{\text{if}}\ \langle u,v\rangle \in S\\{\text{undefined/does not halt}}\ &{\text{if}}\ \langle u,v\rangle \notin S\end{cases}}$

अधिक अनौपचारिक रूप से, एक एल्गोरिथम है जो u = v होने पर रुक जाता है, लेकिन अन्यथा ऐसा नहीं करता है।

यह इस प्रकार है कि P के लिए शब्द समस्या को हल करने के लिए एक पुनरावर्ती फलन G बनाने के लिए पर्याप्त है:

$g(\langle u,v\rangle )={\begin{cases}0&{\text{if}}\ \langle u,v\rangle \notin S\\{\text{undefined/does not halt}}\ &{\text{if}}\ \langle u,v\rangle \in S\end{cases}}$

हालांकि u = v G में अगर और केवल अगर uv⁻¹=1 जी में। यह निम्नानुसार है कि P के लिए शब्द समस्या को हल करने के लिए यह एक पुनरावर्ती फलन h बनाने के लिए पर्याप्त है:

$h(x)={\begin{cases}0&{\text{if}}\ x\neq 1\ {\text{in}}\ G\\{\text{undefined/does not halt}}\ &{\text{if}}\ x=1\ {\text{in}}\ G\end{cases}}$

उदाहरण

इस तकनीक के उपयोग के उदाहरण के रूप में निम्नलिखित सिद्ध होंगे:

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

प्रमाण: मान लीजिए G = ⟨X|R⟩ एक परिमित रूप से प्रस्तुत, अवशिष्ट परिमित समूह है।

बता दें कि S, N के सभी क्रमपरिवर्तनों का समूह है, जो प्राकृतिक संख्याएँ हैं, जो सभी संख्याओं को ठीक करती हैं लेकिन अंत में कई संख्याएँ हैं:

1. S स्थानीय रूप से परिमित समूह है और इसमें प्रत्येक परिमित समूह की एक प्रति होती है।
2. क्रमपरिवर्तन के उत्पादों की गणना करके 's' में शब्द समस्या हल करने योग्य है।
3. परिमित समुच्चय 'एक्स' के सभी मैपिंग की 's' में एक पुनरावर्ती गणना है।
4. चूँकि G अवशिष्ट रूप से परिमित है, यदि w G के जेनरेटर X में एक शब्द है तो w ≠ 1 जी में अगर और केवल x के एस में कुछ मैपिंग एक होमोमोर्फिज्म को प्रेरित करता है s में w ≠ 1 ।
5. इन तथ्यों को देखते हुए, एल्गोरिथम निम्नलिखित स्यूडोकोड द्वारा परिभाषित किया गया है:

x में s के हर मैपिंग के लिए 'के लिए'
    'यदि' R का प्रत्येक संबंधक S में संतुष्ट है
        'अगर' w ≠ 1 s में
            'वापसी' 0
        'अगर अंत'
    'अगर अंत'
'के लिए अंत'

एक पुनरावर्ती फलन h को परिभाषित करता है जैसे कि:

$h(x)={\begin{cases}0&{\text{if}}\ x\neq 1\ {\text{in}}\ G\\{\text{undefined/does not halt}}\ &{\text{if}}\ x=1\ {\text{in}}\ G\end{cases}}$

इससे पता चलता है कि G की शब्द समस्या हल करने योग्य है।

समान शब्द समस्या की असम्बद्धता

एक समूह में शब्द समस्या की हल करने की क्षमता के लिए ऊपर दिए गए मानदंड को सीधे तर्क द्वारा बढ़ाया जा सकता है। यह सूक्ष्म रूप से प्रस्तुत समूहों के एक वर्ग के लिए शब्द समस्या की एकसमान विलेयता के लिए निम्नलिखित मानदंड देता है:

समूहों के वर्ग K के लिए समान शब्द समस्या को हल करने के लिए, यह एक पुनरावर्ती कार्य खोजने के लिए पर्याप्त है $f(P,w)$ यह एक समूह G और एक शब्द के लिए एक परिमित प्रस्तुति P लेता है $w$ Gके जनरेटर में, जैसे कि जब भी G ∈ K:

$f(P,w)={\begin{cases}0&{\text{if}}\ w\neq 1\ {\text{in}}\ G\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ G\end{cases}}$

बूने-रोजर्स प्रमेय: कोई समान आंशिक एल्गोरिदम नहीं है जो हल करने योग्य शब्द समस्या वाले सभी सूक्ष्म रूप से प्रस्तुत समूहों में शब्द समस्या को हल करता है।

दूसरे शब्दों में, हल करने योग्य शब्द समस्या वाले सभी सूक्ष्म रूप से प्रस्तुत समूहों की कक्षा के लिए समान शब्द समस्या हल करने योग्य नहीं है। इसके कुछ रोचक परिणाम हैं। उदाहरण के लिए, हिगमैन सन्निहित िंग प्रमेय का उपयोग एक ऐसे समूह के निर्माण के लिए किया जा सकता है जिसमें हल करने योग्य शब्द समस्या वाले प्रत्येक सूक्ष्म रूप से प्रस्तुत समूह की एक आइसोमोर्फिक प्रति हो। यह पूछना स्वाभाविक लगता है कि क्या इस समूह में हल करने योग्य शब्द समस्या हो सकती है। लेकिन यह बूने-रोजर्स परिणाम का परिणाम है कि:

उपप्रमेय: कोई सार्वभौमिक हल करने योग्य शब्द समस्या समूह नहीं है। अर्थात्, यदि G एक अंतिम रूप से प्रस्तुत समूह है जिसमें हल करने योग्य शब्द समस्या के साथ प्रत्येक सूक्ष्म रूप से प्रस्तुत समूह की एक आइसोमोर्फिक प्रति सम्मिलित है, तो G में स्वयं अघुलनशील शब्द समस्या होनी चाहिए।

टिप्पणी: मान लीजिए G = ⟨X|R⟩ हल करने योग्य शब्द समस्या वाला एक सूक्ष्म रूप से प्रस्तुत समूह है और H G का परिमित उपसमुच्चय है। चलो एच^* = ⟨H⟩, H द्वारा उत्पन्न समूह बनें। फिर H में शब्द समस्या^* हल करने योग्य है: H के जेनरेटर H में दो शब्द h, k दिए गए हैं^*, उन्हें X में शब्दों के रूप में लिखें और G में शब्द समस्या के समाधान का उपयोग करके उनकी तुलना करें। यह सोचना आसान है कि यह पूरी तरह से उत्पन्न वर्ग K (मान लीजिए) के लिए शब्द समस्या का एक समान समाधान प्रदर्शित करता है। ऐसे समूह जिन्हें G में सन्निहित किया जा सकता है। यदि ऐसा होता, तो एक सार्वभौमिक हल करने योग्य शब्द समस्या समूह का गैर-अस्तित्व बूने-रोजर्स से आसानी से अनुसरण करता। हालाँकि, K में समूहों के लिए शब्द समस्या के लिए अभी प्रदर्शित किया गया समाधान एक समान नहीं है। इसे देखने के लिए, एक समूह J = ⟨Y|T⟩ ∈ K; J में शब्द समस्या को हल करने के लिए उपरोक्त तर्क का उपयोग करने के लिए, पहले मैपिंग e: Y → G को प्रदर्शित करना आवश्यक है जो एक सन्निहित िंग e तक फैला हुआ है^*: J → G. यदि एक पुनरावर्ती कार्य होता है जो G में सन्निहित करने के लिए K में समूहों की प्रस्तुतियों को मैप (अंतिम रूप से उत्पन्न) करता है, तो K में शब्द समस्या का एक समान समाधान वास्तव में निर्मित किया जा सकता है। लेकिन सामान्य तौर पर, यह मानने का कोई कारण नहीं है कि ऐसा पुनरावर्ती कार्य मौजूद है। हालांकि, यह पता चला है कि, अधिक परिष्कृत तर्क का उपयोग करते हुए, J में शब्द समस्या को सन्निहित िंग E: J→ G का उपयोग किए बिना हल किया जा सकता है। इसके अतिरिक्त समरूपता की गणना का उपयोग किया जाता है, और चूंकि ऐसी गणना समान रूप से बनाई जा सकती है, यह K में शब्द समस्या का एक समान समाधान होता है।

प्रमाण है कि कोई सार्वभौमिक हल करने योग्य शब्द समस्या समूह नहीं है

मान लीजिए G एक सार्वभौमिक हल करने योग्य शब्द समस्या समूह थे। एक समूह H की एक परिमित प्रस्तुति P = ⟨X|R⟩ को देखते हुए, सभी होमोमोर्फिज्म h: H → G की पुनरावर्ती गणना कर सकते हैं, पहले सभी मैपिंग h की गणना करके^†: X → G. इन सभी मानचित्रणों का विस्तार समरूपता तक नहीं है, लेकिन, चूँकि h^†(R) परिमित है, G में शब्द समस्या के समाधान का उपयोग करके समरूपता और गैर-समरूपता के बीच अंतर करना संभव है। गैर-समरूपता को हटाने से आवश्यक पुनरावर्ती गणना मिलती हैh₁, h₂, ..., h_n, ... .

यदि H के पास हल करने योग्य शब्द समस्या है, तो इनमें से कम से कम एक समरूपता एक सन्निहित िंग होनी चाहिए। तो एच के जेनरेटर में एक शब्द W दिया गया है:

${\text{If}}\ w\neq 1\ {\text{in}}\ H,\ h_{n}(w)\neq 1\ {\text{in}}\ G\ {\text{for some}}\ h_{n}$

${\text{If}}\ w=1\ {\text{in}}\ H,\ h_{n}(w)=1\ {\text{in}}\ G\ {\text{for all}}\ h_{n}$

स्यूडोकोड द्वारा वर्णित एल्गोरिथम पर विचार करें:

माना कि 'n' = 0
    माना कि दोहराने योग्य = TRUE
        जबकि (दोहराने योग्य)
            n को 1 से बढ़ाएँ
            अगर ("G" में शब्द समस्या का समाधान "H" प्रकट करता हैn(w) ≠ 1 जी में)
                'माना कि' दोहराने योग्य = गलत
आउटपुट 0.

यह एक पुनरावर्ती कार्य का वर्णन करता है:

$f(w)={\begin{cases}0&{\text{if}}\ w\neq 1\ {\text{in}}\ H\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ H.\end{cases}}$

फलन f स्पष्ट रूप से प्रस्तुति P पर निर्भर करता है। इसे दो चरों का एक फलन मानते हुए, एक पुनरावर्ती फलन $f(P,w)$ का निर्माण किया गया है जो एक समूह H के लिए एक परिमित प्रस्तुति P लेता है और एक समूह G के जनरेटर में एक शब्द w लेता है, जैसे कि जब भी G में घुलनशील शब्द समस्या हो:

$f(P,w)={\begin{cases}0&{\text{if}}\ w\neq 1\ {\text{in}}\ H\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ H.\end{cases}}$

लेकिन यह समान रूप से बूने-रोजर्स के विपरीत, हल करने योग्य शब्द समस्या वाले सभी अंतिम रूप से प्रस्तुत समूहों के वर्ग के लिए शब्द समस्या को हल करता है। यह विरोधाभास सिद्ध करता है कि G का अस्तित्व नहीं हो सकता।

बीजगणितीय संरचना और शब्द समस्या

ऐसे कई परिणाम हैं जो शब्द समस्या की विलेयता और बीजगणितीय संरचना से संबंधित हैं। इनमें से सबसे महत्वपूर्ण बूने-हिगमैन प्रमेय है:

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

यह व्यापक रूप से माना जाता है कि निर्माण करना संभव होना चाहिए ताकि सरल समूह स्वयं को अंतिम रूप से प्रस्तुत किया जा सके। यदि ऐसा है तो यह अपेक्षा करना मुश्किल होगा क्योंकि प्रस्तुतियों से सरल समूहों तक मैपिंग को गैर-पुनरावर्ती होना होगा।

निम्नलिखित बर्नहार्ड न्यूमैन और एंगस मैकिनटायर द्वारा सिद्ध किया गया है:

एक सूक्ष्म रूप से प्रस्तुत समूह में हल करने योग्य शब्द समस्या है अगर और केवल अगर इसे बीजगणितीय रूप से बंद समूह में सन्निहित किया जा सकता है

इसके बारे में उल्लेखनीय बात यह है कि बीजगणितीय रूप से बंद समूह इतने जंगली हैं कि उनमें से किसी की भी पुनरावर्ती प्रस्तुति नहीं है।

शब्द समस्या की विलेयता के लिए बीजगणितीय संरचना से संबंधित सबसे पुराना परिणाम कुज़नेत्सोव का प्रमेय है:

एक पुनरावर्ती रूप से प्रस्तुत सरल समूह S में हल करने योग्य शब्द समस्या है।

इसे सिद्ध करने के लिए ⟨X|R⟩ को S के लिए एक पुनरावर्ती प्रस्तुति होने दें। एक ∈ S चुनें ताकि S में a ≠ 1 हो।

यदि डब्ल्यू एस के जेनरेटर एक्स पर एक शब्द है, तो दें:

$S_{w}=\langle X|R\cup \{w\}\rangle .$

एक पुनरावर्ती कार्य है $f_{\langle X|R\cup \{w\}\rangle }$ ऐसा है कि:

$f_{\langle X|R\cup \{w\}\rangle }(x)={\begin{cases}0&{\text{if}}\ x=1\ {\text{in}}\ S_{w}\\{\text{undefined/does not halt}}\ &{\text{if}}\ x\neq 1\ {\text{in}}\ S_{w}.\end{cases}}$

लिखना:

$g(w,x)=f_{\langle X|R\cup \{w\}\rangle }(x).$

तब क्योंकि f का निर्माण एकसमान था, यह दो चरों का पुनरावर्ती फलन है।

यह इस प्रकार है कि: $h(w)=g(w,a)$ रिकर्सिव है। निर्माण द्वारा:

$h(w)={\begin{cases}0&{\text{if}}\ a=1\ {\text{in}}\ S_{w}\\{\text{undefined/does not halt}}\ &{\text{if}}\ a\neq 1\ {\text{in}}\ S_{w}.\end{cases}}$

चूँकि S एक साधारण समूह है, इसके केवल भागफल समूह स्वयं और तुच्छ समूह हैं। चूँकि a ≠ 1 in S, हम देखते हैं a = 1 in S_wअगर और केवल अगर एस_wतुच्छ है अगर और केवल अगर w ≠ 1 एस में। इसलिए:

$h(w)={\begin{cases}0&{\text{if}}\ w\neq 1\ {\text{in}}\ S\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ S.\end{cases}}$

S के लिए शब्द समस्या हल करने योग्य सिद्ध करने के लिए इस तरह के एक फलन का अस्तित्व पर्याप्त है।

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

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

यह भी देखें

• शब्दों पर कॉम्बिनेटरिक्स
• वर्ग-सार्वभौमिक समूह
• शब्द समस्या (गणित)
• पहुंच क्षमता की समस्या
• नेस्टेड स्टैक automaton#Properties (समूहों के लिए शब्द समस्या को हल करने के लिए उपयोग किया गया है)

संदर्भ

• Boone, W.W.; Cannonito, F.B.; Lyndon, Roger C. (1973). Word problems : decision problems and the Burnside problem in group theory. Studies in logic and the foundations of mathematics. Vol. 71. North-Holland. ISBN 9780720422719.
• Boone, W. W.; Higman, G. (1974). "An algebraic characterization of the solvability of the word problem". J. Austral. Math. Soc. 18: 41–53. doi:10.1017/s1446788700019108.
• Boone, W. W.; Rogers Jr, H. (1966). "On a problem of J. H. C. Whitehead and a problem of Alonzo Church". Math. Scand. 19: 185–192. doi:10.7146/math.scand.a-10808.
• Borisov, V. V. (1969), "Simple examples of groups with unsolvable word problem", Akademiya Nauk SSSR. Matematicheskie Zametki, 6: 521–532, ISSN 0025-567X, MR 0260851
• Collins, Donald J. (1969), "Word and conjugacy problems in groups with only a few defining relations", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 15 (20–22): 305–324, doi:10.1002/malq.19690152001, MR 0263903
• Collins, Donald J. (1972), "On a group embedding theorem of V. V. Borisov", Bulletin of the London Mathematical Society, 4 (2): 145–147, doi:10.1112/blms/4.2.145, ISSN 0024-6093, MR 0314998
• Collins, Donald J. (1986), "A simple presentation of a group with unsolvable word problem", Illinois Journal of Mathematics, 30 (2): 230–234, doi:10.1215/ijm/1256044631, ISSN 0019-2082, MR 0840121
• Collins, Donald J.; Zieschang, H. (1990), Combinatorial group theory and fundamental groups, Springer-Verlag, p. 166, MR 1099152
• Dehn, Max (1911), "Über unendliche diskontinuierliche Gruppen", Mathematische Annalen, 71 (1): 116–144, doi:10.1007/BF01456932, ISSN 0025-5831, MR 1511645, S2CID 123478582
• Dehn, Max (1912), "Transformation der Kurven auf zweiseitigen Flächen", Mathematische Annalen, 72 (3): 413–421, doi:10.1007/BF01456725, ISSN 0025-5831, MR 1511705, S2CID 122988176
• Kuznetsov, A.V. (1958). "Algorithms as operations in algebraic systems". Izvestia Akad. Nauk SSSR Ser Mat. 13 (3): 81.
• Miller, C.F. (1991). "Decision problems for groups — survey and reflections". Algorithms and Classification in Combinatorial Group Theory. Mathematical Sciences Research Institute Publications. Vol. 23. Springer. pp. 1–60. doi:10.1007/978-1-4613-9730-4_1. ISBN 978-1-4613-9730-4.
• Nyberg-Brodda, Carl-Fredrik (2021), "The word problem for one-relation monoids: a survey", Semigroup Forum, 103 (2): 297–355, arXiv:2105.02853, doi:10.1007/s00233-021-10216-8
• Rotman, Joseph (1994), An introduction to the theory of groups, Springer-Verlag, ISBN 978-0-387-94285-8
• Stillwell, J. (1982). "The word problem and the isomorphism problem for groups". Bulletin of the AMS. 6: 33–56. doi:10.1090/s0273-0979-1982-14963-1.