Tiling Decidability Thresholds and the Einstein Tile's Aperiodic Order — E8 Intelligence Research
- 1Independent Researcher, United Kingdom
Abstract
FINDING: Tiling decidability collapses from algorithmic certainty to undecidability at dimension thresholds, while aperiodic single-tile constructions (Einstein tile) reveal that local rules can force global non-periodicity — a deep link between computation limits and crystallographic order. MATH: - Translational tiling: finite F ⊂ ℤd tiles ℤd iff ∃ T ⊂ ℤd such that ℤd = ⨁t ∈ T (F+t) (direct sum, disjoint translates). - Decidability: For d=1,2 — decidable (Berger 1966, later simplified). For d ≥ 3 — undecidable (Greenfeld & Tao, 2021; also Greenfeld's work). - Finite tiling problem: undecidable in Euclidean plane (Kari 1994) and hyperbolic plane (Margenstern, 2007). - Domino problem (Wang tiles): undecidable in ℤ2 (Berger 1966). - Einstein tile: single aperiodic tile (Smith et al., 2023) — a 13-sided polygon (hat) with no periodic tiling of the plane. CONNECTION
Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
Related
- The Busy Beaver Challenge: BB(5) Solved, Higher-Order Functions and Oracle Decidability — E8 Intelligence Research
- The Busy Beaver Function: From BB(5) to Oracle Machines and Decidability — E8 Intelligence Research
- Collatz Conjecture via Automorphic Cayley Graphs and Decidability — E8 Intelligence Research
- Quasicrystals: Forbidden Symmetry and Golden-Ratio Tiling in Aperiodic Order — E8 Intelligence Research
- Aperiodic Order from Simple Rules: Penrose Tiling, Golden Ratio, and Undecidability — E8 Intelligence Research
BibTeX
@misc{caldin2026tiling,
title = {{Tiling Decidability Thresholds and the Einstein Tile's Aperiodic Order — E8 Intelligence Research}},
author = {Andrew Stewart Caldin},
howpublished = {Zenodo},
year = {2026},
month = oct,
doi = {10.5281/zenodo.23635485},
url = {https://zenodo.org/records/23635485},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Tiling Decidability Thresholds and the Einstein Tile's Aperiodic Order — E8 Intelligence Research
AU - Andrew Stewart Caldin
PY - 2026
DA - 2026/10/25
PB - Zenodo
DO - 10.5281/zenodo.23635485
UR - https://zenodo.org/records/23635485
AB - FINDING: Tiling decidability collapses from algorithmic certainty to undecidability at dimension thresholds, while aperiodic single-tile constructions (Einstein tile) reveal that local rules can force global non-periodicity — a deep link between computation limits and crystallographic order. MATH: - Translational tiling: finite F ⊂ ℤ^d tiles ℤ^d iff ∃ T ⊂ ℤ^d such that ℤ^d = ⨁_t ∈ T (F+t) (direct sum, disjoint translates). - Decidability: For d=1,2 — decidable (Berger 1966, later simplified). For d ≥ 3 — undecidable (Greenfeld & Tao, 2021; also Greenfeld's work). - Finite tiling problem: undecidable in Euclidean plane (Kari 1994) and hyperbolic plane (Margenstern, 2007). - Domino problem (Wang tiles): undecidable in ℤ^2 (Berger 1966). - Einstein tile: single aperiodic tile (Smith et al., 2023) — a 13-sided polygon (hat) with no periodic tiling of the plane. CONNECTION Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
ER -