5 ms·
Very nice! You might be interested in a simple proof I found of why c/2 and c/3 are speed limits for orthogonal and diagonal spaceships respectively. Definiti
by xamuel 11y ago
Very nice!
You might be interested in a simple proof I found of why c/2 and c/3 are speed limits for orthogonal and diagonal spaceships respectively.
Definition: In a gameplay of life, an "infinite lifeline" is a sequence of pairs (c_i,n_i) such that each c_i is alive in generation n_i and either c_(i+1)=c_i or c_(i+1) is adjacent to c_i.
Lemma ("Two Forbidden Directions"): Let x,y be any two 'forbidden' directions from among N,S,E,W,NE,NW,SE,SW. In any gameplay of life that starts finite and doesn't die out, there is an infinite lifeline that never goes in either direction x or y.
The lemma's proof uses biology. Say that (c,n) is a "father" of (c',n+1) if c' is the cell adjacent to c in direction x or y. Otherwise, (c,d) is a "mother" of (c',n+1). By the rules of the game of life it's easy to show every living (c,n+1) has at least one living father and at least one living mother. It follows (modulo some more details) that since the gameplay doesn't die out, there must be an infinite lifeline where each cell is a mother of the next, i.e., an infinite lifeline that never goes direction x or y.
Proof of c/2 orthogonal speed limit: If a spaceship went faster than c/2, say, northward, by the lemma, it would have an infinite lifeline that never goes N or NE. The only way it could ever go northward would be to go NW. Every NW step would have to be balanced out by an eastward step (of which NE is forbidden) or the spaceship would drift west. So every northward step requires a non-northward step, QED.
Proof of c/3 speed limit for diagonal: A diagonal spaceship faster than c/3, say, northeastward, would have an infinite lifeline that never goes N or NE. The only way for it to go northward would be to go NW. Each NW step would need at least two eastward steps in order for the ship to go eastward, QED.
- jessaustin 11y agoI'm no life expert, but this proof doesn't work for me. Just because there exists some configuration that doesn't generate lifelines in your chosen directions, doesn't mean that any particular configuration doesn't generate lifelines in those directions.
- xamuel 11y agoYou're mixing up where the negation goes. The lemma says that in any configuration which starts finite and never dies out, there DOES exist at least one lifeline which DOESN'T go in a forbidden direction. (There are almost certainly lots of other lifelines which do go in forbidden directions, that's fine.) An example of a lifeline in a southeastward spaceship that never goes S or SE: http://www.xamuel.com/images/lifeline.gif http://www.xamuel.com/images/lifeline.gif The proof I outlined above was published in the Elect. J. of Combinatorics (last section): http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p31 http://www.combinatorics.org/ojs/index.php/eljc/article/view...
- jessaustin 11y agoAck, sorry. For some reason my mind wasn't wrapping around the fact that you can choose your configuration before choosing your forbidden directions.
- DerekL 11y ago>By the rules of the game of life it's easy to show every living (c,n+1) has at least one living father and at least one living mother. This statement seems incorrect. It's true that every living cell has a living mother, but there's no requirement of a living father.
- xamuel 11y agoWhen I say (c,n+1) has a "living" father what I mean is a father (b,n) such that b is alive in generation n. Your father might have died before you were born but he didn't die before he himself was born. I handwaved that bit anyway for expediency, if you're interested in the full details see: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p31 http://www.combinatorics.org/ojs/index.php/eljc/article/view...
- DerekL 11y agoOkay, I read that and now I get it. Each live cell has at least three ancestors. Two or fewer of these ancestors come from a forbidden direction, so at least one comes from an allowed direction. Among all of the ancestors from an allowed direction, arbitrarily choose one to be the “mother”. All of the other ancestors are called “fathers”. There's no requirement that a father has to come from a forbidden direction.
- xamuel 11y agoAhh you're right, I messed up when I typed the proof in my comment. Your explanation of it is A++
- invisibowl 11y agoc/3 diagonal is actually impossible as well - the limit is c/4, proved by Conway himself in Life's early years. His proof can be found here: http://www.njohnston.ca/2009/10/spaceship-speed-limits-in-life-like-cellular-automata/ http://www.njohnston.ca/2009/10/spaceship-speed-limits-in-li...