Complex tilings

We study the minimal complexity of tilings of a plane with a given tile set. We note that any tile set admits either no tiling or some tiling with \ooo( n ) Kolmogorov complexity of its ( n\times n )-squares. We construct tile sets for which this bound is nearly tight: all tilings have complexity > n/r(n) , given any unbounded computable monotone r . This adds a quantitative angle to classical results on non-recursivity of tilings -- that we also develop in terms of Turing degrees of unsolvability.

Authors

• Bruno Durand 0001
• Leonid A. Levin
• Alexander Shen 0001

Keywords

• Kolmogrov complexity
• recursion theory
• tilings