概念

半群的字问题(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.)，他们证明了一般群的字问题是不可解的，并且证明了存在有穷个产生元和有穷个定义关系产生的群，其对应的字问题是不可解的。