Economical hard word problem - MathOverflow

Economical hard word problem

2011-12-27T17:54:00Z

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.

Answer by Mark Sapir for Economical hard word problem

2011-12-27T19:14:56Z

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.

Answer by Igor Dolinka for Economical hard word problem

2012-01-17T23:39:23Z

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.

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