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(<italic>n</italic>) Kolmogorov complexity of its (<italic>n\times n</italic>)-squares. We construct tile sets for which this bound is nearly tight: all tilings have complexity ><italic>n/r(n)</italic>, given any unbounded computable monotone <italic>r</italic>. This adds a quantitative angle to classical results on non-recursivity of tilings -- that we also develop in terms of Turing degrees of unsolvability.