On Mon Jan 17, 2000, Stephen Silver wrote:Subject: phoenices

A phoenix is a pattern all cells of which die in every generation, but

which never dies as a whole. All phoenices, oscillators and spaceships

in this post are assumed to be finite.

It's easy to show that a spaceship cannot be a phoenix (see proof

below), so I'm mainly interested in phoenix oscillators. The existence

of p2 phoenix oscillators is well-known, but what about higher periods?

I can prove that there are no p3 examples (see proof below) but I can't

see any obvious reason why there shouldn't be a p4 phoenix, or a p5

phoenix, for example. I modified a copy of lifesrc to look only for

phoenices, but my small scale searches so far haven't revealed any

meaningful partial results for periods greater than 2, let alone a

complete oscillator.

Has anyone else looked at this problem?

Stephen

Here are the promised proofs:

Theorem A. No phoenix can ever extend more than one space outside its

original bounding box.

Proof. Suppose it is about to extend two spaces to the right of the

original bounding box for the first time. Then we have

where the ? cells are inside the original bounding box and the O cells

are just outside it. The O cells must be newborn, so all the ? cells

must have been ON in the previous generation in order to give birth to

the central O cell. In the current generation the ? cells are therefore

OFF. So the central O cell has exactly two neighbours and will survive

into the next generation - a contradiction.

Corollary A1. Every phoenix evolves into a phoenix oscillator.

Corollary A2. No spaceship is a phoenix.

Note. The theorem holds in a number of other cellular automata.

The proof requires only that births not be possible with less than

3 neighbours and that survival occurs with a particular arrangement

of 2 neighbours.

Theorem B. If an oscillator is such that no cell is ON in more than one

phase then it is either a still life or a statorless p2.

Proof. Suppose there is a counterexample. Cells ON in some chosen phase

will be said to be of type Z. Those ON in the previous phase will be called

type Y, those on in the phase before that will be type X, and those of the

phase before that type W. Since the period is at least 3 these types are

all distinct, except that we may have W=Z.

In the following diagrams . marks a cell that is definitely not in the

rotor (and is therefore permanently off), while known rotor cells are marked

Z, Y, X or W according to their type. Cells which are unknown or not

discussed here are marked with a ?.

Consider the leftmost column of the rotor, and in particular the uppermost

rotor cell of this column. We can assume this cell is of type Z. Three of

its neighbours will be of type Y, namely its parents.

Consider the cell to the right of the Z cell (marked x here):

If x is of type Y then it has at least two Y neighbours and so at least

four (to kill it off). It also has three X neighbours (its parents).

Together with its Z neighbour and its non-rotor neighbour this is a total

of nine neighbours. This contradiction shows that x is not of type Y, so

we have the following diagram:

where I have marked in the three X parents of the leftmost Y. But now the

leftmost X has no room for its own W parents.

So the counterexample does not exist.

Corollary B1. There is no p3 phoenix.