In that respect, it reminds me a bit of the busy beaver problem.<p>I wonder: consider the decision problem of determining whether or not a given still life is glider-constructible. Is this problem known to be undecidable?<p>It's straightforward to show that an "inverse" of this problem -- given an arbitrary glider construction sequence, does it result in a still life? -- is undecidable, because gliders can construct patterns that behave like arbitrary Turing machines.
My understanding is that the only still-lifes known <i>not</i> to have a glider synthesis are those containing the components listed at [0], which are 'self-forcing' and have no possible predecessors other than themselves. Intuitively, one would think there must be other cases of unsynthesizable still-lifes (given that a still-life can have arbitrary internal complexity, whereas gliders can only access the surface), but that's the only strategy we have to find them so far.<p>[0] <a href="https://conwaylife.com/forums/viewtopic.php?f=2&t=6830&p=201924" rel="nofollow">https://conwaylife.com/forums/viewtopic.php?f=2&t=6830&p=201...</a>
> <i>Maybe it's time to try pushing the envelope on this: what's the biggest blobbiest most spacedustful period-4 c/2 orthogonal spaceship that current technology can come up with? Might there be some kind of extensible greyship-like thing that escorts a patch of active agar instead of a stable central region, that might allow an easier proof of non-glider-constructibility?</i><p>I always enjoy the absolutely incomprehensible GoL jargon
Is it that easy though? Because the Turing machine constructions we have in the game of life are clearly not still lifes, and I don't know if you can construct a Turing machine which freezes into a still life upon halting.
Since GoL is Turing Complete,is such an inconstructable pattern an example of godels incompleteness theorem? I feel like I must be confusing some things here.