All 23-Bit Still Lifes Are Glider Constructible

https://mvr.github.io/posts/xs23.html

127•HeliumHydride•3w ago

Comments

linolevan•3w ago

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•3w 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•3w 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=201...

isoprophlex•3w 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•3w 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•3w ago

Aah, but construction in GoL is not limited to gliders...still.

vintermann•3w 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•3w 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•3w 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.

amelius•3w ago

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.

GaryHak•3w ago

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.

AlotOfReading•2w ago

You'll be pleased to find out about Critters:

https://en.wikipedia.org/wiki/Critters_(cellular_automaton)

amelius•2w ago

Thanks, very interesting!

ogogmad•3w ago

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.

OisinMoran•3w ago

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.

avadodin•2w ago

> copy to clipboard

no, thank you. I already have hobbies to consume my life.

Show HN: MCP-baepsae – MCP server for iOS Simulator automation

Make Trust Irrelevant: A Gamer's Take on Agentic AI Safety

Show HN: Sem – Semantic diffs and patches for Git

Hello world does not compile

Show HN: ZigZag – A Bubble Tea-Inspired TUI Framework for Zig

Metaphor+Metonymy: "To love that well which thou must leave ere long"(Sonnet73)

Show HN: Django N+1 Queries Checker

Emacs-tramp-RPC: High-performance TRAMP back end using JSON-RPC instead of shell

Protocol Validation with Affine MPST in Rust

Female Asian Elephant Calf Born at the Smithsonian National Zoo

Show HN: Zest – A hands-on simulator for Staff+ system design scenarios

Show HN: DeSync – Decentralized Economic Realm with Blockchain-Based Governance

Automatic Programming Returns

Why Are There Still So Many Jobs? The History and Future of Workplace Automation [pdf]

The Search Engine Map

Show HN: Souls.directory – SOUL.md templates for AI agent personalities

Real-Time ETL for Enterprise-Grade Data Integration

Economics Puzzle Leads to a New Understanding of a Fundamental Law of Physics

Switzerland's Extraordinary Medieval Library

A new comet was just discovered. Will it be visible in broad daylight?

ESR: Comes the news that Anthropic has vibecoded a C compiler

Frisco residents divided over H-1B visas, 'Indian takeover' at council meeting

If CNN Covered Star Wars

Show HN: I built the first tool to configure VPSs without commands

AI agents from 4 labs predicting the Super Bowl via prediction market

EU bans infinite scroll and autoplay in TikTok case

Benchmarking how well LLMs can play FizzBuzz

Why I Joined OpenAI

Octave GTM MCP Server

Show HN: Portview what's on your ports (diagnostic-first, single binary, Linux)