On August 9, 1998, Stephen Silver wrote:Dieter Leithner recently sent me all the superstring postings, which
predate my joining this list. As Nathan Thompson pointed out at the
time, all of Peter Rott's superstrings have even period. It turns out
that there is a very good reason for this: odd-period superstrings are
not possible in Life.
The proof is not very difficult. The first thing to note is that the
second row of a superstring behaves like the 1-D cellular automaton
with rule B01S0. This is a self-dual rule. To get an odd-period
superstring we need an odd-period agar in this 1-D rule. There is
one very obvious such agar, an alternating sequence of ON and OFF cells,
which is p1. This agar, however, can never give an odd-period superstring.
To see this it is necessary to examine the third row of the superstring.
For half the cells the picture looks like this (the superstring is moving
up the page):
It is clear that whatever the ?s represent, the middle cell of the
third row will be OFF in the following generation, and similarly in all
future generations. Since the superstring is assumed to be periodic this
cell must already be OFF. For the other cells in the third row the picture
now looks like this:
If ? is ON, then the middle cell of the third row will be OFF in the
following generation. But if ? is OFF, then it will be ON. So the third
row is p2.
So if we could prove that the 1-D rule has no odd-period agar other than the
one discussed above then we could immediately conclude that there are no
odd-period superstrings. In fact something stronger holds:
Claim: With the exception of the trivial p1 agar, all agars in the 1-D rule
are p2 and statorless.
To prove this, consider the four-cell sequence 0010. You can easily check
that this can only arise from the sequence 110101. And the middle part of
this sequence, 1010, can only arise from 010101. So the pattern 0010 can
only arise in a position which has previously always been 1010, it can never
be part of an agar (which is, by definition, periodic). By duality and
symmetry the same applies to 0100, 1101 and 1011. But this means that the
only agar that contains the sequence 010 (or 101) is the p1 agar discussed
above. The only three-cell sequences that can occur in other agars are 000,
001, 011, 100, 110 and 111, and in all these cases the middle cell changes
state. The agar is therefore p2 and statorless, as claimed.
---
Note that the above proof shows that (periodic) superstrings fall naturally
into two classes, those with a p1 second row and those with a p2 second row.
I will call these Class 1 and Class 2, respectively (not to be confused with
Peter Rott's Type 1 and Type 2). The examples that Peter Rott posted in
August 1996 are almost all Class 2.
This division into Class 1 and Class 2 works not only for Life, but for
any rule in the range B3S23 to B12345678S0123678 (although some of these
rules may not admit periodic superstrings at all). However, my proof that
Class 1 superstrings have a p2 third row doesn't work if births can occur
with 5, 6, 7 or 8 neighbours, such as in HighLife. (In fact it is possible
in HighLife for a Class 1 superstring to have a p1 third row, but I haven't
made any serious attempt to determine if such a superstring can have an
overall odd period.)