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•1h 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•51m 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.
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•9m ago
Aah, but construction in GoL is not limited to gliders...still.
linolevan•1h ago
teraflop•1h ago
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•51m ago
[0] https://conwaylife.com/forums/viewtopic.php?f=2&t=6830&p=201...
CraftingLinks•11m ago
CraftingLinks•9m ago