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?

Improve this question
$\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
    Commented 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$
    – Benjamin Steinberg
    Commented Jul 8, 2014 at 13:52
  • $\begingroup$ Basically there is a big difference between knowing an algorithm exists and constructing it. $\endgroup$
    – Benjamin Steinberg
    Commented 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$
    – Steven Stadnicki
    Commented 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
    Commented Jul 8, 2014 at 19:05

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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