  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
