This is a cool subcommunity! Had no idea there were still open problems that people were working on. Surprised to see human intuition is still around – would have expected a solution through pure brute force.
The state space is much too large for generic brute-forcing. The number of possible patterns in a 16 x 16 grid is already roughly the number of atoms in the universe, or 10^31 years in Planck time units.
In that respect, it reminds me a bit of the busy beaver problem.
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?
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 not 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.
> 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 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.
You can make a Turing machine that contains self-destruct circuitry which destroys all moving parts upon halting. The resulting pattern will be a (pseudo) still life.
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.
If there haven't been any proposals for a friendly name for the 23 bit holdout it looks like a pair of glasses to me. So perhaps "spectacles" would be a nice one, similar to the spectre of recent aperiodic monotile fame.
Ever since programming GOL in assembly on Z80 i dreamt of this.
Game for two persons.
The game runs, you can go back in time and modify by introducing gliders.
Only problem is, how to turn it into a real game, what is the object.
Maybe split the world in two and try building a stable configuration. The opponenent can launch the glider towards your turf, or something like that.
I just found out that there's a 1D cellular automaton called Rule 54 that is conjectured to be Turing complete, but for which there isn't yet a proof.
I think Gemini (an LLM) and me are in agreement that the proof will likely be found by a neuro-symbolic AI. As evidence for this, see AlphaEvolve and the agents which received IMO Gold.
This is a cool subcommunity! Had no idea there were still open problems that people were working on. Surprised to see human intuition is still around – would have expected a solution through pure brute force.
The state space is much too large for generic brute-forcing. The number of possible patterns in a 16 x 16 grid is already roughly the number of atoms in the universe, or 10^31 years in Planck time units.
In that respect, it reminds me a bit of the busy beaver problem.
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?
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 not 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.
[0] https://conwaylife.com/forums/viewtopic.php?f=2&t=6830&p=201...
> 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 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.
You can make a Turing machine that contains self-destruct circuitry which destroys all moving parts upon halting. The resulting pattern will be a (pseudo) still life.
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.
Aah, but construction in GoL is not limited to gliders...still.
If there haven't been any proposals for a friendly name for the 23 bit holdout it looks like a pair of glasses to me. So perhaps "spectacles" would be a nice one, similar to the spectre of recent aperiodic monotile fame.
> copy to clipboard
no, thank you. I already have hobbies to consume my life.
It's annoying here that you can't run CGoL in reverse, like you can with the laws of physics.
Someone should invent a GoL (that is still interesting) with that property.
You'll be pleased to find out about Critters:
https://en.wikipedia.org/wiki/Critters_(cellular_automaton)
Thanks, very interesting!
Ever since programming GOL in assembly on Z80 i dreamt of this.
Game for two persons. The game runs, you can go back in time and modify by introducing gliders. Only problem is, how to turn it into a real game, what is the object. Maybe split the world in two and try building a stable configuration. The opponenent can launch the glider towards your turf, or something like that.
I just found out that there's a 1D cellular automaton called Rule 54 that is conjectured to be Turing complete, but for which there isn't yet a proof.
I think Gemini (an LLM) and me are in agreement that the proof will likely be found by a neuro-symbolic AI. As evidence for this, see AlphaEvolve and the agents which received IMO Gold.