In article <9512040556.AA19536@servidor.dgsca.unam.mx> 
mcintosh@servidor.dgsca.unam.MX (McIntosh Harold V.-UAP) writes:

As they apply to Life, think of the following game of dominoes: Split 
the 3x3 Life neighborhood into two overlapping 3x2 pieces: 

		a b c     a b     b c
		d e f  =  d e  +  e f
		g h i     g h     h i.

The pieces are the dominoes; the left domino has spots (adg) and (beh).  
Suppose we have an ample supply of all the 64 distinct dominoes, and that 
we play the traditional game of matching them. As such, it will be sort of 
trivial because somewhere there will be a domino to match whichever one we 
pick, either on the left or on the right. 

To get the variant which figures out Life evolution, we have to discard some 
of them and try to build up chains with the remainder. To find Life still 
lifes, for example, only the neighborhoods whose central cell stays constant 
should be used, and split up to get the domino set. Actually only about a 
third of the neighborhoods work, which is a lot of dominoes, but it still 
limits the kinds of chains that can be built up. 

The problem posed, to find configurations which vanish utterly on the second 
generation, mean picking out those of the 256 neighborhoods which have this 
property, which is actually a good fraction of the 256 (I'm too lazy to add 
it up here at the keyboard). 

Rather than cut out little pieces of cardboard and lay them out on the table, 
we could make a graph showing which dominoes can be joined together. Normally 
a game of dominoes isn't played this way, but then you don't play with 30 or 
40 different dominoes, either. That graph is the de Bruijn diagram (or rather, 
since the dimension is greater than 1, it is the first stage de Bruijn diagram. 

The first thing to be done with the diagram is to notice that there are loops 
and there are isolated vertices. A vertex with no incoming links can be dropped 
because there is no way to extend the pattern to the left. Likewise, a node 
without any outgoing link blocks chains running to the right. Recursively, 
all those nodes which don't lie on loops can be dropped. The result may be 
connected or disconnected; if disconnected, there are families of chains which 
don't have any sequences in common. 

Some advantage of symmetry and the fact that there are two dimensions will 
simplify the diagram; rotate or reflect the neighborhood, and note that there 
is no point of including neighborhoods which will eventually block upward or 
downward extensions, although this shows up full force only later, in the 
second stage diagram. 

At this point we only have a map which will allow the formation of linear 
strips, so it is work up to two dimensions by creating all possible strips 
and doing it all over again with very oblong rectangular dominoes. In full 
generality this simply can't be done (and not for the huge number of tiles) 
because that would mean solving Post's Correspondence Problem, which is just 
as insoluble (strictly, undecidable) as Turing's Halting Problem. 

But periodic solutions CAN be found, and freestanding solutions CAN be found 
(which is what the posed problem really wants, anyway). So one chooses a 
length, and looks at all loops in the diagram running through the (zero, zero) 
node (that is to get freestanding solutions) of that length and constructs new 
dominoes --- the second stage tiles. Their joining is mapped by the second 
stage de Bruijn diagram, and that is the one which holds the answer. In fact, 
it will produce all solutions of fixed width but arbitrary lateral extent. 

How hard is all this in practice: well, it results in huge diagrams; the first 
stage diagrams grow exponentially with the length of the strip, which means 
that for Life, six, seven, eight is about all that can be worked out on PC 
level machines. A couple of years ago we got a little further on a Cray, 
although the real interest was in period 2 structures. Period 3 is beyond any 
foreseeable computer power, yet 4 would be interesting, to see gliders for the 
first time. 

If all this sounds oppressive, remember that it is a reflection of what is 
really there. On the other hand, the only way people have gotten very extensive 
results up until now is to write special purpose programs that examine small 
fixed areas exhaustively, and those have succeeded pretty well. 

The process works out much better for finding evolution to solidly filled 
areas: there are fewer of them in actuality, and there are fewer tiles to be 
examined to find them. At least for the Life rules; the process applies to 
any rule of evolution. 

Anyone who still wants to follow this up, we have a couple of booklets which 
can be had for the asking; send full address with country and zip code. In 
fact this might make nice stuffing for a web page, if we get up enough energy 
to create one.