# P2830: Strong block universality of Conway's Game of Life

- ID: `P2830`
- Reference: `life-strong-block-universality`
- Page: https://theoremdb.org/statements/P2830
- Record maturity: Reviewed problem with recorded work

## 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\)?

### Problem setup

- **Remark.** 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.** A two-dimensional subshift of finite type is a shift-invariant set of configurations specified by finitely many forbidden finite patterns.
- **Definition.** A block map is a shift-commuting map whose output at each site depends on a fixed finite neighborhood.
- **Remark.** 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.

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

## Status

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](#reference-1)

## Work

### Evidence for the current status

**Claim 1 (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.

The primary paper introduces weak, semiweak, and strong simulation for block maps. Its circuit-system block map is effectively strongly universal, while Theorem 4 proves that Conway's Game of Life is semiweakly universal. Question 2 asks whether the Life simulation can be made strong, which requires the selected preimage map to be bijective and hence to contain no extraneous Life preimages.

The focused search dated 2026-07-28 found no later source answering that exact block-map question. The bounded result in this packet tests a necessary consequence of strong universality against every macrotile dimension of area at most 11. It does not produce a universal construction or a counterexample block map, so the canonical problem remains open.

### Background and intake notes

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

### Other known results

- **Computation 1** (reproduced): Exact finite-torus enumeration rules out every positive macrotile dimension with area at most 11 for a strong Life simulation of the constant map from the binary full shift to a singleton.
- **Proposition 1** (supported): Salo and Törmä give a 6 by 3 periodic Life fixed point whose only global predecessor is itself; it therefore strongly simulates the constant map on a singleton SFT. [2](#reference-2) [4](#reference-4)
- **Claim 2** (reported): For the constant map from any SFT Y to a singleton, strong simulation would make one periodic Life fiber conjugate to Y under blocked shifts; every finite periodic-point count must therefore agree. [1](#reference-1)

### Prior approaches

- **Route 1** (supported): The dated audit confirmed that the exact one-step block-map question remains open in its primary source and separated it from self-enforcing agars and finite automata-network universality. [1](#reference-1) [2](#reference-2) [3](#reference-3) [5](#reference-5) [6](#reference-6)

### Open directions

- **Route 2** (reported): Use exact SAT or transfer methods to test macrocell areas 12 through 18 against several periodic-point counts for the constant binary-full-shift target.

### Runnable artifacts

- **Artifact 1** (reproduced): A deterministic Python program enumerates 7,038,802 periodic Life inputs, checks the area-11 binary-full-shift obstruction, and verifies 126 explicit 6 by 6 alternative predecessors for the 3 by 3 singleton fibers.
- **Artifact 2** (reproduced): A separate C++17 implementation reproduces all 16 macrotile rows, all 414 candidate outputs, and every doubled-fiber histogram used in the area-11 exclusion.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `life-strong-block-universality`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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 https://doi.org/10.1016/j.tcs.2025.115237
   - 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.
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Defines strong block-map simulation, proves effective semiweak universality for Life, and states the exact strong-universality question as open.
   - 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.
2. <a id="reference-2"></a>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 https://doi.org/10.4230/LIPIcs.ICALP.2022.131
   - 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
   - proceedings_article; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Supplies the closest unique-predecessor construction, a 6 by 3 periodic Life fixed point that strongly simulates the singleton target.
   - 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.
3. <a id="reference-3"></a>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 https://doi.org/10.1016/j.tcs.2024.114779
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source 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.
4. <a id="reference-4"></a>Ville Salo and Ilkka Törmä, gol-agars, GitHub software repository, commit a39d66a4a9278a1a6cfb5adc1a8282cd2f18d556 (accessed 2026). README and verify_agars.py, accessed 2026-07-28 https://github.com/ilkka-torma/gol-agars
   - software; software source; commit a39d66a4a9278a1a6cfb5adc1a8282cd2f18d556; checked 2026-07-28
   - Source 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; https://github.com/ilkka-torma/gol-agars/blob/a39d66a4a9278a1a6cfb5adc1a8282cd2f18d556/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.
5. <a id="reference-5"></a>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 https://github.com/ilkka-torma/gol-backward-comp
   - software; software source; commit 2ff235848fb9d62ad4ffbbe1ada37d544d63252b; checked 2026-07-28
   - Source 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.
6. <a id="reference-6"></a>Ville Salo and Ilkka Törmä, gol-preim, GitHub software repository, commit 3d80ff51ef658974f5c9f94cdb8c6a2265bef5f9 (accessed 2026). README and patfinder.py, accessed 2026-07-28 https://github.com/ilkka-torma/gol-preim
   - software; software source; commit 3d80ff51ef658974f5c9f94cdb8c6a2265bef5f9; checked 2026-07-28
   - Source 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.