CHAPTER 9 - DECISION PROBLEMS

Summary

DECISION PROBLEMS IN GENERAL

Can we tell whether or not an element of a free group is in the commutator subgroup? Whether or not it is a commutator? Given a finite presentation, can we tell whether or not an element of the free group is 1 in the group presented? Can we tell whether or not two finite presentations present isomorphic groups?

These questions, and other similar ones, are obviously of interest. We shall see later that the first two questions have the answer “Yes”, while the other two have the answer “No”. The techniques used are those of combinatorial group theory, but have no specific connection with the topological approach. I include this chapter because I find the material particularly interesting.

In order to make these questions precise, we need to be clearer about what is meant by “We can tell … ”. This should mean that we can tell by some purely mechanical process, not requiring thought. In other words, we want to be able to feed the data to a computer and have the computer arrive at the answer as to whether or not the required property holds for the given data.

Readers might think that a computer's ability to arrive at the answer for given data would depend very much on the computer. This turns out not to be so, though the speed and efficiency of the computer's answer will depend on the computer.

More precisely, there is a class of functions (called partial recursive functions) with the following properties.