半群的字問題(word problem for semigroups )是歷史上最先被證明不可判定性的一個問題。所有有限半群和許多可數半群，可以由有窮個產生元及這些產生元組成的有窮串(稱為字)上的有窮個等價關係(稱為定義關係)產生。
基本介紹
- 中文名：半群的字問題
- 外文名：word problem for semigroups
- 領域：數學
- 學科：群論
- 對象：半群
- 相關：群的字問題
概念,半群,群論,群的字問題,
概念
半群的字問題(word problem for semigroups )是歷史上最先被證明不可判定性的一個問題。所有有限半群和許多可數半群，可以由有窮個產生元及這些產生元組成的有窮串(稱為字)上的有窮個等價關係(稱為定義關係)產生。例如，半群〈N，+〉可以由一個產生元產生(沒有定義關係)，而〈n，+n〉(+n表示模n加法)則可以由一個產生元g使定義關係g～∧產生(∧表示空串，g表示i(i<n))。所謂半群的字問題是指：是否存在能行的算法，使得對任意由有窮個產生元和有窮個定義關係生成的半群，及由這些產生元組成的兩個字W1，W2，該算法可以判定W1與W2在半群中是否表示同一個元。
由於以上問題是對任意半群而言的，因此稱為一般的半群的字問題。對於一個特殊的半群，也有其特殊的半群的字問題。波蘭-美國數理邏輯學家波斯特(Post，E.L.)和俄國數學家馬爾可夫(Марков，А.А.)證明了一般的半群的字問題是不可解的，並且存在由有窮個產生元和有窮個定義關係產生的半群，其對應的特殊的半群的字問題是不可解的。首先考慮半群的字問題是挪威數學家圖埃(Thue，A.).它是一個在形式上與邏輯沒有聯繫的問題。
半群
半群是最簡單、最自然的一類代數系統。一個非空集合S連同定義在它上面的一個結合的(即滿足結合律的)二元運算“·”的代數系統(S，·)稱為一個半群。半群(S，·)簡記為S。
半群是群的推廣。群自然是半群；反之顯然未必。半群也是環的推廣。環在只考慮它的乘法運算的時候是一個半群，稱為環的乘半群；但任何一個帶零半群卻未必是某個環的乘半群。半群代數理論的系統研究始於20世紀50年代(雖然，這方面的工作可追溯到1904年蘇士凱維奇(Suschkwitz，A.K.)關於有限半群的論文)。在數學內部和外部的巨大推動下，半群理論已成為代數學的一個公認的分支學科，並早已以其特有的方法獨立於群論和環論之外.在20世紀60年代，蘇聯和美國率先出版了兩本專著，利雅平(Ляпин，E.C.)的《半群》和克利福德(Clifford，A.H.)與普雷斯頓(Preston，G.B.)的兩卷《半群代數理論》，這對半群代數理論的發展，在國際上起了巨大的推動作用.由德國斯普林格出版社出版的《半群論壇》更是有關半群理論的一個重要的國際性專門刊物。許多數學家在世界各地開展半群理論的研究和各層次高級人才的培養(直到博士後)。半群代數理論是半群理論中最基本、最活躍、也最富成果的一部分。此外，尚有半群的分析、拓撲和序理論。
群論
代數學的一個分支。群是數學中廣泛存在的一個重要概念。它的出現始於18世紀末.19世紀中葉，凱萊(Cayley，A.)首先給出了群的公理化定義，後來在物理、化學等學科中找到了重要的套用。例如，一個集合的所有置換構成一個群，又如，數學的某些系統或其他系統的自同構群等。因而，作為獨立數學分支的群論是在其他研究工作中逐漸形成的。
由於群的抽象性，儘管群廣泛存在，並且早在歐幾里得(Euclid)時代，群的思想在《幾何原本》中已經出現，但卻遲至18世紀末期才真正萌生群的概念。此後，直到19世紀中葉是群論的孕育時期，拉格朗日(Lagrange，J.-L.)、柯西(Cauchy，A.-L.)、伽羅瓦(Galois，E.)、西洛(Sylow，L.)等人的工作中已包含了豐富的群論思想與基本結果。特別地，在伽羅瓦關於代數方程的傑出研究中運用現代群論的這些基本思想與結論，顯示了巨大威力，這是數學史上的重要一頁.1854年，凱萊第一次給出了群的公理化定義後，1870年出版了由若爾當(Jordan，M.E.C.)撰寫的第一本有影響的群論著作，群論才真正成為一個獨立學科.此後，克萊因(Klein，C.F.)從幾何的角度考慮，發表了著名的埃爾朗根(Erlangen)綱領，李(Lie，M.S.)由微分方程的研究引入了李群(現在，李群已獨立成為另一分支學科)。群已被廣泛地套用，並獨立地發展成為一個龐大的多方向的代數分支，至今仍長盛不衰。
群論發展的歷史錯綜複雜，它涉及眾多著名數學家以及不少數學領域和其他科學領域，而作為代數分支的群論，主要指那些以群或其推廣為主要研究對象，以代數方法為主要研究方法的各種理論。
當今群論包括基礎理論、置換群論、群表示論、抽象有限群論、無限群的有限群結構及分類理論、無限群有限群的專門方向、線性代數群(含典型群)、半群、群的各種推廣等十多個下屬分支學科。
群論是以公理化的形式出現的。隨著發展，其研究課題、思想與方法愈來愈豐富多彩，在具體方法上常常以作用的形式出現，如在集合上的置換作用、在空間上施加一個旋轉作用等。所以群論與其他數學學科、自然科學學科的相互滲透及群的套用都相當廣泛。群論複雜的歷史與複雜的現狀足以說明這一點，這也正是群論的生命力之所在。例如，群論特別是群表示論對量子物理與量子化學的套用形成了一個單獨的邊緣分支學科。
群的字問題
群的字問題是一個不可判定性問題。所有有限群和一些可數無窮群，可以由有窮個產生元及這些產生元組成的有窮串(稱為字)上的有窮個等價關係(稱為定義關係)表示。例如半群〈z，0，+〉(z為整數集)可以由兩個產生元{p，n}與等價關係{pn～∧，np～∧}表示，p表示i，n表示-i，∧為空串，表示0。所謂群的字問題是指：是否存在能行的算法，使得對任意的可以由有窮個產生元和有窮個定義關係生成的群，及由這些產生元組成的兩個字W1，W2，該算法可以判定W1與W2在群中是否表示同一個元。
由於以上問題是對任意(可有限表示的)群而言的，因此稱為一般群的字問題。對於一個具體的群，也有其對應的特殊的群的字問題。相對半群的字問題來說，群的字問題的解決要困難得多。解決這一問題的是諾維科夫(Novikoff，P.S.)和美國學者布恩(Boone，W.W.)，他們證明了一般群的字問題是不可解的，並且證明了存在有窮個產生元和有窮個定義關係產生的群，其對應的字問題是不可解的。
