14
$\begingroup$

Can anyone give me an example of a very simple word problem, where by "simple" I mean that it has very few generators and relations, that is nevertheless insoluble. To make the question easier, I am prepared to allow "relation schemas" (an example might be that the fifth power of any word is equal to the identity, say), and I'm happy -- in fact, very happy -- to weaken "insoluble" to "insoluble in polynomial time" (in the length of the word). Also, I'm happy to work in a semigroup rather than a group. To make clearer what would count as a good example, let me give the reason behind it. I would like to find a collection of strings (the strings that are equal to the identity in the semigroup) such that recognising membership is difficult, but such that the space of strings in the collection is "interesting to explore", in the sense that one can develop methods for showing quite non-trivially that certain strings belong to the collection, and then build on those methods to get even less trivial examples and so on.

My motivation for that is to have a nice toy model of mathematics itself. So I'd like to be able to develop from the original replacement rules further particularly useful replacement rules that would be like lemmas, and that kind of thing. But I really would like the initial set of generators and relations to be very simple. Does this ring a bell with anyone?

Edit. Many examples of groups with insoluble word problems use sets of integers for which membership is not decidable and encode their membership problems as word problems for suitably constructed groups. I wouldn't consider such examples good ones, because they are simple relative to a set that may be quite complex. I want absolutely simple examples. If that seems like rather a strong demand, remember that I am allowing a considerable weakening of the insolubility condition.

Improve this question
$\endgroup$
6
  • $\begingroup$ Ever read Raymond Smullyan? Gerhard "Ask Me About System Design" Paseman, 2011.12.27 $\endgroup$
    – Gerhard Paseman
    Commented Dec 27, 2011 at 18:04
  • $\begingroup$ Also, in her book on Recursion Theory, Anne Yasuhara has an example of a tag system which might be to your liking. Gerhard "Happy Belated Boxing Day Everybody" Paseman, 2011.12.27 $\endgroup$
    – Gerhard Paseman
    Commented Dec 27, 2011 at 18:08
  • $\begingroup$ Is the first example of an insoluble problem here unsatisfactory? en.wikipedia.org/wiki/Word_problem_for_groups#Examples $\endgroup$
    – Dylan Wilson
    Commented Dec 27, 2011 at 18:15
  • $\begingroup$ @Dylan, I don't know if I'm looking at the same example, but if I am, then I don't like it because it encodes another problem. Maybe I should add that as a further restriction. In fact, I think I will. $\endgroup$
    – gowers
    Commented Dec 27, 2011 at 18:28
  • $\begingroup$ Fair point- though I guess it means that one could equivalently ask for a relatively "simple" recursively enumerable set where the membership problem is not computable, or something. $\endgroup$
    – Dylan Wilson
    Commented Dec 27, 2011 at 18:40

2 Answers 2

Reset to default
12
$\begingroup$

Here is an example that I know of. The following semigroup presentation has a recursively unsolvable word problem.

Generators: a,b,c,d,e

Relations: ac=ca, ad=da, bc=cb, bd=db, abac=abace, eca=ac, edb=be.

OR

Relations: ac=ca, ad=da, bc=cb, bd=db, ce=eca, de=edb, cca=ccae

These examples were published by G.S.Ceitin in 1958 (Trudy Math. Inst. Steklov, Vol. 52, pp. 172--189). Now, whether this suits Timothy's motivation, well,...(?)

Improve this answer
$\endgroup$
1
  • $\begingroup$ I don't know whether this suits my motivation until I've messed around with it for a while. But it looks promising, so many thanks. (Sorry for not writing this earlier -- I've been away from Mathoverflow for a while.) $\endgroup$
    – gowers
    Commented Feb 7, 2012 at 21:09
6
$\begingroup$

First of all if you are looking for a semigroup or group presentation, you only need 2 generators. Second the most "economical" (known) undecidable semigroup presentation has 2 generators and 3 relations (Matiyasevich, Yuri, Sénizergues, Géraud, Decision problems for semi-Thue systems with a few rules. Theoret. Comput. Sci. 330 (2005), no. 1, 145–169.). And the most economical (known) group presentation has 2 generators and 12 relations (Borisov, V. V. Simple examples of groups with unsolvable word problem. Mat. Zametki 6 1969 521–532.). See also this question and answers there.

Improve this answer
$\endgroup$
5
  • $\begingroup$ It looks to me as though these examples aren't quite what I'm looking for, interesting though they are. I haven't properly understood the first paper you refer to, but it looks as though it takes an arbitrary semigroup and encodes it as one with just three relations. From that I deduce that the relations are probably very complicated. I think I'm more interested in the relations being short than in there being few of them, though I'd like the latter as well. Also, if there are many relations but they can be easily grasped (as occurs in, say, the braid group on n generators) I would be happy. $\endgroup$
    – gowers
    Commented Dec 27, 2011 at 21:40
  • $\begingroup$ OK, then you need to look at my answer to the question of Ben Steinberg (the link is in my answer). The relations of the McKenzie-Thompson group have "meaning" (the group simulates not a particular machine but the definition of recursion functions, and so the relations correspond to the standard operations on recursive functions). The universal group (there is also a similar semigroup) has very easy defining relations. Again it does not simulate any particular device. $\endgroup$
    – user6976
    Commented Dec 27, 2011 at 22:59
  • $\begingroup$ The conversion from Turing machine to semigroup presentation can be done without much blowup so perhaps one needs economical Turing machines which recognize an undecidable language. $\endgroup$
    – Benjamin Steinberg
    Commented Dec 28, 2011 at 0:29
  • 1
    $\begingroup$ @Timothy: "Toy model of mathematics" is not clear at least to me. It would be good if you explain in more details what do you need this group/semigroup for. There are very many different ways to construct structures with undecidable word problem. Semigroups are not the easiest things. For example, the word problem in the free modular lattice (the signature has two operations) is undecidable and you can "encode the whole mathematics" in the free modular lattice. $\endgroup$
    – user6976
    Commented Dec 28, 2011 at 4:10
  • $\begingroup$ @MarkSapir: Thanks for this answer! I am very new to this concept. you know, I was searching the web an example in which I can get what we are looking for when we say unsolvable word problem in a semigroup. $\endgroup$
    – Mikasa
    Commented Apr 7, 2018 at 17:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .