Timeline for Is any interesting question about a group G decidable from a presentation of G?
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 23, 2010 at 13:57 | comment | added | Joel David Hamkins | Henry, thanks for your comment. Yes, I understand that point very well. This was why I found the possibility of a Rice's theorem in this context so tantalizing, because if true, it would have explained the phenomenon so completely. But alas, Stillwell has refuted it. | |
| Feb 23, 2010 at 5:30 | comment | added | HJRW | I think this misses the point somewhat. There are some very general, very well-behaved classes of groups. For instance, a 'randomly chosen' finitely presented group is hyperbolic, which is a very nice sort of hyperbolic group. But the point is that one can't recognise if a given presentation falls into a nice class or not. Indeed, we can't recognise if a given presentation is of the trivial group! That's the point about Markov properties. | |
| Feb 23, 2010 at 4:40 | comment | added | Chad Groft | Automaticity is not decidable. The proof that Markov properties are undecidable would apply here. More generally, any condition on a group that applies to the trivial group, and which implies that the group has decidable word problem, cannot be decidable. So hope survives! Specifically, there is a construction which takes a f.p. group G and a word w in G, and builds a group G_w. This new group is trivial if w is trivial and contains G as a subgroup if w is not trivial. Testing G_w for the condition would test w for triviality, which is clearly a problem. | |
| Feb 23, 2010 at 3:28 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |