Résumé
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 G(n) Kolmogorov complexity of its (n x n)-squares. We construct tile sets for which this bound is tight: all (n x n)-squares in all tilings have complexity Omega(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.