Homework X

Sample Solutions

Problem 1.

(a) This system is not terminating as the term f(g(a,b), g(a,b), g(a,b)) cycles after three steps.

(b) this system is not confluent either as g(a,b) has two distinct normal forms, a and b.

Problem 2

(a ) This rewriting system is terminating. Each of the rules "simplifies" a term in the sense below until further simplification is impossible.

s x + y ® s (x+y) reduces the 's' applications to the left arg of +

0 + x ® x reduces the + ops

x + 0 ® x ditto

(-x) + x ® 0 ditto

(x+y) + z ® x + (y+z) moves (…) to the right

(b) This rewriting system is not confluent. Numerous conclusions based on the equations do not follow from the rewrite rules. For instance, using the equations,

-0 + 0 = -0 by the third equation, and -0 +0 = 0 by the fourth equation, and hence -0 = 0, however, the normal form of -0 is -0 and the normal form of 0 is 0! As another example, using the equations, for any integer n

--n =

--n + 0 =

--n + (-n+n) =

(--n + -n) + n =

0 + n =

n

But for any integer n, the normal form of --n is --("normal form of n"), not the normal form of n.