5
$\begingroup$

Let $G$ be a finitely generated group. I wonder if there are examples where:

1) The word problem is known to be solvable in $G$ but there is no algorithm known.

2) The word problem is known to be solvable in $G$ but it is also known that no algorithm for solving the problem can be exhibite.

3) the same as 1) and 2) but with other decisional problems.

$\ $

Is 2) really possible? The question relies on the difference between "$\exists x$" and "showing an $x$". It seems to me that if $G$ has solvable problem then, by definition, an algorithm $A$ that solves the problem exists. Since algorithms are build up from finite objects, in principle I can enumerate all of them and eventually find $A$ (but how can I be sure that $A$ solves the word problem for $G$?). Am I making a big confusion or the question makes sense?

$\endgroup$
14
  • 4
    $\begingroup$ 2) should be formulated in a way to make sense, what's the input? Right now it sounds like "given a non-empty subset of positive integers, can we exhibit an element in this set?" $\endgroup$
    – YCor
    Jul 8, 2014 at 12:37
  • $\begingroup$ Do you mean is there a fg group with a solvable word problem but for which it is undecidable if a Turing machine accepts the word problem? $\endgroup$ Jul 8, 2014 at 13:52
  • $\begingroup$ Basically there is a big difference between knowing an algorithm exists and constructing it. $\endgroup$ Jul 8, 2014 at 14:00
  • 1
    $\begingroup$ @YCor There are in fact similar results to (2) in graph theory; the Robertson-Seymour theorem essentially says that every family of graphs that's closed under the operation of taking minors is the compliment of a union of cones, but there can be no algorithm for taking a description of a minor-closed family and producing the minimal elements of its compliment; see mathoverflow.net/a/48025/7092 $\endgroup$ Jul 8, 2014 at 15:47
  • 1
    $\begingroup$ @StevenStadnicki I'm aware that these kind of results exist, but they ought to be stated in a proper way, which is, I'm afraid, not the case. What's the input? A "f.g. group with solvable word problem" is not an input. Should it be understood that the input is a recursive presentation and the question is whether, when the resulting group has solvable word problem, the output provides a algorithm? Possibly there are other interpretations of the question, and for this reason I don't consider it's asked in a proper way. $\endgroup$
    – YCor
    Jul 8, 2014 at 19:05

1 Answer 1

8
$\begingroup$

The technique for constructing groups with unsolvable word problems applies more generally to construct groups that "simulate'' Turing machines. So, if a Turing machine halts for a recursive set of inputs, it can be arranged that the corresponding group will have a solvable word problem. However, the algorithm will depend on the set of inputs for which the machine halts.

This reduces question 1) to finding a Turing machine which halts for a recursive set of inputs, but for which the set itself is not yet known. You could take, for example, a machine that halts on input 0 if there is an odd perfect number, and does not halt at all if not.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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