2 added 490 characters in body

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.

1

# 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?