Complex Tilings

Abstract

We study the minimal complexity of tilings of a plane with a given tile set. We note that every tile set admits either no tiling or some tiling with O(n) Kolmogorov complexity of its n-by-n squares. We construct tile sets for which this bound is tight: all n-by-n squares in all tilings have complexity at least n. This adds a quantitative angle to classical results on non-recursivity of tilings -- that we also develop in terms of Turing degrees of unsolvability. Keywords: Tilings, Kolmogorov complexity, recursion theory

An extended abstract of a weaker version of this article appeared in Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), 2001

References in corpus (2)

• Reliable Cellular Automata with Self-Organization
• Aperiodic Tilings: Breaking Translational Symmetry

Cited by in corpus (11)

• Fixed Point and Aperiodic Tilings
• Aperiodic tilings and entropy
• Computing (or not) Quasi-Periodicity Functions of Tilings
• Fixed-point tile sets and their applications
• Effective closed subshifts in 1D can be implemented in 2D
• 1D Effectively Closed Subshifts and 2D Tilings
• Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
• The expressiveness of quasiperiodic and minimal shifts of finite type
• Fixed Point Constructions in Tilings and Cellular Automata
• Complexity and Avoidance
• Kolmogorov complexity as a language