4 ms·

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 ha

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.

teraflop 9mo ago
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.
- LegionMammal978 9mo ago
  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=201924 https://conwaylife.com/forums/viewtopic.php?f=2&t=6830&p=201...
  - isoprophlex 9mo ago
    > 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
- CraftingLinks 9mo ago
  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.
  - CraftingLinks 9mo ago
    Aah, but construction in GoL is not limited to gliders...still.
- vintermann 9mo ago
  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.
  - HeliumHydride 9mo ago
    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.
layer8 9mo ago
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.

teraflop 9mo ago

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.

LegionMammal978 9mo ago
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=201924 https://conwaylife.com/forums/viewtopic.php?f=2&t=6830&p=201...
- isoprophlex 9mo ago
  > 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
CraftingLinks 9mo ago
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.
- CraftingLinks 9mo ago
  Aah, but construction in GoL is not limited to gliders...still.
vintermann 9mo ago
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.
- HeliumHydride 9mo ago
  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.

layer8 9mo ago

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.