On the other hand, if you only look at a finite subset of the infinite field, then you find that knowing the exact contents of a n by n box in one generation only tells you the exact contents of an (n-2) by (n-2) box in the next generation. You have 2^(n^2) patterns mapping to 2^((n-2)^2) patterns, the former is 16^(n-1) times as large as the latter. This makes the existence of convergent patterns trivial, and the existence of Garden of Eden patterns quite surprising.
I agree with the GoE part, but does this really single-handedly imply convergent patterns? Two n×n states that produce the same (n-2)×(n-2) successor don't necessarily have the same effects on their boundaries. Contrapositively, the part about only determining a (n-k)×(n-k) successor applies to any cellular automata that use a (k+1)×(k+1) neighborhood, even reversible ones.
This is correct.
Thanks for pointing that out.
Many experts suspect that there is no polynomial-time solution to the so-called NP-complete problems, though no-one has yet been able to rigorously prove this and there remains the possibility that a polynomial-time algorithm will one day emerge. However unlikely this is, today I would like to invite LW to play a game I played with with some colleagues called what-would-you-do-with-a-polynomial-time-solution-to-3SAT? 3SAT is, of course, one of the most famous of the NP-complete problems and a solution to 3SAT would also constitute a solution to *all* the problems in NP. This includes lots of fun planning problems (e.g. travelling salesman) as well as the problem of performing exact inference in (general) Bayesian networks. What's the most fun you could have?