Two Forbidden Directions

[Sam Alexander]

Hello everybody, first time posting here I'm Sam Alexander, a logic phd student from Ohio State University. Used to think Life was just a silly diversion, until I realized it was a fertile ground for applying some graph theory I've been doing, and then when I started studying it I finally saw how deep the game is

Anyway, as I said, I've been doing some graph theory and found a way to apply it to Life. In this post, Nathaniel said:

c/3 seems to be the upper diagonal limit for rules without "2" in the birth list, and I'm not sure why *that* is.

I think I can explain that using this result I got called the Two Forbidden Directions result.

Definition: Given an initial life configuration, a "lifeline" is an infinite sequence c(1),c(2),... of cells, such that for every n:
1. c(n) is live in generation n
2. c(n+1)=c(n) or c(n+1) is a neighbor of c(n)

Basically, a lifeline is a way of "walking" through the game of life. You're only allowed to walk on live cells, and at each generation, you're allowed to stand still where you were, or walk to a neighbor. Here's an illustration of a lifeline in the glider, the blue cells are the lifeline:



Here's a theorem I proved using some new graph theory:

Theorem: Suppose you have an initial configuration with finitely many live cells, and that in the resulting Game of Life, the board doesn't ever become completely dead. Suppose any two directions (from among north, south, east, west, NE, NW, NE, SW, SE, "stand still") are "forbidden". Then, in the resulting Game of Life, there is a lifeline which never takes either of the forbidden directions.

For example, with the southeast-moving glider, the theorem guarantees we can find a lifeline which never goes (say) south nor southeast. Which is surprising since the glider itself moves southeast. In fact, the lifeline in the above illustration, is exactly such a lifeline, it only goes E, SW, and "stand still".

In fact, the theorem doesn't even use all the rules of life. It only uses that birth requires 3+ neighbors and survival requires 2+ neighbors. Thus, it's relevant to Nathaniel's question. The two following corollaries actually apply to any such ruleset...

Corollary 1: A spaceship can't move in a horizontal direction faster than c/2.

Proof: By symmetry, assume such a spaceship moves north. By the theorem, there's a lifeline which never steps north nor northeast. The lifeline must move at least as fast as the spaceship, or it would get "left behind". But the lifeline can move northward with at most speed c/2 because to move N cells north without ever stepping north or northeast, you'd have to take at least 2N steps, e.g. N steps northwest + N steps east. Thus, the spaceship itself can move with at most speed c/2.

Corollary 2: A spaceship can't move in a diagonal direction faster than c/3.

Proof: By symmetry, assume such a spaceship moves southeast. By the theorem, there's a lifeline which never steps southeast nor south. The lifeline must move at least as fast as the spaceship, or it would get left behind. But it cannot move southeast faster than c/3, because to move N cells southeast without ever stepping southeast or stepping south, requires at least 3N steps: N steps southwest + 2N steps east, for instance. Thus, the ship itself has c/3 as a speed limit.

(Of course, for Life, c/3 is not the optimal diagonal speed limit, c/4 is. I'm still trying to modify my argument to give a c/4 diagonal speed limit proof for Life. Anyway, at least Nathaniel's question is addressed)

Read more here: Applications to Conway's Game of Life

[137ben]

Wow! You have set a new upper bound on spaceship speeds for a large number of rules. Could you post the proofs here, or provide a link?

[Sam Alexander]

Here's a direct proof of the Two Forbidden Directions result, without using any of my more general graph theory. The drawback for the directness & elementariness is that it must seem "pulled out of my hat". I never would have stumbled on it without the more general stuff... Also I think the proof using my machinery is a lot more beautiful. This direct proof is rather laborious...


Theorem: Take any modification of Game of Life where survival requires 2+ neighbors and birth requires 3+ neighbors. Take any finite initial configuration which never goes totally extinct. Take any two directions (from among N, S, E, W, NE, NW, SE, SW, and "stand still") and call them "forbidden". Then there exists an infinite lifeline for the given initial configuration, which never steps in either of the two forbidden directions.

Proof: Let u and v be the forbidden directions. Without loss of generality we can assume they're different. Let u' and v' be their opposite directions (where the opposite of "stand still" is "stand still"). Define a "finite lifeline" to be a finite sequence c(1),...,c(n) of cells such that for all i=1,2,...,n, c(i) is live in generation i and, if i<n, then c(i)=c(i+1) or c(i) is a neighbor of c(i+1). This finite lifeline is said to have length n.

Claim 1: For any generation n and any cell x alive in generation n, there is a finite lifeline c(1),...,c(n) which never goes in direction u or v, and which ends with c(n)=x.

Proof: By induction. Obvious if n=1 (take the trivial sequence c(1)=x). Suppose n>1.

Case 1: x is born in generation n (x was dead in generation n-1). Then x has at least three live neighbors in generation n-1. At least one of them is *not* the cell in the u' or v' direction from x. Call this one y. By induction, find a finite lifeline c(1),...,c(n-1) with c(n-1)=y and which never goes directions u or v. Extend it by setting c(n)=x. By choice of y, this extension preserves the property of being a finite lifeline and of never going direction u or v.

Case 2: x survived into generation n (x was live in generation n-1).
--Subcase 1: "stand still" is one of the forbidden directions. By relabeling if needed, we can assume "stand still"=u and hence v is not "stand still". Since x survived from generation n-1 into generation n, there were two live neighbors of x in generation n-1. At least one of them, y, is not the v' neighbor of x. Now proceed as in case 1.
--Subcase 2: "stand still" is not one of the forbidden directions. Then let y=x and proceed as in Case 1.

This establishes Claim 1.

Claim 2: There are arbitrarily long finite lifelines which never go direction u or v.

Proof: By assumption, the initial configuration never dies out, so there are live cells in generation k no matter how big k is. Thus by Claim 1, there are finite lifelines, never going direction u or v, of arbitrarily huge length.

Now I'll construct the infinite lifeline which never goes direction u or v. The construction is similar to the proof of Konig's Lemma, if you're familiar with it. For sake of brevity, say that cells A and B are "semineighbors" if they are neighbors *or* if A=B.

By assumption, only finitely many cells are alive in generation 1. Of the arbitrarily long finite lifelines avoiding u/v, each starts with one of these finitely many cells. This implies there is some cell c(1) alive in generation 1 such that there are arbitrarily long finite lifelines avoiding u/v which begin at c(1). Because, if there were no such c(1), then there would be a bound on the length of such lifelines starting at each initially live cell, and hence a bound on the lengths of *all* such lifelines, violating Claim 2.

Of the finite lifelines avoiding u/v which start with c(1) and having length>1, each one has as 2nd member a semineighbor of c(1) which is live in generation 2. It follows that some semineighbor c(2) of c(1) is the 2nd member of arbitrarily long finite lifelines avoiding u/v which start at c(1).

Similarly, there is a semineighbor c(3) of c(2) which is the 3rd member of arbitrarily long finite lifelines avoiding u/v which start with c(1),c(2).

And similarly forever. This defines an infinite lifeline c(1),c(2),... This infinite lifeline never goes direction u or v. Suppose it did-- say c(k+1) is direction u or v from c(k), for example. But we chose c(k+1) so that it's the (k+1)th member of (arbitrarily long) finite lifelines which start c(1),...,c(k) and avoid u/v. Since these arbitrarily long ones don't go in direction u or v, that violates c(k+1) being direction u or v from c(k). This completes the proof.

[calcyman]

By the way, Nathaniel has already proven the c/3 diagonal theorem. The proof is in Game of Life Cellular Automata (Springer, 2010).


Anyway, your technique is still impressive. The Two Forbidden Directions theorem can be proved more directly:

As you say, for n = 1, the proposition is clearly true.

A cell being alive (x,y,t) implies that the sum of the nine neighbours in the previous generation is at least 3. The converse is not true, but this is irrelevant.

Due to the Dirichlet pigeonhole principle, if each cell must have three predecessors, then when two predecessors (in the inverse forbidden directions) are removed, then at least one predecessor must remain.

So, the proposition for n = k implies the proposition for n = k+1.

I'm still trying to modify my argument to give a c/4 diagonal speed limit proof for Life.

It's a special case of the theorem that no configuration can propagate faster than c/2, by Manhattan distance.

[Sam Alexander]

The Two Forbidden Directions theorem can be proved more directly:

As you say, for n = 1, the proposition is clearly true.

A cell being alive (x,y,t) implies that the sum of the nine neighbours in the previous generation is at least 3. The converse is not true, but this is irrelevant.

Due to the Dirichlet pigeonhole principle, if each cell must have three predecessors, then when two predecessors (in the inverse forbidden directions) are removed, then at least one predecessor must remain.

So, the proposition for n = k implies the proposition for n = k+1.

That's a nice slick rewording of the claim that every live cell can be reached without going in 2 directions. It doesn't immediately yield the desired result (an *infinite* lifeline). If infinitely many cells are allowed to be live in generation 1, then you can cook up a configuration where there above all holds, and yet there are no infinite lifelines at all. For example, you could initially populate the board with a pattern which shrinks to nothing in 1 generation, separated from a pattern which shrinks to nothing in 2 generations, separated from a pattern which shrinks to nothing in 3 generations, and so on. Then the species never goes extinct, and the reasoning you just gave works, but there's no infinite lifeline.

But I guess the infinite lifeline isn't actually needed to get the c/3 limit, finite lifelines are enough. The "Claim 1" alone works. If a spaceship moves faster than c/3, there's a generation k such that the spaceship has moved exactly n units southeast where 3n>k. Take a cell x on the which is as southeast as possible in the spaceship in generation k. There's a (finite) lifeline starting in the original spaceship and ending at x in generation k, which never steps southeast or south. This lifeline moved *at least* n steps southeast in k generations, without ever going south or southeast. Absurd...

So that's really cool. Is the fact that we can actually get an *infinite* lifeline interesting in its own right?

So how does Nathaniel's proof of the c/3 diagonal speed limit go?

[Nathaniel]

So how does Nathaniel's proof of the c/3 diagonal speed limit go?

You can read a preprint on my website: here -- the result is Theorem 1 (which is only stated in the preprint for the rule 2x2, but applies to any "B3" rule. The proof in the preprint actually proves the diagonal speed limit result in two ways -- the first way is to prove it directly using a case analysis (if this cell which is diagonally offset by 1 is alive three generations from now, then this and this cell must be alive, and this cell must be dead, yada yada, contradiction). The second proof proves something slightly more general -- in a B3 rule, if a spaceship travels a cells vertically for every b cells horizontally, it cannot travel faster than c(max{a,b})/(2a+b) -- putting a = b = 1 gives the result we want.

Anywho, it's always great to have new ways to look at problems like this. Any chance of applying it to rules other than B3 rules? If I recall correctly, there is a 3c/4 diagonal spaceship known in a B0 rule, and I'm not aware of any non-trivial speed limits in rules like that.