Note that BitOr[x, y] + BitAnd[x, y]  x + y and BitOr[x, y] - BitAnd[x, y]  BitXor[x, y] . The patterns below show where BitXor[x, y]  t for successive t and correspond to steps in the "munching squares" program studied on the PDP-1 computer in 1962.

The number which appears at position i is given by BitXor[i, Floor[i/2]] . (Iterating the related function BitXor[i, 2i] yields numbers whose digit sequences correspond to the rule 60 cellular automaton).

[Iterated maps from] bitwise operations Cellular automata can be thought of as analogs of iterated maps in which bitwise operations such as BitXor are used instead of ordinary arithmetic ones.

But as the picture on the next page indicates, by having appropriate blocks 5 cells wide rule 30 can actually be made to emulate Rule 30 set up to emulate a single Xor operation—as used in a step of rule 90 evolution. … The picture shows that for each possible combination of inputs, the result from the rule 30 evolution corresponds exactly to the output from the Xor .

Note that ⊻ stands for Xor .

And in this case cellular automaton rules become logic expressions: • Rule 254: Or[p, q, r] • Rule 250: Or[p, r] • Rule 90: Xor[p, r] • Rule 30: Xor[p, Or[q, r]] • Rule 110: Xor[Or[p, q], And[p, q, r]] (Note that Not[p] corresponds to 1 - p , And[p, q] to p q , Xor[p, q] to Mod[p + q, 2] and Or[p, q] to Mod[p q + p + q, 2] .)

A few have distinct words for Or and Xor : examples are Latin with vel and aut and Finnish with vai and tai . … Essentially all computer languages support And , Or and Not as ways to combine logical statements; many support And , Or and Xor as bitwise operations.

The functions And , Xor and Not are equivalent to Times , Plus and 1 - # & for variables modulo 2, and in this case algebraic functions like PolynomialReduce can be used for minimization.

Particularly dramatic are the concatenation systems discussed on page 913 , as well as successive rows in nested patterns such as Flatten[IntegerDigits[NestList[BitXor[#, 2 #] &, 1, 500], 2]] and sequences based on numbers such as Flatten[Table[If[GCD[i, j]  0, 1, 0], {i, 1000}, {j, i}]] (see page 613 ).

The maximal length turns out always to be realized for the simple parity function Xor , as well as its negation.