Timeline for Decidability: Presentations vs. Groups
Current License: CC BY-SA 4.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 28, 2019 at 7:26 | comment | added | Ali Caglayan | Would these kinds of questions not fall under the term "Combinatorial group theory"? "Combinatorial group theory: A topological approach" by Cohen, has an entire chapter on decision problems for example. | |
| Jul 28, 2019 at 3:10 | answer | added | Robert Furber | timeline score: 4 | |
| Jul 15, 2019 at 11:03 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Mar 17, 2019 at 11:15 | comment | added | YCor | @YiftachBarnea the statement that the triviality problem is undecidable (in the Turing sense) means that, among all presentations (maybe with $d\ge 2$ fixed generators), the set of presentations defining a nontrivial group is not recursively enumerable. | |
| Mar 17, 2019 at 11:08 | comment | added | YCor | @DerekHolt that's confusing. The statement "Goldbach's conjecture is decidable" usually means that either "Goldbach's conjecture is true" or "Goldbach's conjecture is false" is a theorem of ZFC, and we don't know. We know that CH is not decidable. Of course, this has nothing to do with Turing-decidability, but the confusion is frequent. | |
| Mar 17, 2019 at 11:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Feb 15, 2019 at 10:06 | answer | added | Yiftach Barnea | timeline score: 0 | |
| Feb 15, 2019 at 9:53 | comment | added | Yiftach Barnea | @DerekHolt since I am not an expert I might not be using the right terms. However, to make such questions fit better with the intuition, one would require that the machine will produce a proof rather than just yes or no. So I don't just want the machine to tell me whether the group is trivial, but also to give me a proof. I hope this clarify my intention. | |
| Feb 15, 2019 at 8:09 | comment | added | Derek Holt | That reminds me that people occasionally ask questions like "Is Golbach's Conjecture decidable?" and the answer is of course yes, because one of the two algorithms that output "yes" and "no" correctly outputs the answer (even if we don't yet know which one is correct). | |
| Feb 14, 2019 at 23:55 | comment | added | Benjamin Steinberg | To Derek's point, there is a Turing machine which cans translate from one fixed presentation to another. We may not know which one. | |
| Feb 14, 2019 at 23:53 | comment | added | Benjamin Steinberg | If the group G is fixed and the input is a finite presentation of G, then the algorithm which always says yes or always says no gives the answer to triviality. | |
| Feb 14, 2019 at 22:25 | comment | added | YCor | A finitely generated group has solvable word problem iff it is isomophic to $\mathbf{N}$ endowed with a computable group law. | |
| Feb 14, 2019 at 22:11 | comment | added | Derek Holt | I don't think your question in the final paragraph makes sense. If the input is a presentation, then the problem would be to decide whether that presentation defines a trivial group. Either that can be done or it cannot. It doesn't make sense to say that we cannot decide it for all inputs. Decidability applies to the problem as a whole, not to the individual inputs to the problem. | |
| Feb 14, 2019 at 21:55 | comment | added | Derek Holt | Incidentally, the definition of the word problem involves a (finite) generating set, but it does not involve relations so it is not connected with presentations in particular. | |
| Feb 14, 2019 at 21:53 | comment | added | Derek Holt | Yes it's moderately obvious. If the word problem is decidable using generators $X$, and you have another set $Y$ of generators, then you can express each element of $Y$ as a word over $X$, and then when you read an input word over $Y$ you just translate it into a word $X$ as you read it and use your existing word problem solver over $X$. | |
| Feb 14, 2019 at 21:43 | comment | added | Yiftach Barnea | @BenjaminSteinberg, I think I stated the input clearly, it is a presentation. My question about the triviality is, does there exist a finitely presented group such that for all its presentations you can not decide if the presentation is trivial? | |
| Feb 14, 2019 at 21:38 | comment | added | Yiftach Barnea | @DerekHolt is this an obvious fact? I can see why it might be true if the generators are the same and the relations generate the same subgroup, but it is not obvious to me otherwise. | |
| Feb 14, 2019 at 21:25 | comment | added | Benjamin Steinberg | Most of these issues arise from not clearly stating what is the input to a problem. For example the triviality problem takes as input a presentation and asks if it presents the trivial group. The input is a presentation not a group. Usually for the word problem the group is fixed and the input is just a word over the generators. In this case as Derek says having a decidable word problem is presentation independent. People will often say the uniform problem if the group is part of the input. | |
| Feb 14, 2019 at 20:52 | comment | added | Derek Holt | The decidability of the word problem, for example, is a property of the group, it is independent of the generating set. The same applies to most of the familiar decision problems such as conjugacy problem, isomorphism problem. | |
| Feb 14, 2019 at 18:59 | history | asked | Yiftach Barnea | CC BY-SA 4.0 |