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:
I think I can explain that using this result I got called the Two Forbidden Directions result.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.
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