MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Economical hard word problem

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.

-
 Ever read Raymond Smullyan? Gerhard "Ask Me About System Design" Paseman, 2011.12.27 – Gerhard Paseman Dec 27 2011 at 18:04 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 – Gerhard Paseman Dec 27 2011 at 18:08 Is the first example of an insoluble problem here unsatisfactory? en.wikipedia.org/wiki/… – Dylan Wilson Dec 27 2011 at 18:15 @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. – gowers Dec 27 2011 at 18:28 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. – Dylan Wilson Dec 27 2011 at 18:40
show 1 more comment

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,...(?)

-
 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.) – gowers Feb 7 2012 at 21:09

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.

-
 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. – gowers Dec 27 2011 at 21:40 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. – Mark Sapir Dec 27 2011 at 22:59 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. – Benjamin Steinberg Dec 28 2011 at 0:29 @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. – Mark Sapir Dec 28 2011 at 4:10