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.

We provide some examples showing how game-theoretic arguments can be used in computability theory and algorithmic information theory: unique numbering theorem (Friedberg), the gap between conditional complexity and total conditional complexity, Epstein–Levin theorem and some (yet unpublished) result of Muchnik and Vyugin.