2

(1) Is it true that there are no rigid spaceships in Conway's Game of Life, i.e. spaceships with period 1 i.e. spaceships of constant shape (only allowed to rotate) of non-zero translational velocity?

If so: why do such spaceships have to change their shape while moving?

How can this be seen most easily?

Are there Life-like cellular automata with rigid spaceships?

(2) Can it be shown (and how) if a) almost all spaceships have a fixed number of living cells, b) almost all spaceships have a varying number of living cells, c) neither of both?

Hans-Peter Stricker
  • 18,159
  • 1
    It is enough to look at one point and the $8$ points around it. Can you put blacks in those $9$ points such that the center doens't change? –  Apr 23 '14 at 14:35
  • I don't understand your question: if I put a "black" in the center and 2 or 3 "blacks" around it, the center will not change. So what do you mean? – Hans-Peter Stricker Apr 23 '14 at 14:46
  • But not in any way, or otherwise one of the $8$neighbors might become alive. So, the neighboring cells are kind of star-shaped. I will use that it is bounded. Then there are cells in the spaceship that have only neighbors in half (divided by a line) of its neighboring positions. This leaves even less possibilities. I think only a line ... –  Apr 23 '14 at 15:12
  • Your argument is too abstract for me. Could you please be more concrete. E.g., what precisely is the assumption of your argument? – Hans-Peter Stricker Apr 23 '14 at 15:31
  • What does 'life-like' mean? You can easily find semi-totalistic 1d 'rigid' spaceships in a 3-state automaton, and it's easy to 'stretch' those ships up (in non-semi-totalistic fashion) to 2d; with a little effort and enough states you can do it in semitotalistic fashion too. – Steven Stadnicki Apr 23 '14 at 17:55
  • @Steven: https://en.wikipedia.org/wiki/Life-like_cellular_automata – Hans-Peter Stricker Apr 23 '14 at 17:57

2 Answers2

2

In response to the first question: It can be shown that any such spaceship in the Game of Life would be of one of the two speeds c orthogonal or c/2 diagonal. Both of these speeds have been proven to be impossible, so none can exist. However, there are, in fact, life-like cellular automata that contain such spaceships. Specifically, B2 rules (i.e. ones with birth from two neighbors) often have this property.

Aidan F. Pierce
  • 1,465
0

Let us assume that the spaceship is bounded or maybe that it has only finitely many live cells. Notice that if we put live cells on every even numbered row we get a fixed configuration.

$$\begin{matrix}...&x&x&x&...\\...&o&o&o&...\\...&x&x&x&...\\...&o&o&o&...\end{matrix}$$

Now, since it is bounded we can find a live cell that has live neighbors only on a semi-plane of its neighbors. Graphically this is that at most the neighbors can be as in

$$\begin{matrix}o&x&x\\o&x&x\\o&x&x\end{matrix}$$

or $$\begin{matrix}x&x&x\\x&x&x\\o&o&o\end{matrix}$$

You get the idea. Now, if the center living cell must be preserved we can have at most $3$ living neighbors as in

$$\begin{matrix}o&x&o\\o&x&x\\o&x&o\end{matrix}$$

But the neighboring dead cells must also be preserved. So, only two living neighbors and in a row like

$$\begin{matrix}o&x&o\\o&x&o\\o&x&o\end{matrix}$$

With this same argument the row of living cells must continue indefinitely. But this can't be if the spaceship must be unbounded.

  • Why must the center living cell be preserved? (The spaceship is allowed to move, so no living cell is supposed to be preserved.) – Hans-Peter Stricker Apr 23 '14 at 16:43
  • @HansStricker I see. I used the wrong definition of period. –  Apr 23 '14 at 16:45
  • @HansStricker So, we want, after one generation to get a translation of the ship. We shouldn't allow rotation because otherwise the blinker would be of period $1$, isn't it? –  Apr 23 '14 at 17:16
  • Obviously my conception of "period" was mistaken. I wanted to define "rigid", but did it the wrong way. Because the blinker is supposed to be rigid - even when of period 2. (Please allow me to edit my question!) – Hans-Peter Stricker Apr 23 '14 at 17:45