The undecidability of the domino problem

1966/01/01 by Robert Berger, Robert E. Berger · 977 citations
Chemistry · Mathematics · #Chemistry #Domino #Domino effect #History and Theory of Mathematics #Law #Mathematics #Political science

paper · doi:10.1090/memo/0066

published in Memoirs of the American Mathematical Society 0(66), 0 (American Mathematical Society)

openalex publication_date 1966/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Cited by

• Undecidability of Tiling with a Tromino
• Self-simulable groups
• Characterization and Topological Behavior of Homomorphism Tree-Shifts
• Is the injectivity of the global function of a cellular automaton in the hyperbolic plane undecidable?
• Pattern avoidance is not P-recursive
• It's a Tough Nanoworld: in Tile Assembly, Cooperation is not (strictly) more Powerful than Competition
• An Optimal Algorithm for Tiling the Plane with a Translated Polyomino
• Matching Rules for the Sphinx Tiling Substitution
• The complexity of generalized domino tilings
• 1D Effectively Closed Subshifts and 2D Tilings
• Infinite games with finite knowledge gaps
• Periodicity in tilings
• Complexity Results and Practical Algorithms for Logics in Knowledge Representation
• Approximating entropy for a class of \zz² Markov Random Fields and pressure for a class of functions on \zz² shifts of finite type
• A linear algorithm for Brick Wang tiling
• Construction of infinite finitely presented nilsemigroup
• Seas of squares with sizes from a Π⁰₁ set
• Undecidable translational tilings with only two tiles, or one nonabelian tile
• On the cohomology of homshifts
• Tilings and Submonoids of Metabelian Groups
• Translational tilings: structured or wild?
• Parametrized complexity of relations between multidimensional subshifts
• A primer on substitution tilings of the Euclidean plane
• On Decidability of Expressive Description Logics with Composition of Roles in Number Restrictions
• Fixed-point tile sets and their applications
• Constructions with Countable Subshifts of Finite Type
• Tessellations and Positional Representation
• The computation of overlap coincidence in Taylor-Socolar substitution tiling
• The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
• Subshifts with sparse traces
• Solving Pictorial Jigsaw Puzzle by Stigmergy-inspired Internet-based Human Collective Intelligence
• Undecidability of Translational Tiling with 2 Polycubes
• Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
• Undecidability of Tiling the Plane with a Set of 5 Polyominoes
• Hard Tiling Problems with Simple Tiles
• An Application of Topological Multiple Recurrence to Tiling
• The structure of translational tilings in ℤ^d
• Universality in symbolic dynamics constrained by Medvedev degrees
• Algorithms for translational tiling
• Three characterizations of a self-similar aperiodic 2-dimensional subshift
• Pattern Complexity of Aperiodic Substitutive Subshifts
• Undecidability of the Spectral Gap (short version)
• Rectangular tileability and complementary tileability are undecidable
• On physical problems that are slightly more difficult than QMA
• Simulation of minimal effective dynamical systems on the Cantor sets by minimal tridimensional subshifts of finite type
• Decidability of plane edge coloring with three colors
• Partial decidability protocol for the Wang tiling problem from statistical mechanics and chaotic mapping
• Strongly aperiodic subshifts of finite type on hyperbolic groups
• Combinatorial substitutions and sofic tilings
• Limit Sets and Internal Transitivity in Free Group Actions
• Minimal sofic shift on a group that is not finitely-generated
• Independent Set Enumeration and Estimation of Related Constants of Grid Graphs and Their Variants
• Tiling simply connected regions with rectangles
• Fixed Point Constructions in Tilings and Cellular Automata
• Complexity of two-variable Dependence Logic and IF-Logic
• Undecidability of Translational Tiling of the Plane with Four Tiles
• Diamonds and Dominoes: Impossibility Results for Associative Modal Logics
• SHACL Satisfiability and Containment (Extended Paper)
• Undecidability of Translational Tiling of the Plane with Orthogonally Convex Polyominoes
• Two Tiling is Undecidable
• Translation-like Actions and Aperiodic Subshifts on Groups
• On the finite-dimensional marginals of shift-invariant measures
• Lattice tilings of Hilbert spaces
• Turing degrees of multidimensional SFTs
• Boundary action of automaton groups without singular points and Wang tilings
• An aperiodic monotile that forces nonperiodicity through dendrites
• Approximating the Hard Square Entropy Constant with Probabilistic Methods
• Theory of Computation of Multidimensional Entropy with an Application to the Monomer-Dimer Problem
• A remark on inverse limits of effective subshifts
• Polyominoes Simulating Arbitrary-Neighborhood Zippers and Tilings
• Ordine privo di periodicità: il fascino matematico delle tassellazioni
• Concrete Domains Meet Expressive Cardinality Restrictions in Description Logics (Extended Version)
• Pathographs and some (un)decidability results
• Effective closed subshifts in 1D can be implemented in 2D
• Aperiodic Subshifts of Finite Type on Groups
• Multidimensional tilings and MSO logic
• The domino problem on groups of polynomial growth
• Hard Tiling Problems with Simple Tiles
• Upper bounds on the growth rates of hard squares and related models via corner transfer matrices
• Complexity of Two-Dimensional Patterns
• 2D cellular automata: dynamics and undecidability
• Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity
• Mechanical Computing: The Computational Complexity of Physical Devices
• Superintuitionistic predicate logics of linear frames: undecidability with two individual variables
• Homological aperiodic tilings of 3-dimensional geometries
• Stellar Resolution: Multiplicatives
• Fixed-point tile sets and their applications
• Undecidability of the Emptiness Problem of Deterministic Propositional While Programs with Graph Loop: Hypothesis Elimination Using Loops
• The structure of the models of decidable monadic theories of graphs
• The Nature of Computation
• Reversibility of 2D cellular automata is undecidable
• On Derivatives and Subpattern Orders of Countable Subshifts
• An aperiodic set of 13 Wang tiles
• Undecidability and nonperiodicity for tilings of the plane
• On column-convex and convex Carlitz polyominoes
• Two-dimensional cellular automata
• Dominoes and the complexity of subclasses of logical theories
• Reversibility and surjectivity problems of cellular automata
• Basic Concepts of Cellular Automata
• Packing, covering and tiling in two-dimensional spaces
• NP -completeness of the game Kingdomino TM
• Some Properties of Lattice Substitution Systems
• Modular-topology optimization with Wang tilings: an application to truss structures
• Epistemic Horizons and the Foundations of Quantum Mechanics
• Algorithmic properties of first-order modal logics of linear Kripke frames in restricted languages
• On aperiodic sets of Wang tiles
• Topological completely positive entropy is no simpler in \mathbb Z²-SFTs
• Undecidability of the Spectral Gap (full version)
• The complexity of some regex crossword problems
• One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly\n System, or Tiling System with a Single Puzzle Piece
• Directional Expansiveness for Rd-Actions and for Penrose Tilings
• On the Weierstrass Preparation Theorem over General Rings
• A general framework for quasi-isometries in symbolic dynamics beyond groups
• Tessellation [wikipedia]