5

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?

user126154
  • 829
  • 4
  • 19
  • 4
  • 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?"
    • – YCor Jul 08 '14 at 12:37
  • 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? – Benjamin Steinberg Jul 08 '14 at 13:52
  • Basically there is a big difference between knowing an algorithm exists and constructing it. – Benjamin Steinberg Jul 08 '14 at 14:00
  • @BenjaminSteinberg there are such examples? – user126154 Jul 08 '14 at 14:07
  • @BenjaminSteinberg The fact that it is undecidable if a Turing machine accepts the word problem, implies that we cannot exhibit any algorithm to solve the problem. Right? – user126154 Jul 08 '14 at 14:28
  • It means you can't determine if the Turing machine you are exhibiting is the correct one or not. – Benjamin Steinberg Jul 08 '14 at 15:26
  • For example, there is a TM that gets correct the question of whether Riemann hypothesis is true. Either it is the TM that always says "yes" or the TM that always says "no". I can exhibit both, but I don't know which one is correct. – Benjamin Steinberg Jul 08 '14 at 15:27
  • In your case things are even worse. For any fixed TM M which always halts, there is no algorithm to determine given a TM as input whether it accepts the same set as M. Since finitely presented groups are as general as Turing machines, as John Stillwell points out, you cannot decide if a given TM decides the word problem for your group. – Benjamin Steinberg Jul 08 '14 at 15:28
  • 1
    @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 http://mathoverflow.net/a/48025/7092 – Steven Stadnicki Jul 08 '14 at 15:47
  • 1
    @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. – YCor Jul 08 '14 at 19:05
  • Possible duplicate: http://mathoverflow.net/q/14918/1946. See also http://mathoverflow.net/a/126647/1946, and http://mathoverflow.net/a/48031/1946. – Joel David Hamkins Jul 08 '14 at 20:34
  • @BenjaminSteinberg thank you. May I take a little more of your time? If I understand, given a fixed G it is possible that the WP is solvable for G but $()$ "there is no algorithm that decides whether a TM M solves the problem". Is that right? If so, is $()$ coherent with the possibility that I could prove, for a given explicit particular TM, that it solves the WP for my given G? Or $(*)$ means that there is no way at all, given an explicit TM, to see that it solves the WP problem? – user126154 Jul 09 '14 at 09:53
  • It means there is no algorithm to determine on input a TM whether it solves your problem. You might be able to prove for a single TM it works. – Benjamin Steinberg Jul 09 '14 at 12:24
  • The closest thing two 2) that could happen is we prove in some theory (like ZFC) that $G$ is solvable, but there not being an explicit algorithm that ZFC proves is correct. – Christopher King Jan 24 '19 at 03:57