ConwayLife.com

Though it was not discussed in this thread, we (me & Ilkka Törmä) learned on Discord that people are also interested in whether there exists a finite configuration which admits a Game of Life -preimage, but does not admit a finite one. The answer is "yes", we proved this quite soon after our ...

In a similar vein, it is PSPACE-hard whether a given pattern appears in the limit set, just run a Turing machine inside the hole to determine whether it blows up.

Of course calcyman is correct, in my previous message I meant that the previous proof does not work at all because of stabilization. The observation of calcyman is that, for the same reason, another (even intuitively simpler) proof gives even smaller higher orphans, though unlike in the previous ...

I suppose this result must imply a tighter upper bound on the necessary size of a patch of agar with a central disturbance, that is an easily provable Grand^N Orphan. It seems as if the size of the agar patch should only have to expand at lightspeed, on average, to force the no-Nth-grandparent ...

Let me add that dynamically this has the consequence that Game of Life restricted to its limit set (the set of configurations that can be seen after arbitrarily many steps) is not "chain-transitive". In particular it is not topologically transitive or topologically mixing. This is something we have ...

My reading of mtve’s statement was always something like “at least one additional level almost certainly exists” — presumably because the SAT~solver methods mtve was using didn’t seem to be running into any insurmountable walls, just getting a little more CPU-intensive for each level.

So I didn’t ...

From https://www.conwaylife.com/wiki/Grandfather_problem :

Next levels
"A father and grandfather, but no great-grandfather" pattern[7], and a "father, grandfather and great-grandfather, but no great-great-grandfather" pattern[8], have also been constructed by the same method.

No further levels ...

It's interesting to have a method of generating grand^N-orphans that doesn't have to rely on checking exponentially increasing number of predecessors as the value of N increases. Just "flip one cell in the center" of a large enough agar patch instantly guarantees a Garden of Eden, none of whose ...