[#P2830] Strong block universality of Conway's Game of Life
Problem. Let \(g:\{0,1\}^{\mathbb Z^2}\to\{0,1\}^{\mathbb Z^2}\) be Conway's Game of Life map. Does \(g\) strongly simulate every block map \(\phi:Y\to D^{\mathbb Z^2}\) whose domain \(Y\) is a two-dimensional subshift of finite type? Explicitly, for every such \(\phi\), do there exist positive integers \(m,n\), an injective macrotile substitution \(\tau:D\to\{0,1\}^{[m]\times[n]}\), and a bijective partial block map \(h\) from the Life configurations \(x\) satisfying \(g(x)\in\tau(D^{\mathbb Z^2})\) onto \(Y\), such that \(g(x)=\tau(\phi(h(x)))\) for every such \(x\)?
1Problem setup
Remark 1. The Life update makes a dead cell live when exactly three of its eight neighbors are live, and keeps a live cell alive when two or three of its eight neighbors are live.
Definition 1. A two-dimensional subshift of finite type is a shift-invariant set of configurations specified by finitely many forbidden finite patterns.
Definition 2. A block map is a shift-commuting map whose output at each site depends on a fixed finite neighborhood.
Remark 2. The substitution \(\tau\) replaces each symbol by an \(m\)-by-\(n\) rectangular pattern. Bijectivity of \(h\) requires each simulated configuration to correspond to exactly one allowed Life preimage.
2What counts as a solution
- For every finite-type domain \(Y\) and block map \(\phi:Y\to D^{\mathbb Z^2}\), construct \(m,n,\tau,h\) satisfying the displayed bijective simulation, or exhibit one explicit \(Y,\phi\) and prove that no such data can exist.
1Status
Current status (Semiweak universality is proved and strong universality remains open). Salo and Törmä prove that Life is semiweakly universal and leave strong block universality open. This packet derives a periodic-fiber count test and excludes macrocell area at most 11 for one required target, the constant map from the binary full shift.[1]
1Records
Notes and companion material
The existing semiweak simulation already transports computational hardness into one-step Life preimages. Strong simulation would remove extraneous preimages, so local gadget catalogs, uniqueness certificates, and obstructions in preimage fibers are reusable even before the universal statement is settled.
Original intake status. UNKNOWN as of 2026-07-27. The 2025 primary paper proves that Life is semiweakly universal as a block map and explicitly leaves strong universality open in Question 2.
- 2026-07-27 status search checked the 2025 primary paper, its block-map simulation definitions, and later searches for strong universality of Life; no proof or obstruction settling Question 2 was found.
- The strongest neighboring result is effective semiweak universality: every target configuration has a selected Life preimage, but further Life preimages may remain outside the selected copy.
- A positive artifact must control every preimage of each simulated macrotile configuration. A negative artifact should isolate a block-map invariant that the Life preimage fibers cannot match bijectively.
Recorded example 1. The circuit-system block map used by Salo and Törmä is effectively strongly universal, while their Life construction semiweakly simulates it. The unresolved step is making the interpretation of all allowed Life preimages bijective.
How the 8 records connect
ProblemStrong block universality of Conway's Game of Life
- Claim 1Semiweak universality is proved and strong universality remains openin this packetSupported
- Route 1Primary-source audit separates three meanings of strong universalitysupportsSupported
- Computation 1The binary full-shift target needs macrotile area greater than 11supportsReproduced
- Claim 2Strong universality forces exact periodic-point counts in a periodic Life fibersupportsReported
- Proposition 1The 6 by 3 Köynnös agar passes the singleton testinformsSupported
- Artifact 1Exact finite-torus fiber and certificate replaychecksReproduced
- Artifact 2Independent C++ area-11 cross-checktestsReproduced
- Route 2Extend the binary full-shift periodic-count screenusesReported
2See also
How to cite
TheoremDB contributors, “Strong block universality of Conway's Game of Life,” TheoremDB research memory, snapshot of July 28, 2026. https://theoremdb.org/statements/life-strong-block-universalityThis page as plain text: life-strong-block-universality.md
This problem includes 8 records joined by 9 typed links, current as of July 28, 2026.
1References
- Ville Salo and Ilkka Törmä, Structure and computability of preimages in the Game of Life, Theoretical Computer Science 1042 (2025), 115237, Definitions 4-5, Theorem 4, and Question 2. Definitions 4–5, Theorem 4, Section 9, and Question 2. ↗scholarly publication · reference source · version of record · checked 2026-08-01Source use: citation only.Defines strong block-map simulation, proves effective semiweak universality for Life, and states the exact strong-universality question as open.Also cited at Question 2 and Definitions 4-5 state the strong-block-universality problem; this CC0 self-contained record was prepared on 2026-07-27.Also cited at Ville Salo and Ilkka Törmä, Structure and computability of preimages in the Game of Life, Theoretical Computer Science 1042 (2025), 115237, Definitions 4-5, Theorem 4, and Question 2.Also cited at Definitions 4-5, Theorem 4, and Question 2.Also cited at Definition 5 and Theorem 7.Also cited at Definitions 4-5, Theorem 4, Section 9, and Question 2.Also cited at Salo and Törmä (2025), Definitions 4-5, Theorem 4, Section 9, and Question 2. Exact-phrase and citation searches completed 2026-07-28.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.For Strong block universality of Conway's Game of Life: Theorem 7 applies semiweak universality to a constant map and obtains a split factor of a periodic Life fiber. Replacing the section by the bijection required in Definition 5 gives the conjugacy and fixed-point-count test.Defines the target notion, proves semiweak universality, and states the open strong-universality question.Theorem 7 applies semiweak universality to a constant map and obtains a split factor of a periodic Life fiber. Replacing the section by the bijection required in Definition 5 gives the conjugacy and fixed-point-count test.Primary source for the exact target and its current published status.
- Ville Salo and Ilkka Törmä, What Can Oracles Teach Us About the Ultimate Fate of Life?, ICALP 2022, Section 3.1, Köynnös, especially Lemma KoynnosForcing and the following global forcing argument. Section 3.1, Köynnös, especially Lemma KoynnosForcing. ↗proceedings article · reference source · version of record · checked 2026-08-01Source use: citation only.Supplies the closest unique-predecessor construction, a 6 by 3 periodic Life fixed point that strongly simulates the singleton target.Also cited at Ville Salo and Ilkka Törmä, What Can Oracles Teach Us About the Ultimate Fate of Life?, ICALP 2022, Section 3.1, Köynnös, especially Lemma KoynnosForcing and the following global forcing argument.Also cited at Section 3.1, Köynnös, especially Lemma KoynnosForcing and the following global forcing argument.For Strong block universality of Conway's Game of Life: Supplies the explicit periodic fixed point and the finite certificate proving that its only global predecessor is itself.Supplies the explicit periodic fixed point and the finite certificate proving that its only global predecessor is itself.Closest unique-global-predecessor result and source of the singleton strong-simulation example.
- Martín Ríos-Wilson and Guillaume Theyssier, “Intrinsic universality in automata networks II: Glueing and gadgets”. Theoretical Computer Science 1016 (2024), 114779. DOI 10.1016/j.tcs.2024.114779. Abstract and the finite automata-network simulation definitions. ↗scholarly publication · reference source · version of record · checked 2026-08-01Source use: citation only.Resolves a terminology collision: its strong-universality theorem concerns finite automata networks, not one-step block-map fibers of infinite Life.For Strong block universality of Conway's Game of Life: Terminology collision: its strong universality theorem concerns a family of finite automata networks, not one-step block-map fibers of the infinite Life cellular automaton.Terminology collision: its strong universality theorem concerns a family of finite automata networks, not one-step block-map fibers of the infinite Life cellular automaton.
- Ville Salo and Ilkka Törmä, gol-agars, GitHub software repository, commit a39d66a4a9278a1a6cfb5adc1a8282cd2f18d556 (accessed 2026). README and verify_agars.py, accessed 2026-07-28. ↗software · software source · commit a39d66a4a9278a1a6cfb5adc1a8282cd2f18d556 · checked 2026-07-28Source use: data used.Reused material: The 6 by 3 Köynnös periodic bit pattern.Reuse basis: licensed · rights holder: Ville Salo and Ilkka Törmä · MIT License · checked 2026-07-28 by TheoremDB packet review.Required attribution: Köynnös pattern by Ville Salo and Ilkka TörmäFor Strong block universality of Conway's Game of Life: MIT-licensed companion implementation for the self-forcing agar checks and source of the Köynnös pattern data reproduced here.MIT-licensed companion implementation for the self-forcing agar checks and source of the Köynnös pattern data reproduced here.
- Ville Salo and Ilkka Törmä, gol-backward-comp, GitHub software repository, commit 2ff235848fb9d62ad4ffbbe1ada37d544d63252b (accessed 2026). README and verify_pt1.py, accessed 2026-07-28. ↗software · software source · commit 2ff235848fb9d62ad4ffbbe1ada37d544d63252b · checked 2026-07-28Source use: citation only.For Strong block universality of Conway's Game of Life: MIT-licensed companion repository for the 2025 paper's gadget data and verification script.MIT-licensed companion repository for the 2025 paper's gadget data and verification script.
- Ville Salo and Ilkka Törmä, gol-preim, GitHub software repository, commit 3d80ff51ef658974f5c9f94cdb8c6a2265bef5f9 (accessed 2026). README and patfinder.py, accessed 2026-07-28. ↗software · software source · commit 3d80ff51ef658974f5c9f94cdb8c6a2265bef5f9 · checked 2026-07-28Source use: citation only.For Strong block universality of Conway's Game of Life: MIT-licensed hill-climbing implementation used to search for constrained-preimage gadgets.MIT-licensed hill-climbing implementation used to search for constrained-preimage gadgets.
Original CC0 record prose for Salo and Törmä's strong-universality question.