10
$\begingroup$

I recently found out that there is no algorithm which, given an arbitrary group presentation, will determine in finite time if it represents the trivial group*. Additionally, in a lecture I recently attended, it was portrayed that given any desired property P of a group, there is no algorithm that will determine if an arbitrary group (presentation) has this property. (For additional info, see the second answer to this question on MathOverflow).

My question is about the scope of this notion of "algorithm." With regard to group presentations, my intuition tells me that there must be some way to classify or otherwise look at these arbitrary group presentations that would enable us to determine if they are the trivial group (or have some property P). However, I am not very well versed on what it means for something to be solved via an algorithm vs. other mathematical methods.

In general, if something has been shown to be unsolvable via algorithm, does it mean that it is entirely unsolvable (and thus futile to pursue in research)? Or, are there cases where we have shown that despite being unable to use an algorithm to determine if a property exists, we have used other mathematical methods with success?

*Clarification by Arturo.

$\endgroup$
  • $\begingroup$ By "it is algorithmically impossible to determine..." you really mean "there is no algorithm which, given an arbitrary group presentation, will determine in finite time if it represents the trivial group", right? Careful with the phrasing... $\endgroup$ – Arturo Magidin Feb 14 '11 at 2:35
  • $\begingroup$ Yes, thank you, Arturo. I am still clumsy with phrasing for these concepts. $\endgroup$ – Rachel Feb 14 '11 at 2:45
  • $\begingroup$ What do you mean by "entirely unsolvable"? The halting problem is an example of something undecidable that can be solved by a human in finite time. $\endgroup$ – Brandon Carter Feb 14 '11 at 2:53
  • $\begingroup$ @Brandon By "entirely unsolvable" I meant not even solvable by a human (in any amount of time or given any number of advances in theory/heuristics). After reading Arturo's response, I probably would not have asked the question in this way if I had a better understanding of algorithms and decidability/solvability. $\endgroup$ – Rachel Feb 14 '11 at 4:10
19
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This clarifies a lot! Thank you, Arturo. Re: "It's just that we cannot do it mindlessly." No wonder my moments of mindlessness end in mathematical messes! $\endgroup$ – Rachel Feb 14 '11 at 3:11
  • $\begingroup$ In paragraph 4, the fact that there can "only" be no algorithm that solves all instances is missing/obscure. But it is central: there can be algorithms that solve subsets of all problems. $\endgroup$ – Raphael Feb 20 '11 at 21:04
  • 1
    $\begingroup$ @Raphael: I attempted to clarify it, and also add that for some subclasses there are algorithm elsewhere. $\endgroup$ – Arturo Magidin Feb 20 '11 at 21:51
  • $\begingroup$ Thank you so much for this beautiful answer, I wish I could upvote ten times! $\endgroup$ – Blue Nov 23 '19 at 17:33
4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ so in other words, algorithmic unsolvability do imply unsolvability if every proof of the problem can be verified by an algorithm. $\endgroup$ – Chao Xu Feb 20 '11 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.