From: David Bernier Subject: unsolvable word problems in combinatorial group theory: recent results? Date: Fri, 18 Feb 2000 15:21:46 GMT Newsgroups: sci.math,sci.logic Summary: [missing] The word problem for groups is often given as: "given a finite group presentation and relators, decide whether a given word reduces to the identity element." This problem, for general groups, is known to be unsolvable by any algorithm. As I understand it, there are group presentations with unsolvable word problems; for these groups, does it mean that the set of words that reduce to the identity is a non-recursive set? My impression is yes, because if the set were recursive, then an algorithm would exist to decide the word problem for this group; though perhaps one could not prove (in ZFC, say) that the algorithm always gives the right answer... How small can the group presentation be if it's word problem is unsolvable? Does the reducibility question amount to: "does this word reduce to e following some fixed rules based on the relators" or is it: "is the _value_ of this word the identity element e?" I read an introduction to this problem (group presentations, etc) in the Feb. 1997 issue of the American Math. Monthly, I think. I'm not sure about some points, hence this post. Thanks for any input, David Bernier Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: "Edward van Kervel" Subject: Re: unsolvable word problems in combinatorial group theory: recent results? Date: Fri, 18 Feb 2000 23:25:45 +0100 Newsgroups: sci.math,sci.logic Would the appendix of Shoenfield's "Mathematical Logic" be of any use to you, or is that old hat? edward van kervel [quote of previous article deleted --djr]