The photon/XOR system

(October 15, 2007)

This is a one-dimensional CA-like system, in which a single "photon" (here colored blue) moves left and right within an infinite array of cells which are otherwise ON (black) or OFF (white).

Each row represents one generation of the system. The cells in each row lie midway between the cells of the previous row. The regular ON and OFF cells follow the XOR rule, meaning that a cell is ON if and only if exactly one of the two cells above it is ON. The photon moves in the direction it is facing until it hits an ON cell, in which case it switches direction. The photon counts as an OFF cell for XOR purposes.

In the above picture, the starting configuration has the photon facing left, surrounded by two ON cells, one on each side of the photon. Of course, other starting configurations are possible.

Here is the same initial configuration run to 100 generations:

This system was discovered by David Eppstein in August 2001, in the form of the following pattern for the 2D rule B25/S4:

Each three generations of the above pattern represent one generation in the photon/XOR system.

The amazing thing about this system is that the photon seems to describe a pseudorandom walk. Meaning the following. Let us represent the states of the photon as a binary sequence of L's (for left) and R's (for right). Then, for the above starting configuration, we obtain the following sequence:

LRLRR LLRLL LLRRL RLRLR LRLLL RRRLL RRLLL LRLRR LRLLR RRLLR RRLRR LRLLL RRRRR RLRRR RRRRR LLRRL LLRLR LLRRL RRLLR LLLRL RRRRR RLLRL RLRRL RRRRR RLRRL LLLLR LLLRR LRLLL LLLRL RRLLR RRRRR LRRRR RLRRL RLLLR RLLLR RRLLL RRRRL RRRLL LRLRR LRLLL LLRLL RLRRR RRRRL RRLLL RLLRR RRRLR RLRRL RLRLL LLRLR LLLLR RLLLR RRRRL RLRRL RLLLR RLRRR RRLRL LLRRL LLRRL RLRLL RRRRR RLRLR RRLRR RRRLL RRLRR LLRRR RLRLR RLLLR RLLRR LRLRL RRRRR RRRLR LRLRR LRLRL RLRRL LLLLL RRRRL RRRLR RRLLL LRRRL RRRLR RRRRL LLLLL RLRLR LLLRR RLRRR RRRRL RLLRR RLLLL LLRLR RRLLR LRLLL LLRRL LRRRR RLRLL LRLLR LRRRL LRRLR LLLLR LLLLR LRRRR RRRRR RLRLL LRLLL LRLRL RLRLL LLLRL RRRRR RRRRL RLRRL LRLLR LRLLL RLRLL RRLLL LRLRL RRLRL LRRLL RLRRL RRLRL LLLRR RRRLR LLRLR RLRLR RLRLL LLLRR LLLLR RRLLR RLRRR LLLLR LRRRR LRLLL LLLLL LLLLR LLRLR RLLRL LRRRR LRRLR LRLLL RRRRR LRLLL LRLRL LRLLL RLLLL LRLRL RLRRL LRLLR RLLLR RRRRR RRLRR LLRRL RLLRR RRRLL LRRLR LRLRL RRLRL LLLLL LRLRL LRLRR RLLLR LLLRR LLLRR RLRLR LRLRR LRLRL RLRRL LLLRR RRLRR LRRLL LLRRL RRRLR RLRRR RRLRR RRRRR LLLLL LLLRR RLLRR RRLRR LRRLR RLRRL RRRLL RRRRR LRRRL RLRRL RLRRL LRLRL LLRLR LLRRR RLLLR LRRRL RRRLL RLLRR LLLRR RLLRR RLRRL LLRLR LLRRL LLRLR RLRRL LRRLL RRRRR LLRRR RRLLR LLRLR RRRLL LLLRR RRLRL LRLLL LLLLR RRLRL LRLRL LRRLL RLRLR LRLLR RLRRR RLLLL RRRLR LRRRL LLLLL RLLLR RRLLR RLRRR RRLRR LLRRR RRLLL LRRRL RRLLR LLLLL LLRLR LLLRL RRRLR LLRLR RLLLR LLRRR LLLRR RLRLL RRRLR LRLRL RLRRR LRLLL LLRRL LLLLL RLLLR RRRLL RLRRR RLLLL RRRLL LLRLL LRLLL LRLRL LRRLR LLLRR LRRRR LRLLR RLLRR LLLLL RLLLL RLRRL LLRLL LLLRR LRLRL RLLLL RLRLR RLLRR LLLLL LLLLR LRRLR RRRLR RRLLL RRRLL RLLLR LLRRL RLLRR RRLRL RLRLR LLLRR RLRRR LLRRR LRRLR LLLRL LRRRR RRRRR RRRLR LRRLR LLRRL RRLRL LLLLL LLRLL RLRRR LLRLR RRLRL LRRRR RRRLL LRLLL RLLRR RLLLR RLLRL RLRLR LRLRL RRRRL RRRRR RRLLR LRRRR RLLLL LRRLR LRRRR LLRRR LRLLR RLRLL RRLRR LLLLL RLLLR RRRLR LLRRR LLRLL LRRRR LLLRR RLLLL RRRLR RRRLL RLRRL LRLLR LLRRL LLLLR LLRRL RRRLL LRRRR RRLRR RLRRR LRLRL RRLRL RLRLR RLRLR RLLLR RLRRL LRLRR RLLLR LLRLL LLLLR RRLLL RLLRL RRLLR LRRLR RRRLR RLLRL RLLRR LLLLR LLRLL RLRLR LLLRL LRLRL RLLRR RLLLL RLLLL RLLRL RLLLR RLLRL RRRLR RRLRL LRRRL LLLLL LRRRL LRRRR LLRRR LLLRL RRLRL RRLLR RRRLR RRLRL LLLRR LRLRL LLLLL RRRRL RLLRL RLLRL LRRLL LRRLR RLRRR RRLLL RLLRR RLLRL RLRLL RRLRR RRRRR RRRLL LRRLL LLRRR LLLRR RLRLL LRLRL RLRRL LLLLL RLRRL RRLRL RRLRL RLLRR LRRLL RLLLR RLLRL RLLLR LLLLL RLLRR ...

This sequence seems statistically indistinguishable from a truly random binary sequence, as far as we have tested. Similarly, other starting configurations produce other pseudorandom sequences.

In this page we summarize what we know about the photon/XOR system.

Basic properties

Every finite sequence of L's and R's can be achieved by providing an appropriate initial condition. In fact, a given sequence of L's and R's uniquely forces an inverted cone of ON and OFF cells around it.

For example, let us take an arbitrary sequence of length 12, like RRLLLRRLLLLL. This sequence forces the following cone:

Also, each infinite state of the universe has exactly two predecessors, one with the photon facing left and one with the photon facing right. (These predecessors might have infinitely many ON cells.) For example, the starting configuration used above:

has these two predecessors:

Also, it is not hard to show that for any starting configuration with finitely many ON cells, with at least one ON cell on each side of the photon, the resulting sequence of L's and R's is necessarily aperiodic, and contains infinitely many of both L's and R's.

Running in time O(n log n)

Say we are given an initial photon/XOR configuration with a finite number of ON cells, and we want to generate the resulting sequence of states of the photon:

RLLLL RRRLR RLLRR LLLLR RRRRL RLLLR LRRRR LRRRR LLLLR LLLRL LLRRL LLRRL ...

The simplest approach would be to run the system one step at a time. Then, it would take time O(n²) to produce the first n characters of the sequence, since after each step the active portion of the universe expands by one cell.

However, it is possible to generate the first n terms of sequence in time O(n log n). The algorithm we describe here was found by Tomas Rokicki in August 2001.

More on the XOR rule

The algorithm is based on the fact that, in the absence of the photon, the XOR rule is very easy to calculate far into the future. So let us first look at the XOR rule more closely.

For convenience, let us align the cells so that the cells of each row lie directly below the cells of the previous row. We now define the state of each cell to be the XOR of the cell above it and the cell above-right of it:

Denote by C_g(i) the i-th cell at generation g. Then the evolution rule is C_g₊₁(i) = C_g(i) ⊕ C_g(i+1), where ⊕ denotes XOR.

Now comes the key observation: It is easy to advance a pattern k generations into the future, if k is a power of two. This is due to the following fact:

If k is a power of two, then C_g₊_k(i) = C_g(i) ⊕ C_g(i+k).

Now consider the following problem: We are given an initial configuration consisting on n cells, and we want to obtain the sequence of the first n states of the leftmost cell:

Again, the naive approach would involve computing the whole triangle of states, which would take time O(n²). However, it is possible to compute this sequence in time O(n log n).

To do this, we partition the cells into blocks, which we call plateaus. The "zeroth" plateau contains just the leftmost cell; the first plateau contains the next 2 cells; the second plateau contains the next 4 cells; and so on. In general, the ith plateau contains 2ⁱ cells, for i = 0, 1, 2, 3, ....

We advanve the cells in the ith plateau in steps of 2ⁱ. Thus, at step k of the algorithm, the zeroth plateau is at generation k; the first plateau is at the largest generation divisible by 2 not larger than k; the second plateau is at the largest generation divisible by 4 not larger than k; and so on. For example, at step 11, the cells of the system are at the following generations:

(We do not actually store these generation numbers. They can be deduced by knowing that we are at step 11.)

Let us see how to advance the system to step 12. The zeroth plateau is advanced to generation 12 by performing a triple XOR of three adjacent cells:

The first plateau is advanced to generation 12 by performing, for each cell in it, a triple XOR of cells with separation 2:

Finally, the second plateau is advanced to generation 12 by performing, for each cell in it, a double XOR of cells with separation 4:

Now the system is at step 12, as desired.

The general rule is as follows: Let z(k) denote the number of trailing zeros in the binary representation of k. Then, to advance the system from step k–1 to step k, we advance the first z(k) plateaus by triple XORs, and the next plateau by double XORs. In our example we had k = 12 = 1100₂, so z(k) = 2. Hence, we performed triple XORs on the first two plateaus (the zeroth and the first) and double XORs on the second plateau.

We leave as an exercise to show that this algorithm is correct and indeed runs in time O(n log n).

Back to the photon/XOR system

Let us apply this technique to the photon/XOR system.

We keep the cells left and right of the photon in separate arrays, in the "plateau format" described above. And we keep the current state of the photon (L or R) as a boolean value. For example, at generation 11 we might have the following configuration:

(Again, we do not actually store the generation numbers of the cells. They can be deduced by knowing that we are at step 11.)

Let us see how to advance the system to step 12. Since the photon is facing left, we have to add one extra cell at the beginning of the right array. This extra cell is ON, just like the first cell in the right array. Furthermore, since the first cell in the left array is ON, the photon now turns to the right:

Next, we advance the left and right arrays from step 11 to step 12, via the technique of triple XORs and double XORs explained above:

There's just one problem remaining: Because of the extra cell added to the right array, the boundaries of the plateaus are now in the wrong positions. To correct this, we have to backtrack the last cell in some plateaus to an earlier generation. This is done by performing double XORs:

To know which cells to backtrack at step k, represent k in binary. Number the digits in the binary representation of k as 0, 1, 2, ... from right to left. For each i, if the ith digit is a 1, then we have to backtrack by 2ⁱ generations the cell that used to be the last cell of the ith plateau. We do this by XORing this cell with a cell 2ⁱ units farther away. Then the cell becomes the first cell of the (i+1)-st plateau. In our case we had k = 12 = 1100₂; therefore we backtracked the cells that used to be the last cells of the second and third plateaus.

Code