LXOR Cellular Automata and Perpendicular Causation


Experience isn’t interesting until it begins to repeat itself – in fact, till it does that, it hardly is experience.

                                                                             Elizabeth Bowen, 1938


In another note we discussed the operation of forming a successor to a string of binary bits by taking the bit-wise exclusive OR of that string with the same string rotated one bit to the left. We will use LXOR to refer to this operation. (If we took the XOR of the string and the same string rotated one bit to the right, we would call this operation RXOR.) This operation can be regarded as a rule for cellular automata. For example, the figure on the left below shows a complete cycle (period 126) of the LXOR operator applied to 18-bit strings, with the initial seed value of 5. The progression is upward, beginning with the seed at the bottom.


Since the 18 bits are arranged and rotated in a loop, we could just as well consider an infinite string of bits with period 18. This is shown, for four 18-bit cycles, in the figure on the right, which is really just putting four of the left-hand figures end-to-end. It’s interesting that this infinite 2-dimensional plane of binary bits is periodic in two different directions, with a period of 126 in the vertical direction and a period of 18 in the horizontal direction. Thus the ratio of periods is 7:1. This is reminiscent of elliptic functions in the complex plane that are period in two different directions.


The pattern that emerges with 18-bit strings depends on the initial seed value. As discussed in the previous note, there are 519 distinct cycles of period 126. There is some variety in these results, but the patterns are fairly uniform. However, for strings of other lengths there is much more variety in the patterns that emerge from the simple LXOR operation. For example, the figure below shows the initial evolution of a 19-bit string with seed 7.



This shows only about the first 500 iterations, but the actual period of this operation is 9709. For another example, the figure below shows the first 256 iterations of a 29-bit string, with four string cycles shown side by side.



One of the most interesting features of these cellular automata is that the same rule of formation applies both vertically and horizontally. This is easily seen by noting that if a,b are two consecutive bits of a string, and if aʹ,bʹ are the corresponding bits in the successor string, then by definition aʹ = a XOR b. But we can apply the XOR operation to both sides with bit a, to give



Thus the elements of the space satisfy the same law of evolution in two perpendicular directions. In other words, the very same operation that generates the plane from a given horizontal seed also generates the plane from a corresponding vertical seed. In general the iteration may have different periods in the two directions, although there are “square” examples in which the periods are the same in both directions. It follows that, just as there are cycles of period 9709 for 19-bit strings, there are also cycles of period 19 for 9709-bit strings.


It also worth noting that although each string has a unique successor, it does not have a unique predecessor. As discussed in the previous note, each string has either two complementary predecessors, or no predecessor. So, although a given seed string can be uniquely extrapolated in one direction, it cannot be uniquely extrapolated in the other. With each step in the non-unique direction, we must either choose between two possible strings, or else find that there is no possible string.


The iteration rule in cellular automata is sometimes regarded as representing causation, and it certainly enables us to solve the “Cauchy problem” by extrapolating from a given “initial condition”. On the other hand, most physical situations exhibit temporal symmetry in their

“laws”, so they can be extrapolated both forward and backward in time, whereas this LXOR iteration cannot be uniquely extrapolated backward. However, the LXOR iteration shows that the flow of causation is ambiguous, because the plane of bits satisfies the same formative rule in two perpendicular directions. It’s as if we can just as well regard either the vertical or the horizontal direction as the “space” dimension, and the other as the “time” dimension. In both cases, the same law of evolution is satisfied, and yet the two coincident but perpendicular universes would appear to be very different to their inhabitants.


Return to MathPages Main Menu