I'm currently writing Section 7.1.4 of The Art of Computer Programming, which is about a fascinating combination of data structures and algorithms called binary decision diagrams (BDDs). A BDD is a super tool for manipulating Boolean functions, and it is especially good at functions that are somewhat symmetric. Since Conway's rule for Life-state transitions is an almost symmetric function of nine Boolean variables (namely the states of a cell and its eight neighbors), it can be represented by a very small BDD, at least locally. Therefore I decided to base a bunch of exercises for 7.1.4 on applications of BDDs to Conway's game. Before I started this work, Section 7.1.4 was already much longer than I had anticipated, because BDDs have turned out to be surprisingly rich. Furthermore, I still am far from finishing the section; consequently I can't devote more than a couple of pages (max) to Life, and I'll have to cut out much of the stuff that has been fascinating me during the past couple of weeks. I'm very glad that you expressed an interest in passing the info to other Lifenthusiasts, so that somebody else might be inspired to carry the BDD torch further into the world of "First Life". My results generally deal with the Facts of Life when restricted to rectangular $m\times n$ configurations, with $m$ and $n$ not too large, assuming all dead cells outside the rectangle. For example, one of my first results was to count the number of $10\times10$ configurations that vanish in one step. The answer is 4,400,789,480,783,375 and this number is now a[10] in OEIS sequence A134963. The total calculation needed only about 9 billion references to memory, in my laptop at home. Exactly one of these solutions has the maximum weight, namely *.**..**.* .********. ********** ********** .********. .********. ********** ********** .********. *.**..**.* and there's a similarly unique solution of weight 69 for $9\times9$. I suppose a pattern like this will be uniquely optimal on boards of size $m\times n$ when $m$ and $n$ aren't of the form $3k-1$. But on, say, a chessboard ($8\times8$), the most you can have before total wipeout is 46. Here is one of the eight solutions (although only three solutions are distinct under symmetries of the board): [well, I leave this as exercise 1; answers are at the end] Going the other way, how many Life configurations on a chessboard cause all 64 cells to become ALIVE at the next instant (and no cells outside the board until the time after that)? One obvious solution is .*..*..* **.**.** ........ .*..*..* **.**.** ........ .*..*..* **.**.** and there are many such solutions of weight 27. But there also are 54 solutions of weight 28. [Exercise 2 is to find one such.] I believe this problem of turning on the whole rectangle (and nothing outside) is solvable if and only if $m$ and $n$ both have the form $3k-1$. Here's a way to go from $8\times8$ Life to a $6\times6$ checkerboard: *....... ........ ....*.*. .*.*.*.. .**.*... ..*.*.*. ...*.**. .*.*.*.. .*..*... |-> ..*.*.*. .*...*.. .*.*.*.. ..**.*.. ..*.*.*. .......* ........ The lefthand configuration has weight 17 (the minimum). [Exercise 3 is to find an $8\times8$ predecessor with weight 22, which is the maximum.] In all of these problems, BDDs allow me to calculate not only the solutions of minimum and maximum weight; they let me minimize or maximize any linear combination $\sum_{i,j}x_{ij}$, over the set of all solutions. And it's also possible to generate uniformly random solutions efficiently. There are just five ways to go from a chessboard to ******** *......* *.****.* *.*..*.* *.*..*.* *.****.* *......* ******** in one step. [Exercise 4 is to find the one that is beautifully symmetric.] How many chessboard configurations exhibit Still Life? Exactly 4782725. The one with maximum weight 36 is unique, and it's quite obvious --- just a section of the agar culture made of $2\times2$ blocks. But there's essentially only one $8\times8$ still life of weight 35 [exercise 5]. The number of $n\times n$ still lifes can be enumerated without difficulty for small $n$ using BDDs, namely 1, 2, 12, 83, 417, 3928, 58697, 4782725, 285886827, 29305144137 for $n = 1$, 2, 3, ..., 10. I should mention that these counts include cases where the edges of the board are blank, and cases where smaller still lifes are placed together in ways that don't interfere; I'm merely counting the total number of fixed points of Conway's mapping, subject to the condition that everything is dead outside of the bounding square. (The 12 cases for $n=3$ are: 1 empty, 4 blocks, 1 tub, 4 boats, 2 ships.) Similarly, we can count the number of flip-flops, or 2-cycles, that fit in an $n\times n$ square, for $n$ up to 9: 0, 0, 1, 12, 43, 163, 8424, 582769, 40292074. Here I also looked at cases of maximum weight, in the chessboard case ($8\times8$). I was afraid that the results would be trivial combinations of known 2-cycles sharing space with a bunch of still-life junk, and indeed most of the max-weight solutions were just "beacons" plus stills. But there were two nice surprises, of things that may be new. First, there's a "Van de Graaff generator", below the table and block in *..*..** *..*..** ****..** ****..** ........ ........ **....** **....** *.*..*.* <-> *.*..*.* ; ..*..*.. ..****.. *.*..*.* *.*..*.* **....** **....** and second, there's a nifty "spark plug" (with blocks in the corner): ...**.** ...**.** ..*.*.** ..*.*.** .*...... .*.*.... *...*.** <-> *.***.** . **.***.* **.*...* ....*.*. ......*. **.*.*.. **.*.*.. **.**... **.**... This spark plug is the unique $8\times8$ flip-flop in which both states have 28 live cells. Incidentally, there's also a unique $7\times7$ in which both states have 26 cells alive: *.**.** *.**.** **.*.*. **.*.*. ......* ...*..* ***.*** <-> **...** *...... *..*... .*.*.** .*.*.** **.**.* **.**.* What shall we call it? While looking at these things I also stumbled across another cute flip-flop that might deserve a name if other people like it too: ...*... ...*... ..*.*.. ..*.*.. .*.*.*. .*.*.*. *..*..* *..*..* .**.**. .**.**. ..*.... <-> ....*.. ..**... ...**.. **.*.** **.*.** *..*..* *..*..* ..*.*.. ..*.*.. ...*... ...*... I looked also at the special 2-cycles that are called phoenixes, because every live cell dies on every step but then snaps back to life; thus the 2-cycle is x<->y with x&y=0. The smallest such case is well known to be an $8\times8$; it is best viewed with the notation that you used for the huge phoenix shown in Figure 150 of Martin Gardner's "Wheels, Life, and Other Mathematical Amusements" (page 243): .o o.o. . o oo .. .. oo o . .o.o o. I was able to carry out a complete search for all phoenix flip-flops up to size $15\times16$ before exceeding the current address space limit of 8 gigabytes in my quick-and-dirty BDD implementation. None of those smallish solutions presented any new ideas, unfortunately; the next case, $10\times12$, was simply an oval instead of a circle. Two of the $8\times8$s are able to fit on a $13\times15$ board, or on a $14\times14$, without interfering. The nicest small solution is probably the valentine, $10\times16$: .o .o o.o. o.o. . o.o. o oo .o .. .. oo o . .o. o.o o.o .o. .o.o o. It's a shame that I probably won't have space for this in TAOCP, but at least I'll be able to use it for Jill next February 14. I spent a week looking at "caged Life", namely at the full life histories of all $2^{mn}$ configurations of an $m\times n$ rectangle, until the time when they escape that rectangle (if they do). The biggest case I could handle satisfactorily was only $6\times6$, but already in this case the results were quite interesting. Consider first the configurations that escape from a $6\times6$ cage. It's not hard to see that exactly $806544\cdot2^{16}=52,857,667,584$ of the $2^{36}=68,719,476,736$ configs leave in one step. Then BDD techniques quickly characterize the predecessors of those guys; there are exactly $657527179\cdot2^4=10,520,434,864$ of them. And the predecessors of the predecessors can again be found in a similar way, leading to the following table: escape in 1 52857667584 escape in 2 10520434864 escape in 3 2105885159 escape in 4 763710262 escape in 5 331054880 escape in 6 201618308 escape in 7 126169394 escape in 8 86820176 escape in 9 63027572 escape in 10 41338572 escape in 11 30298840 escape in 12 17474640 escape in 13 9797472 escape in 14 5258660 escape in 15 3058696 escape in 16 1416132 escape in 17 523776 escape in 18 204192 escape in 19 176520 escape in 20 62456 escape in 21 13648 escape in 22 2776 escape in 23 2256 escape in 24 440 escape in 25 104 If a configuration lasts 26 generations, it never gets out. Here's one of the 104 patterns that procrastinates the longest before leaving: .....* **..*. ***.** .*.*.. ...... ..**.* On generation 25 it breaks out briefly at the left, but that part dies on generation 27. Meanwhile it also breaks out at the right on generation 26, and continues thereafter as a blinker. Its whole life history fits into a $6\times8$ cage. Another slow-starter, with the same eventual history, is *.**.. .....* **..*. ....*. *..*.. ..*..* I mentioned earlier that there are 3928 $6\times6$ still lifes. Looking at their predecessors, we find still after 0 3928 still after 1 4778052 still after 2 158873308 still after 3 479258492 still after 4 242032670 still after 5 175164301 still after 6 162710820 still after 7 98334624 still after 8 58165332 still after 9 36640164 still after 10 24811664 still after 11 13214004 still after 12 8557020 still after 13 4789012 still after 14 2820552 still after 15 2538816 still after 16 1095180 still after 17 728720 still after 18 348344 still after 19 218648 still after 20 141992 still after 21 64912 still after 22 32528 still after 23 10136 still after 24 4872 still after 25 744 still after 26 112 The 112 procrastinators put on quite a show. They all have essentially the same behavior after generation 14 (when they appear to be a block and a blinker, but the blinker is too close to the block to remain stable); eventually, on generation 26, they die. One such is ..*..* ***... .*...* .***.* ..*... **.*.. I also mentioned the existence of exactly 163 $6\times6$ flip-flops. They are the strange attractors of millions of other caged beasties: 2-cycle after 0 326 (163+163) 2-cycle after 1 1196514 (615433+581081) 2-cycle after 2 16930284 (8497432+8432852) 2-cycle after 3 24566566 (12385414+12181152) 2-cycle after 4 17305596 (8906474+8399122) 2-cycle after 5 8756720 (4488060+4268660) 2-cycle after 6 4783600 (2466314+2317286) 2-cycle after 7 2338996 (1207630+1131366) 2-cycle after 8 1261496 (648506+612990) 2-cycle after 9 539664 (278970+260694) 2-cycle after 10 338752 (176248+162504) 2-cycle after 11 70812 (35508+35304) 2-cycle after 12 25096 (7812+17284) 2-cycle after 13 2964 (960+3004) 2-cycle after 14 88 (0+88) (The counts in parentheses track patterns that lead to the lexicographically first or second element of a 2-cycle.) One of the 88 varieties that dawdle for 14 steps is .**.*. .**.** *..... *.*.** ; ...**. ...*.. it is essentially the only case having the minimum starting weight (15). OK, I've accounted for all but 1936 of the $2^{36}$ possibilities. It turns out that the remaining wise guys all end up in a 4-cycle that's called "mold", .**... .**... .**... .**... .**... *..*.. *..*.. *..*.. *..*.. *..*.. *.*..* -> *.*... -> *.*.*. -> *.*.*. -> *.*..* , .*.... .*.**. .*..*. .*.*** ..**.* ..**.* ..***. .....* ...*** ..**.* ....*. ...**. ..*.*. ...... ....*. probably because it has a fixed "loaf" in the upper left corner. The stats: 4-cycle after 0 16 (4+4+4+4) 4-cycle after 1 936 (32+436+32+436) 4-cycle after 2 976 (20+468+20+468) 4-cycle after 3 8 (0+4+0+4) The uniquely longest foreplay comes from the orangutan, .*.**. .*...* .**... **..** .*.*.. .*.*.* Since all $2^{36}$ cases have now been classified, we can conclude that moldy bread is the smallest Life cycle having length more than 2; no other extended cycle fits in a $6\times6$ cage. In this study of $6\times6$ caged Life, BDD methods are outstanding for characterizing the early escapees or early periodic elements; but they bog down when looking at, say, the cases that become still after a half-dozen steps. Those cases are pretty much like random bit patterns, which are incompressible. Anyway this whole exercise was a good way to shake down my BDD software. I doubt if it will turn out to be feasible to make a similarly complete study of $7\times7$ caged Life any time soon, with any methods whatever. That's a pity, because a lot of interesting phenomena don't begin to show up until the cage gets larger. It should be interesting to study $6\times6$ toroidal Life, in which case nobody escapes; then we have a complete mapping of $2^{36}$ states into $2^{36}$. Instead of BDD techniques for that, a forward-moving approach would seem better; the BDD method is good for going backward, but we might as well go strictly forward in time, since all states matter. (Notice that $2^{36}$ bits is eight large gigabytes.) In that space, gliders will have period 24; even longer periods are presumably possible. And of course a glider has period 140 in $5\times7$ toroidal Life... Most of my Life investigations were actually directed towards another goal, namely to find a $10\times10$ Garden of Eden configuration. For some reason I found it plausible that such a configuration must exist, and I thought I could use BDD methods to find it. This turned out to be a big time waster, and my efforts were fruitless; yet I shall report them here, just in case somebody sees how to succeed where I failed. First I simply computed the BDD with 49+25 variables, for all cases where a $7\times7$ starting configuration x_{11}x_{12}x_{13}x_{14}x_{15}x_{16}x_{17} x_{21}x_{22}x_{23}x_{24}x_{25}x_{26}x_{27} x_{31}x_{32}x_{33}x_{34}x_{35}x_{36}x_{37} x_{41}x_{42}x_{43}x_{44}x_{45}x_{46}x_{47} x_{51}x_{52}x_{53}x_{54}x_{55}x_{56}x_{57} x_{61}x_{62}x_{63}x_{64}x_{65}x_{66}x_{67} x_{71}x_{72}x_{73}x_{74}x_{75}x_{76}x_{77} leads in one step to 0 0 0 0 0 0 0 0 y_{22}y_{23}y_{24}y_{25}y_{26} 0 0 y_{32}y_{33}y_{34}y_{35}y_{36} 0 0 y_{42}y_{43}y_{44}y_{45}y_{46} 0 ; 0 y_{52}y_{53}y_{54}y_{55}y_{56} 0 0 y_{62}y_{63}y_{64}y_{65}y_{66} 0 0 0 0 0 0 0 0 this BDD has 867107 nodes. Then, by computing $\lnot \exists x_{11} \ldots \exists x_{49}$, I had a BDD in 25 variables $y_{ij}$ for all $5\times5$ cases that can't achieved with a border of zeros after one step of a $7\times7$. The latter BDD turns out to have 87958 nodes, and 138626 solutions; in other words, 138,626 $5\times5$s cannot be achieved in this way. Aha, I thought: Lots of really small Gardens of Eden! But of course I was foolish. One of my "pseudo-gardens" was, for example, the symmetric **.** *.*.* .***. *.*.* **.** and although it has no $7\times7$ predecessor with all-dead boundary, it does have 189,832 $7\times7$ predecessors that give the right 25 results in the interior. Most of those predecessors can be extended with further cells on their exterior, which serve to kill off the unwanted life outside the $5\times5$ goal. On the other hand, it's interesting to note that the pattern ..**.*. *.*...* ...*..* ..**..* , *..*... *..*.** .*....* which is one of those 189,832 predecessors, can NOT be extended in such a way: You can readily verify, although it's not trivial, that the lefthand column of this $7\times7$ can't be killed off by placing any further pattern on its periphery. Thus it's important to clarify a subtle distinction between a Garden of Eden and an "orphan". An orphan is a set of cell states that cannot arise after one step of Life; a Garden of Eden is an orphan that includes every cell of the plane. Furthermore, an $m\times n$ orphan is an orphan whose cells are defined only inside an $m\times n$ rectangle; and $m\times n$ Garden of Eden is a Garden of Eden for which all cells are dead outside of such a rectangle. It is known that there are no $5\times6$ orphans. But I do not believe anybody has proved even that there are no $5\times5$ Gardens of Eden. To do that, you'd need to establish the existence of predecessors that not only match the states inside any given $5\times5$, they also kill off everything outside of the square. I could probably write a program in a few hours that would take all of the 138,626 pseudo-gardens and find a valid predecessor for them; probably I wouldn't need to go further than $9\times9$ or $11\times11$. I haven't time to do that, but my example above shows that such a program must be run before anybody can claim that $5\times5$ Gardens of Eden do not exist. Such a claim is much stronger than claiming that $5\times5$ orphans do not exist. Indeed, I believe there is no known example of a rectangular Garden of Eden that is not an orphan; yet I believe it is likely that such Gardens of Eden do exist. I almost found such an example by combining two instances of Achim Flammenkamp's $10\times13$ rectangle that has exactly one $12\times15$ predecessor. Anyway, having failed to find a $5\times5$ Garden of Eden, I started to look for $10\times10$ orphans. Every such orphan consists of four $5\times5$ squares that are presumably somewhat difficult to precede. On the (unwarranted) assumption that my pseudo-gardens were unusually difficult specimens, I looked exhaustively at them, and found those with fewest $7\times7$ predecessors. The only such example that has less than 100,000 such predecessors is **.** .**** ****. , *.*** ***.* which has 95,970. But 538 of my pseudo-gardens had less than 200K. For each of those 538, and each of the eight ways to rotate and/or flip them, I looked at the sets of 24 bits that occur at the top-and-right boundary of their predecessors. Namely, if $\alpha$ is a $7\times 7$ predecessor, let $x$ be the 14 bits in the two top rows of $\alpha$, and let $y^T$ be the 14 bits in the two right columns. (Then $x$ and $y$ have four bits in common.) The set of all pairs $(x,y)$, taken over all predecessors $\alpha$, determines whether we'll be able to use $\alpha$ in the lower left of any $12\times12$ square that precedes a $10\times10$ with the given $5\times5$ in its lower left quarter. Each of my 538 pseudo-gardens had at most 200K predecessors, so it had at most 200K pairs $(x,y)$; but in fact, the truth was much better than this worst-case estimate. The best case was ***** *.*.* ..*** , **..* **.** for which only 24,919 border-pairs $(x,y)$ arise. The 538 nonisomorphic pseudo-gardens and their rotation/flips led to 4039 different ways to orient the squares; I choose the 100 that had the fewest pairs $(x,y)$. Then I composed each of those 100 with each of the others. In other words, when $\alpha$ has border pairs $(x,y)\in S(\alpha)$ and $\beta$ has border pairs $(y,z)\in S(\beta)$, the border pairs of the composition $\alpha\circ\beta$ are those $(x,z)$ such that $(x,y)\in S(\alpha)$ and $(y,z)\in S(\beta)$, for some $y$. These composite border pairs $(x,z)$ govern the middle rows of any any $12\times12$ that precedes a $10\times10$ with given squares $\alpha$ in the lower left quarter and $\beta$ (rotated 90 degrees) in the lower right quarter. The choices of $\alpha$ and $\beta$ that had the fewest such pairs $(x,z)$ turned out to be **.***.*** ***.***.** **..****.* *.****..** ..***..*** and ***..***.. *.*.*.*.*. .*.*.*.*.* ******..** **..****** with just 26,173 pairs each. In other words, only about 26K of the $2^{24}$ possible top rows of a $7\times12$ configuration can precede each of these $5\times10$s. The final step is to combine two of these hard-to-precede $5\times10$s. We'll have a $10\times10$ orphan if and only if their $(x,z)$ pairs are totally disjoint. The odds against this are huge, even if there are only 26K pairs; but I had millions of cases to try, so it wasn't inconceivable that I could get lucky. I didn't. The best I found were two combinations in which there were only 37 possibilities for the middle two rows of a preceding $12\times12$. Here is one of the two winners: .*.***.**. *..*.*..** .**.*****. *.**.*.*.* ***.****** ***.***..* *.***.*.*. ***..***.. .*.*.*.*** **..****.* Unfortunately, 37 is greater than 0, so I have no orphan. If I had time to pursue this, I suppose my next step would be to try for an $11\times11$ orphan. (Achim has, of course, discovered a $12\times11$, for which I now have great admiration.) From my experiences above, I would be willing to bet that if an $11\times11$ orphan exists, there also exists one in which the central nine cells are *** *.* *** (because the hard cases in my experiments all had high density). I could surround those nine cells with four $4\times7$ tiles. And I could search heuristically for tiles that have a small number of possibilities at the top and right boundaries of their predecessors. Then, I hope, I could find tiles $\alpha$, $\beta$, $\gamma$, $\delta$, for which there's no four-cycle $(w,x)\to(x,y)\to(y,z)\to(z,v)$ with $(w,x)\in S(\alpha)$, $(x,y)\in S(\beta)$, $(y,z)\in S(\gamma)$, and $(z,w)\in S(\delta)$. That would define an orphan. End of report. I hope my remarks have been scrutable. ------------ answer 1: answer 2 (too easy): answer 3: answer 4: answer 5: *...**.* **..*..* ......*. **.**.** .**.**.* ..*****. **.**.** *.*.*..* *..**..* *.*.*.** .******* ........ *...*... ..*..*.. **..*... .******* .*..*..* ..**.**. **....** ....*.** *******. **.**.** *...*... **....** *****.** ******.* ........ *.*.*.*. ..*..*.. *....... .****... .*..*..* ........ *..**..* .*.**.** *.**.*.* **.**.** *.**.**. **.**.** **.**.** One other afterthought: I should have realized that it's pretty easy to analyze 6x6 toroidal Life, because there are 36x8 automorphisms. Thus the whole directed graph can be represented comfortably in 4 gigabytes.