Does algorithmic unsolvability imply unsolvability in general?

Solution 1:

First: just exactly what is and what is not an algorithm is in fact a fairly deep philosophical question. Intuitively, we are talking about a "recipe" that, given the input, will yield an answer in an automatic manner, following certain pre-set rules and procedures.

There have been several independent attempts at formalizing the notion: Turing machines/Turing computability, Church's $\lambda$-calculus, Goedel's (amplified by Kleene and Rosser) notion of general recursive functions. It turned out that all of these notions are equivalent, in that if some process satisfies one of the definitions, then it satisfies all of them. This led Church to state his famous thesis, that in fact these notions do capture the idea of what an "algorithm" is; that is, that anything we can reasonably call an "algorithm" will in fact satisfy these definitions. (Everyone agrees anything that is Turing computable/$\lambda$-definable/given by general recursive functions is an algorithm; the question is whether everything that "is" an algorithm satisfies the definition). It is not 100% acceptable, but most people seem to accept it. It's not something that can be proven formally; it can only be settled in the negative (by producing something that everyone agrees should be called an "algorithm", but which can be shown to not be Turing computable/$\lambda$-definable/etc). We cannot prove it formally, because that would require a formal definition of what an "algorithm" is, and this is precisely the crux of the matter!

Assuming you take Church's thesis as true, then you can essentially think of "algorithm" as something you can program your computer to do, and which will, without any further action, eventually produce an answer, positive or negative, even if the "eventually" is so far off that the Sun would burn out before you got the answer.

So, second: what does it mean to say that there is no algorithm which, given an arbitrary group presentation, will always be able to decide if the group is trivial? It means that there is no way to program a computer to figure it out. If you try writing a program to do it, either it will not always give you the correct answer, or it will sometimes choke, meaning, it will be caught in an endless loop and never give you an answer (even theoretically).

This is a strong result: it doesn't just say that nobody has found a way to program a computer to do it, it says that nobody ever will; there is simply no set of instructions that will do it. This is much like saying that one cannot trisect the general angle using only straightedge and compass: it doesn't mean nobody has been able to figure out how, it means that nobody ever will, that no such procedure can exist.

That does not mean that given a group presentation you cannot figure out a way of determining if it is the trivial group, or whether the group it defines has property $P$. That's because you are not bound by a set of rigid instructions; you can make guesses, inspired at times, you can use tricks, you can come up with clever maps into nontrivial groups, etc. Again, for an analogy, think about writing down an elementary function (addition, product, division, powers, radicals, exponentials, trigonometric functions, logarithms, etc). You can program a computer to write down its derivative, because there is an algorithmic procedure for computing the formal derivative, using the product rule, sum rule, quotient rule, chain rule, etc. However, in order to integrate the function, we don't have an algorithm: we don't have a recipe that will always work. Instead, we have a bunch of heuristics of things to try, common tricks, and so on. That's why Mathematica can always give you the derivative, but sometimes chokes when you ask it to compute an indefinite integral.

Added. It also does not mean that there aren't subclasses of groups for which you can solve the problem. For example, if you are given a finite presentation for an abelian group, then there is a simple algorithm that will decide if that abelian group is trivial or not.

So, saying that the word problem (determining if a given finite group presentation yields the trivial group) does not have an algorithmic solution does not make it "entirely unsolvable"; it means there is no "recipe" that will always work. Now there are other interesting questions one can ask: is there a large and natural class of presentations where we do have an algorithm? If so, what are they, and what is the algorithm? Can we trace where the boundary is between "easy" groups (those for which we have a general algorithm) and the "hard" ones (those for which we cannot)? Can we classify the kinds of presentations for which there is no algorithm? Can we come up with heuristics to help try to solve the problem? Given a class of groups, can we find an algorithm that works for that class (e.g., nilpotent groups, solvable groups, etc). And so on. Particular instances of the problem (that is, particular presentations) may be dealt with in an ad hoc manner (a method specifically tailored to that particular presentation), so that determining if a particular presentation is the trivial group is not "unsolvable". It's just that we cannot do it mindlessly.

Solution 2:

It's actually even more shocking than what Arturo's answer might suggest. Consider the following algorithm. Given a group presentation $G=\langle S|R \rangle$, enumerate all possible proofs (say, using the axioms of ZFC), and check whether or not they give a proof that $G$ is trivial or not. If $G$ is trivial, then this algorithm must finish. Indeed, if $G$ is trivial, then we can write each element of $S$ as a product of conjugates of elements of $R$, and this constitutes a proof.

However, we know that there are inputs for which this algorithm does not terminate. This implies that there are finite presentations that define nontrivial groups, but for which there is no proof that they are nontrivial. This gives a concrete and down-to-earth example of Goedel's incompleteness theorem!