MIT 6.044J/18.423J Handout 24 6.044 Fall 1996 13 December, 1996 The Word Problem for Semigroups is Undecidable by A. R. Meyer and Gillian Bidgood Semigroup Equations In these notes we consider equations which hold for algebras with an associative binary operation. Such algebras are called semi-groups. Formally, a semi-group is defined to consist of: 1. a nonempty set called the domain of the semigroup, whose members are called "elements" of the semigroup. For example, the domain might be "the integers mod 17" or "all strings made up entirely of a's and b's". 2. an associative binary operator, *, on the domain. In other words, if S and T are elements of the semigroup, so is S*T. As an illustration of where semigroups might arise, consider the eight "rigid automorphisms" of the square: rotate (n * p/2) radians clockwise for n=0,1,2,3; reflect about (1) horizontal, (2) vertical, (3) upper left to lower right diagonal, and (4) the other diagonal. We can define a binary operation, *, on these rigid automorphisms, namely S * T means "do S then do T". This operation is associative, and in fact S * T is always one of the eight above when S and T are. So these eight automorphisms are the elements of a semigroup called "The Rigid Automorphisms of the Square" (RAS) with the binary operation *. Suppose A and B respectively denote rotating the square 0 and pi/2 radians clockwise, and R represents reflecting about the vertical axis, then B*R denotes rotating pi/2 radians and then reflecting. Similarly, R*B*B*B denotes reflecting and then rotating 3 pi/2. Now we notice that the net effect of doing the sequence of automorphisms denoted by R*B*B*B is the SAME that denoted by B*R--as the reader should verify. So we say that the semigroup equation B*R = R*B*B*B is TRUE in RAS. Note that since * is associative, we have omitted parentheses in the expressions above. In fact, it is conventional to omit the operation * as well and just write BR = RBBB (1) A sequence of symbols such as RBBB from an alphabet denoting semigroup elements is called a "word" over the semiigroup alphabet. Since A is the "do-nothing", or "indentity", automorphism, the following equations are obviously also true: AB = B, BA = B, AR = R, RA = R, and AA = A. (2) Two more easily verified equations are A = BBBB and A = RR. (3) It is easy to use these equations to deduce many new ones. For example, (BR)B = (RBBB)B = R(BBBB) = RA = R, so we conclude that BRB = R. In fact, it is not hard to show that EVERY equation between words over the alphabet {A, B, R} which is true in RAS follows simply by repeatedly rewriting the lefthand sides of one the equations labelled (1-3) by their corresponding righthand sides, or vice-versa. That is, (1-3) are a COMPLETE set of axioms for word equations over this semigroup. Formally, define a relation --(1-3)--> between words by the condition that W_1 --(1-3)--> W_2 iff for some words U,S,T,V, the word W_1 is of the form USV, and W_2 is of the form UTV, and either "S = T" or "T = S" is one of the equations (1-3) above. Let --(1-3)*-> denote the transitive closure of --(1-3)-->. We define a proof system with just the inference rule W_1 --(1-3)*-> W_2 ------------------ W_1 = W_2 and claim that this proof system proves exactly the word equations true in RAS. Exercise 1. (a). Explain how to rewrite any word over alphabet {A, B, R} into one of the following "CANONICAL" words A, B, BB, BBB, R, RB, RBB, RBBB, using axioms (1-3). (b) Using the fact that there are only eight rigid automorphisms of the square, conclude from part (a) that two words over {A, B, R} denote the same automorphisms IFF they can be rewritten to the same canonical word. (c) Conclude that the proof system above is a COMPLETE axiom system for word equations over RAS. (d) From part (c) we immediately conclude that the true word equations of RAS are half-decidable. Prove that they are actually decidable. (As an aside, we also note RAS satisfies the additional properties that (1) there is an identity element, and (2) every element has a 2-sided "inverse". So RAS is in fact what mathematicians would call a "group".) The Word Problem for Semigroups The example in the previous section illustrates a typical situation in semigroup theory: we are given some finite set script_E of word equations, and we want to know whether another word equation follows from them by repeatedly rewriting one side of equations in script_E by their other sides. This problem is called the Semigroup Word Problem. More precisely, we define the Semigroup Word Problem (SWP) to be the set of sequences of word equations such that the last equation in the sequence follows by rewriting from the preceding equations in the sequence. For example, we observed in the previous section that the sequence ( BR = RBBB, BBBB = A, RA = R, BRB = R ) is in SWP. But the equations used to prove BRB = R are not enough to prove the equation RR = A, even though RR = A is true over RAS. That is, ( BR = RBBB, BBBB = A, RA = R, RR = A ) is NOT in SWP. Exercise 2. Prove that ( BR = RBBB, BBBB = A, RA = R, RR = A ) is NOT in SWP. HINT: R's are preserved by rewriting. Exercise 3. Explain why SWP is half-decidable. We will prove in these notes THEOREM (SWP). The Semigroup Word Problem is not decidable. The proof will follow from showing how, given any 2-counter machine, M, to construct a sequence Q_M of word equations such that Q_M is in SWP iff M halts. Since we know that the halting problem for 2-counter machines is undecidable, this implies that SWP must also be undecidable. Actually, instead of the halting problem for 2-CM's it will be technically convenient to use the "cleanly-halting problem". A 2-CM, M, is said to "cleanly halt" if, started at instruction number zero with empty counters, it halts by transfering to the smallest possible halting line number with with its counters empty again. That is, starting in configuration (0, 0, 0), M halts in configuration (n, 0, 0) where n = length(M). Exercise 4. Prove that the cleanly-halting problem for 2-counter machines is undecidable. HINT: For any M, it is easy to add a few lines of "post-processor" instructions which, when M would halt, will clear the registers and then do a goto to the smallest halting line number. Let step_M(k, l, m) be the configuration, if any, which follows from configuration (k, l, m) by one step of M; step_M(k, l, m) is undefined if (k, l, m) is a halting configuration for M. Also, let n = length(M). The idea behind our proof will be to represent a configuration (k, l, m) by the "configuration word," rep(k, l, m), over the alphabet {$, !, 0, ..., n}. Namely, define rep(k, l, m) ::= $ !.....! k !.....! $ \ / \ / \_/ \_/ (l !'s) (m !'s) Next we will introduce word rewriting rules R_M corresponding to the instructions of M. These rules will have the following key property: LEMMA (One-Way Simulation). rep(k, l, m) --(R_M)--> rep(k', l', m') iff step_M(k, l, m) = (k', l', m'). From the One-way Simulation Lemma we can immediately conclude that M cleanly halts iff rep(0, 0, 0) --(R_M)*-> rep(n, 0, 0). So if we could always decide whether one word rewrote to another according to any given set of rewrite rules, then we could also decide the cleanly-halting problem. This implies: THEOREM (Undecidable One-Way Word Rewriting). The problem, given a finite set, R, of word rewriting rules and two words U, V, whether U --(R)*-> V is undecidable. To deduce the undecidability of the SWP, we have to consider rules which allow rewriting in "either direction." We'll take this up in the next section. For now, let's develop the one-way rules. To construct R_M, we remember that M is a length n sequence of instructions of the forms inc1 increment first register inc2 increment second register dec1 decrement first register, except leave it alone if it is 0. dec2 decrement second register, except leave it alone if it is 0. ifr1 a b if register 1 is zero, go to line a, otherwise go to line b ifr2 a b if register 2 is zero, go to line a, otherwise go to line b Now R_M is defined as folows; If the i^th instruction is -------- include the rules ------------- inc1 i --> ! i+1 inc2 i --> i+1 ! dec1 ! i --> i+1 $ i --> $ i+1 dec2 i ! --> i+1 i $ --> i+1 $ ifr1 a b $ i --> $ a ! i --> $ b ifr2 a b i $ --> a $ i ! --> b ! For example, if M was the sequence of instructions, inc1 ifr2 3 17 dec2 ifr1 2 4 inc1 then, remembering that instructions are numbered starting at zero, the resulting rules would be: 0 --> ! 1 1 $ --> 3 $ 1 ! --> 17 ! 2 ! --> 3 2 $ --> 3 $ $ 3 --> $ 2 ! 3 --> ! 4 4 --> ! 5 It is now easy to check that the One-Way Simulation Lemma follows immediately from the definitions of --(R_M)--> and step_M. Two-Way Rewriting The One-Way Simulation Lemma reveals that rewriting according to the rules R_M corresponds exactly to steps performed by M. Now if we let E_M be the equations obtained from R_M (by replacing "-->" by "="), then E_M rewriting is exactly forward AND BACKWARD R_M rewriting. But if we allow rewriting backwards, that is, from a righthand side of a rule of R_M to its lefthand side, could there be an unintended way to rewrite one configuration word into another? The answer is "yes;" there are configuration words which two-way rewrite to one another but neither leads to the other by steps of M. Nevertheless, two-way rewriting corresponds in a manageable way to steps of M. Note that a given configuration of M may not have a unique preceding configuration, and consequently a configuration word may rewrite "backwards" in more than one way. For example, suppose the zeroth and first instructions of M were both (ifr1 2 2). Then configurations (0, l, m) and (1, l, m) both lead in one step to configuration (2, l, m). This implies that rep(2, l, m) could rewrite backwards to both rep(0, l, m) and rep(1, l, m). LEMMA (Two-Way Simulation). Let S be a configuration word of M. (1) If S --(E_M)--> T, then T is also a configuration word of M. (2) If S --(E_M)*-> T, then there is an configuration word U such that S --(R_M)*-> U and T --(R_M)*-> U. Proof: (1) follows by definition of the rules of R_M, as the reader may verify. To prove (2), assume S --(E_M)*-> T. Consider the shortest sequence of words starting at S and going by single two-way rewriting steps to T. By (1), every word in this sequence is a configuration word. Suppose there are three consecutive words V, W, X in this sequence which follow by a backward rewriting followed by a forward rewriting. In other words, we have V <--(R_M)-- W --(R_M)--> X , which is to say W --(R_M)--> V and W --(R_M)--> X. Now by One-Way Simulation, V is the configuration word corresponding to one step of M from the W configuration. And so is X. But the next configuration of M is uniquely determined by the current configuration, so it must be that V and X are the same word! Thus the two steps which rewrite V to W to X are actually rewriting V to itself. This means that we could find a shorter sequence of two-way rewritings from S to T by removing these rewritings of X to itself. This contradicts our choice of the shortest sequence of rewriting form S to T. So in the shortest sequence of two-way rewritings from S to T, the rewritings from S must begin with (zero or more) forward rewritings to some word U, and then be followed by (zero or more) backward rewritings to T. QED. COROLLARY 1: Let T be a configuration word which represents a halting configuration of M. Then for all words S, S two-way rewrites to T iff S one-way rewrites to T: S --(E_M)*-> T iff S --(R_M)*-> T Proof: By the Two-Way Simulation Lemma, there is a two-way rewriting form S to T in which the only backward rewritings are at the end. But since T represents a halting configuration, it follows by One-Way Simulation that no word rewrites backwards into T. So this rewriting from S to T must consist soley of forward rewritings. QED. So we conclude, COROLLARY 2. The equation rep(0, 0, 0) = rep(n, 0, 0) is provable by rewriting from the equations E_M iff M cleanly halts. So let Q_M be the equation sequence E_M followed by the equation rep(0,0,0) = rep(length(M),0,0). Now by Corollary 2, M cleanly halts if Q_M is in SWP. This completes the proof of Theorem (SWP).