enter image description hereenter image description hereI was reading "An introduction to the theory of groups" by Rotman, chapter 12, the word problem. I am stuck inThis is the proof given the following theorem, Let $G$ be a finitely presented group with presentation $$G = \langle x_{1}, \ldots ,x_{n} \mid r_{1},\ldots ,r_{m}\rangle$$ If $\Omega$ is the set of all words on $x_{1},\ldots,x_{n}$, then $E = \{ \omega \in \Omega \mid \omega = 1 \text{ in }G \}$ is recursively enumerable. The proof goes like this: We put an order in the set of generators, by Zermelo's well ordering principle, this well ordering will induce a dictionary order in the set of words, also similarly impose this ordering among the words formed by the set of relators. I donot understand this proof, I know to show a set is recursively enumerable I need to show that a Turing machine exists such that when the elements of the set are put in the machine, the machine computes the element, i.e., there exists a finite sequence of basic moves which ends at a terminal description (according to the definition of the book).

Edit: I incorporate the definition of recursively enumerable as given in Rotman. But the main proof does not seem to rely on the definition. This is where my problem is. Thanks.

  • 5
    $\begingroup$ The proof is not difficult. Using your ordering on words you can systematically enumerate all products (of any length) of all conjugates of $r_1,\ldots,r_m$, and reduce the resulting words. By doing that you churn out all reduced words that evaluate to the identity in the group. Of course you may have a very long wait before specific words are output. There is a slightly more effective way of doing this using the Knuth-Bendix completion procedure, but that's not required for the theoretical proof. $\endgroup$
    – Derek Holt
    Apr 16 at 14:23
  • 2
    $\begingroup$ Please do not rely on pictures of text. $\endgroup$
    – Shaun
    Apr 16 at 14:59
  • 1
    $\begingroup$ @IzaakvanDongen I am equally puzzled. I would have thought one then had to enumerate (in the same way) all the products of these conjugates of relators. (As in Derek Holt's comment.) $\endgroup$ Apr 16 at 16:54
  • 1
    $\begingroup$ The process I described enumerates precisely the set of reduced words that evaluate to the identity in the group. I really think that if you understood all the definitions, then this would be clear. Except in the case of the free group with no relators, there will always be infinitely many such words, so the process will not halt. $\endgroup$
    – Derek Holt
    Apr 16 at 16:54
  • 2
    $\begingroup$ @DerekHolt Not by your comment, but by the proof in Rotman which seems only to enumerate conjugates of products of relators; I thought we needed products of these conjugates which is what you enumerate. $\endgroup$ Apr 16 at 17:02

1 Answer 1


I don't think you are going to get a satisfactory answer to your question regarding a formal Turing machine description for this problem, for the following reasons.

Algorithms have been around in mathematics for a long time before they were formalized by Alan Turing in a paper he published in the 1930's.

At some point after that, Turing machines became part of the standard education of a mathematician. I learned about them in a logic course that I took in my junior year of college, sometime around 1977. One thing that one learns in such a course is how to formalize very simple algorithms as Turing machines.

Inspired by Turing's advances, programmable computers were developed in starting in the 1940's. At its heart, a programmable computer uses machine language, which is not very far from the concept of a Turing machine, but which is designed to be more practically adapted to the realities of an electronic computer. Most computer designs include specs which demonstrate that the computer's machine language is equivalent to a Turing machine.

But even machine language is too low level for practical computation, and computer scientists slowly developed higher level languages that are easier for humans to use. Every computer has its own "assembly language" which is higher level than machine language, but is better adapted for human use. Actual machine language programs are typically written by an "assembler" which is a program that translates "assembly language" into machine language.

But even assembly language is too low level, and higher level programming languages were eventually developed. Perhaps the one language which really got this off the ground was BASIC, developed in the early 1960's.

Computer programming courses slowly became part of the standard education, starting with BASIC. Better and better programming languages were developed and applied. More and more scientists and mathematicians wrote computer software for various applications. Our own @DerekHolt wrote one of the most widely used software packages for group theory (perhaps he or someone could leave a link to this package in the comments).

So what do mathematicans do instead, if they don't ever write actual Turing machines? What they do instead is to rely on their education in algorithms and programming. When presented with an informal description of an algorithm, their training aids them in determining whether that description is sufficiently precise that it can be translated into some programming language. They don't need to actually write that program, if all they want to know for sure is that the problem is Turing computable. Holt's description in the comments of an algorithm for enumerating words that evaluate to $1$ is perfectly fine for that purpose.

Nonetheless, if you do understand that an informal algorithm is Turing computable, or if you wish to enhance your own understanding of whether or not it is Turing computable, you do always have option of trying to write a program for implementing that algorithm in Basic, or C, or Java, or whatever is the programming language of your choice.

But, if you really, really wanted to have a Turing machine for inputting a finite group presentation and recursively enumerating the words which evaluate to $1$, you would probably have to do something like this. First, use the algorithm described in Derek Holt's comment to write a computer program (perhaps using Holt's software, or some ordinary computer language; earlier in my career I wrote various programs for my mathematics in the C language). Compile that software. Behind the process of compiling that software, it will be translated into assembly language, and then into machine language, on whatever computer you are using. Get the specs for your computer, and use them to translate the machine language program into an actual Turing machine. What might be marginally more practical is to translate directly from the assembly language into a Turing machine, but that might be too laborious.

  • $\begingroup$ The first computer language I wrote in was ALGOL60, which is now extinct (although it influenced many later languages), then I had a long period writing in C. My KBMAG package is written in C, with interfaces to GAP and Mgama. But these days I write nearly all of my group theory software in Magma or GAP. $\endgroup$
    – Derek Holt
    Apr 17 at 15:28
  • $\begingroup$ I think the reason that Rotman provides a detailed definition of a type of Turing machine is that he used this explicitly in the proof of the unsolvability of the word problem in semigroups, which is reasonably straightforward. The proof for groups, which can also be found in Rotman's book, is much more difficult, and makes extensive use of HNN extensions. $\endgroup$
    – Derek Holt
    Apr 17 at 15:30
  • $\begingroup$ @DerekHolt "Reasonably straightforward"? I am genuinely stuck in the proof unsolvability of the word problem in semigroups. Nevertheless, I understood the proof of the question I asked here, thanks to you guys! $\endgroup$ Apr 17 at 16:17
  • $\begingroup$ @DerekHolt: I figured that I was dating myself, and my programming years, by stopping with C and Java (and, in all honesty, Java is even after my programming years). $\endgroup$
    – Lee Mosher
    Apr 17 at 16:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .