A Semigroup With Unsolvable Word Problem

Stephen G. Simpson

Original Draft: February 10, 2000 Current Draft: September 4, 2009

We construct a finitely presented semigroup with unsolvable word problem. We follow the exposition of the first few sections of Chapter 12 of Joseph J. Rotman, The Theory of Groups, 2nd edition, Allyn-Bacon, 1973, with the difference that Rotman uses Turing machines while we use register machines.

Our construction is based on the following fact. There is a register machine program P which computes the partial recursive function 2^{x} ↦ 0 · φ_{x}^{(1)}(x), and such that P uses only two registers, R_{1} and R_{2}. This follows easily from Exercise 1.5.10 in my Math 558 lecture notes, Foundations of Mathematics.

Note that {x : P(x) halts} is nonrecursive. In other words, given x, the problem of deciding whether P halts if started with x in R_{1} and with R_{2} empty, is unsolvable. Furthermore, we may safely assume that if P(x) halts then it halts with both registers empty.

The idea of our construction is to encode the action of P into the word problem of a semigroup S.

Let I_{1}, …, I_{l} be the instructions of P. As usual, I_{1} is the first instruction executed, and I_{0} is the halt instruction. Our semigroup S will have l + 3 generators a, b, q_{0}, q_{1}, …, q_{l}. If R_{1} and R_{2} contain x and y respectively, and if I_{m} is about to be executed, then we represent this state as a word ba^{x}q_{m}a^{y}b. Thus a serves as a counting token, and b serves as an end-of-count marker. For each m = 1, …, l, if I_{m} says “increment R_{1} and go to I_{n_{0}}”, we represent this as a production q_{m} → aq_{n_{0}} or as a relation q_{m} = aq_{n_{0}}. If I_{m} says “increment R_{2} and go to I_{n_{0}}”, we represent this as a production q_{m} → q_{n_{0}}a or as a relation q_{m} = q_{n_{0}}a. If I_{m} says “if R_{1} is empty go to I_{n_{0}} otherwise decrement R_{1} and go to I_{n_{1}}”, we represent this as a pair of productions bq_{m} → bq_{n_{0}}, aq_{m} → q_{n_{1}}, or as a pair of relations bq_{m} = bq_{n_{0}}, aq_{m} = q_{n_{1}}. If I_{m} says “if R_{2} is empty go to I_{n_{0}} otherwise decrement R_{2} and go to I_{n_{1}}”, we represent this as a pair of productions q_{m}b → q_{n_{0}}b, q_{m}a → q_{n_{1}}, or as a pair of relations q_{m}b = q_{n_{0}}b, q_{m}a = q_{n_{1}}. Thus the total number of productions or relations is l^{+} +2l^{−}, where l = l^{+} +l^{−} and l^{+} is the number of increment instructions and l^{−} is the number of decrement instructions. Let S be the semigroup described by these generators and relations.

We claim that for all x, ba^{x}q_{1}b = bq_{0}b in S if and only if P(x) halts. The “if” part is clear. For the “only if” part, assume that ba^{x}q_{1}b = bq_{0}b in S. This implies that there is a sequence of words ba^{x}q_{1}b = w_{0} = ⋯ = w_{n} = bq_{0}b where each w_{i+1} is obtained from w_{i} by a forward or backward production. We claim that the backward productions can be eliminated. In other words, if there are any backward productions, we can replace the sequence w_{0}, ⋯, w_{n} by a shorter sequence. This is actually obvious, because if there is a backward production then there must be one which is immediately followed by a forward production, and these two must be inverses of each other, because P is deterministic. Thus we see that ba^{x}q_{1}b = bq_{0}b via a sequence of forward productions. This implies that P(x) halts. Our claim is proved.