Complex Tilings
<|reference_start|>Complex Tilings: 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<|reference_end|>
@article{durand2001complex,
    title={Complex Tilings},
    author={Bruno Durand, Leonid A. Levin, Alexander Shen},
    journal={Journal of Symbolic Logic, 73(2):593-613, 2008},
    year={2001},
    doi={10.2178/jsl/1208359062},
    archivePrefix={arXiv},
    eprint={cs/0107008},
    primaryClass={cs.CC cs.DM}
}