8
$\begingroup$

Is there any reasonably updated list of (representative) examples of finitely presented groups with undecidable word problem?

By "representative" I mean "avoiding obvious redundancy", i.e. examples different from each other in providing (from some point of view) new insight into the problem.

A brief comment on the ideas and methods used, and even the concrete presentations when possible, would also be of interest.

In case there is not such list, I wonder if it is a suitable big-list for MO.

$\endgroup$
3
  • 3
    $\begingroup$ Miller III (1981, citeseerx.ist.psu.edu/viewdoc/…) produced f.p. groups with no nontrivial quotient has decidable word problem (DWP). (In comparison, recall that any f.p. simple group has DWP.) Paul Schupp told me once that Miller's paper contains ideas that are really subtle from the point of view of computability theory (having in mind that most undecidability results in group theory just consist in just encoding some undecidability feature and contain no original idea from the point of view of computability). $\endgroup$
    – YCor
    Commented Nov 15, 2015 at 12:29
  • 1
    $\begingroup$ Take a look at the reference here: mathoverflow.net/questions/107357/… and mathoverflow.net/questions/84398/economical-hard-word-problem and en.m.wikipedia.org/wiki/Word_problem_for_groups#Examples $\endgroup$
    – Misha
    Commented Nov 15, 2015 at 17:39
  • $\begingroup$ Thank you for the references. Perhaps there are not enough examples for a big-list. Miller's paper looks interesting anyway. $\endgroup$
    – suitangi
    Commented Nov 17, 2015 at 12:23

1 Answer 1

5
$\begingroup$

In addition to Miller's book cited above you can look at "Algorithmic problems in varieties" and "Asymptotic invariants, complexity of groups and related problems" for more recent examples. These include results about complexity of the word problem. Even more recent results are in papers by Olshanskii and myself (see the arXiv).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.