From: David Bernier <bernier@my-deja.com>
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" <edward@a1.nl>
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]