All 23-Bit Still Lifes Are Glider Constructible

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 2 hours ago | parent [-]

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 2 hours ago | parent | next [-]

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...

▲

CraftingLinks an hour ago | parent | prev [-]

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 an hour ago \| parent [-]
		Aah, but construction in GoL is not limited to gliders...still.