The Undecidability of the Domino Problem
From MaRDI portal
Publication:5141335
DOI10.1007/978-3-030-57666-0_6zbMath1457.52017OpenAlexW2775667632MaRDI QIDQ5141335
Pascal Vanier, Emmanuel Jeandel
Publication date: 18 December 2020
Published in: Lecture Notes in Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-030-57666-0_6
Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Quasicrystals and aperiodic tilings in discrete geometry (52C23) Tiling dynamics (37B52)
Related Items (4)
Substitutive structure of Jeandel-Rao aperiodic tilings ⋮ Undecidable translational tilings with only two tiles, or one nonabelian tile ⋮ Graph subshifts ⋮ Arithmetical hierarchy of the Besicovitch-stability of noisy tilings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fixed-point tile sets and their applications
- Combinatorics and topology of the Robinson tiling
- Tilings of the plane and Thurston semi-norm
- Substitutions in dynamics, arithmetics and combinatorics
- A characterization of the entropies of multidimensional shifts of finite type
- On the dynamics and recursive properties of multidimensional symbolic systems
- A small aperiodic set of Wang tiles
- Matching rules and substitution tilings
- Aperiodic tiles
- Seas of squares with sizes from a \(\Pi_{1}^{0}\) set
- Local rules and global order, or aperiodic tilings
- Tilings, substitution systems and dynamical systems generated by them
- Undecidability and nonperiodicity for tilings of the plane
- Turing-machines and the Entscheidungsproblem
- Putting the Pieces Together: Understanding Robinson's Nonperiodic Tilings
- ENTSCHEIDUNGSPROBLEM REDUCED TO THE AEA CASE
- Quelles tuiles ! (Pavages apériodiques du plan et automates bidimensionnels)
- Two-by-Two Substitution Systems and the Undecidability of the Domino Problem
- Fixed Point and Aperiodic Tilings
- Periodicity and Immortality in Reversible Computing
- The Tiling Problem Revisited (Extended Abstract)
- The Nilpotency Problem of One-Dimensional Cellular Automata
- Nonrecursive tilings of the plane. I
- Nonrecursive tilings of the plane. II
- Linear sampling and the ∀∃∀ case of the decision problem
- An Introduction to Symbolic Dynamics and Coding
- An aperiodic set of 11 Wang tiles
- Computational Complexity
- Forbidden information
- Medvedev degrees of two-dimensional subshifts of finite type
- Two-Tape Simulation of Multitape Turing Machines
- The undecidability of the Turing machine immortality problem
- The undecidability of the domino problem
- An Unsolvable Problem of Elementary Number Theory
This page was built for publication: The Undecidability of the Domino Problem
