Undecidability of translational monotilings

2023/09/18 by Rachel Greenfeld, Terence Tao, Greenfeld, Rachel +1 · 1 voice · 5 citations
Computer Science · #Cellular Automata and Applications #semigroups and automata theory #Computability, Logic, AI Algorithms

paper · pdf · doi:10.48550/arxiv.2309.09504

Abstract

In the 60's, Berger famously showed that translational tilings of ℤ² with multiple tiles are algorithmically undecidable. Recently, Bhattacharya proved the decidability of translational monotilings (tilings by translations of a single tile) in ℤ². The decidability of translational monotilings in higher dimensions remained unsolved. In this paper, by combining our recently developed techniques with ideas introduced by Aanderaa and Lewis, we finally settle this problem, achieving the undecidability of translational monotilings of (periodic subsets of) virtually ℤ² spaces, namely, spaces of the form ℤ²× G₀, where G₀ is a finite Abelian group. This also implies the undecidability of translational monotilings in ℤ^d, d≥ 3.

Cited by

• Undecidability of Tiling with a Tromino
• Translational tilings: structured or wild?
• Additive systems for ℤ are undecidable
• Undecidability of Translational Tiling with 2 Polycubes
• Undecidability of Translational Tiling of the Plane with Four Tiles

Discussions

• All the Terry Tao talk made me go and check out what he's up to nowadays and I felt a kind of nerd pride in the fact that one of his recent papers is on an undecidability problem tracing back to Hao W [bsky, 29 points, 2 comments]

Related

• Undecidability of Translational Tiling with Three Tiles
• Undecidable translational tilings with only two tiles, or one nonabelian tile
• Undecidability of Translational Tiling of the 3-dimensional Space with a Set of 6 Polycubes
• On the Undecidability of Tiling the 3-dimensional Space with a Set of 3 Polycubes
• Periodicity and decidability of tilings of ℤ²