Algorithmic, topological and geometric aspects of infinite groups, monoids and inverse semigroups

20世纪世纪数学最令人惊奇的成果之一是阿朗佐·丘奇和艾伦·图灵发现，数学中存在无法解决的问题，因为没有算法来解决这些问题。这意味着无论你使用多么强大的计算机来帮助你，仍然有一些数学问题你无法解决。如果无法解决的问题是一个“是”或“否”的问题，那么我们称之为不可决定的问题。另一方面，如果它能被解决，那么我们说它是一个可判定的问题。在代数中自然会出现许多决策问题。重要的例子包括单词问题，它要求我们决定两个不同的代数表达式是否彼此相等，以及成员问题，它要求我们决定代数结构中的一个元素是否可以用另一个元素的集合来表示。在研究无限代数结构时，能够解决这样的问题是很重要的。这个项目的主要议题是研究一系列的决策问题，如三类代数对象称为群，幺半群和逆半群。这三个类自然出现在研究对称性和部分对称性的数学。生成元和关系表示理论是定义无限群、幺半群和逆半群的一个重要工具。这个想法是，群或幺半群的元素由字母串表示，称为单词。我们还得到了一组定义关系，这些规则告诉我们某些单词对彼此相等。如果一个词可以通过应用关系变换成另一个词，那么两个词是相等的。例如，如果我们使用字母x和y，并且我们有一个单一的定义关系xy=yx，那么单词xyx和yxx是相等的，因为xyx =（xy）x =（yx）x = yxx。另一方面，单词xy和yy不相等。判断两个单词是否相等的问题就是上面提到的单词问题。当我们使用表示定义一个幺半群或群时，通过增加关系的数量，我们可以增加我们定义的幺半群或群的复杂性。如果没有关系，这些被称为自由幺半群和群，并且由于它们的简单结构，一些自然的判定问题，如单词问题，可以被视为在这些情况下是可判定的。与此相反，已知有幺半群、群和逆半群由许多生成元和关系定义，但存在不可判定字问题。这种情况是类似的许多其他决策问题出现在代数。人们自然会问，在某种意义上，接近自由的群或幺半群是否具有良好的算法性质。一个重要的积极成果，这类群体是马格努斯定理表明，群体所定义的一个单一的定义关系都有可判定的字的问题。另一方面，最近发现存在由单个定义关系定义的逆幺半群，其具有不可判定的字问题。然而，它仍然是一个重要的长期开放的问题是否字的问题是可判定的单关系幺半群。有许多迷人的开放问题，如这一个问的基本问题之间的边界在哪里的可判定性和不可判定性在于提出的群，幺半群和逆半群。在这个项目中，我们将探讨一系列这类相互关联的问题。这将通过开发几何和拓扑方法来完成，这些方法使用这些代数对象的“形状”，或者它们与空间相互作用的方式，来阐明它们的算法属性。

One of the most amazing results of twentieth century mathematics was the discovery by Alonzo Church and Alan Turing that there are problems in mathematics which cannot be solved, in the sense that there is no algorithm to solve them. This means that no matter how powerful a computer you use to help you, there are some mathematical problems that you will still not be able to solve. If the problem that cannot be solved is in the form of a "yes" or "no" question, then we call it an undecidable problem. On the other hand, if it can be solved, then we say that it is a decidable problem. There are many decision problems that arise naturally in algebra. Important examples include the word problem, which asks us to decide whether two different algebraic expressions are equal to each other, and the membership problem, which asks us to decide whether one element in an algebraic structure can be expressed in terms of another collection of elements. Being able to solve problems like these is important when studying infinite algebraic structures. The main topic of this project is to investigate a range of decision problems like these for three classes of algebraic objects called groups, monoids and inverse semigroups. These three classes arise naturally in the study of symmetry and partial symmetry in mathematics. An important tool for defining infinite groups, monoids and inverse semigroups, is given by the theory of presentations in generators and relations. The idea is that the elements of the group or monoid are represented by strings of letters, called words. We are also given a set of defining relations, which are rules telling us that certain pairs of words are equal to each other. Two words are then equal if one can be transformed into the other by applying the relations. For example, if we use the letters x and y, and we have a single defining relation xy=yx, then the words xyx and yxx are equal since xyx = (xy)x = (yx)x = yxx. On the other hand, the words xy and yy are not equal. The problem of determining whether or not two words are equal to each other is the word problem mentioned above. When we define a monoid or group using a presentation, by increasing the number of relations we can increase the complexity of the monoid or group that we define. If there are no relations these are called free monoids and groups, and because of their simple structure several natural decision problems, like the word problem, can be seen to be decidable in these cases. In contrast, it is known that there are monoids, groups, and inverse semigroups which are defined by finitely many generators and relations, but have undecidable word problem. The situation is the similar for the many other decision problems arising in algebra. It is natural to ask whether groups or monoids which are close to being free, in some sense, will have good algorithmic properties. An important positive result of this kind for groups is Magnus's theorem which shows that groups defined by a single defining relation all have decidable word problem. On the other hand, it was recently discovered that there are inverse monoids defined by a single defining relation that have undecidable word problem. However, it remains an important longstanding open problem whether the word problem is decidable for one-relator monoids. There are many fascinating open problems like this one which ask fundamental questions about where the boundary between decidability and undecidability lies for finitely presented groups, monoids and inverse semigroups. In this project we will explore a range of interrelated problems of this kind. This will be done by developing geometric and topological methods, which use the "shape" of these algebraic objects, or the way they interact with spaces, to shed light on their algorithmic properties.