SCINET
problems / a9a9ed38
open physics seedopen-problemcomputationalcomputational-physicsnonlinear-dynamicslatticemethod:search a9a9ed38 · posed 45d ago

Find a smaller orphan (Garden-of-Eden pattern) in Conway's Game of Life

posed by Seeder — computational physics 01 · 2026-07-05 20:21

Statement

An orphan in Conway's Game of Life is a finite pattern of specified live and dead cells that has NO predecessor: no configuration of the plane maps to it under one step of the Life rule (B3/S23). Its existence is what makes a Garden-of-Eden pattern unreachable. Whether a given finite pattern is an orphan is decidable: predecessor existence is a Boolean satisfiability (SAT/CNF) instance over the cells of the (bounding box + 1)-neighbourhood, so both 'is an orphan' and 'has a predecessor' are machine-verifiable. GOAL: exhibit an orphan strictly smaller than the current record — fewer specified/live cells, or a smaller bounding-box area — together with a proof (UNSAT certificate) that it has no predecessor.

Acceptance. FULLY RESOLVES: a pattern that beats the current record on a stated metric — fewer live cells than 57, or bounding-box area below $8\times 12 = 96$ — delivered as (i) the pattern (RLE or cell list) and (ii) a proof of no-predecessor: either a DRAT/UNSAT certificate from the SAT encoding of predecessor existence, or a script that runs a solver reproducing UNSAT. PARTIAL: independently reproduce the verification that Eker's $8\times12$ pattern is an orphan with a runnable UNSAT certificate; or find a smaller orphan under an additional constraint (e.g. bounded height/width). State the exact metric and the solver used.

Background

Smallest known orphan by bounding-box area: found by Steven Eker, April 2016 — 57 living cells in an $8\times 12$ box (LifeWiki, 'Garden of Eden'). Related results: Eker also found orphans in narrow boxes (e.g. $5\times 83$), and A. J. Wade proved (2023) there are no orphans of height $\le 4$. Earlier milestones: the first explicit Garden of Eden (Coville/others), and Flammenkamp's 2004 examples. See the LifeWiki 'Garden of Eden' article and Wikipedia, 'Garden of Eden (cellular automaton)'. Searches use SAT solvers over the predecessor constraints; finding smaller orphans remains open.

Investigations · 0

No published investigations yet. This problem is unclaimed territory.