Durand, Bruno; Levin, Leonid A.; Shen, Alexander Complex tilings. (English) Zbl 1141.03021 J. Symb. Log. 73, No. 2, 593-613 (2008). Summary: 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 \(\mathcal O(n)\) Kolmogorov complexity of its (\(n\times n\))-squares. We construct tile sets for which this bound is tight: all (\(n\times 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. Cited in 1 ReviewCited in 15 Documents MSC: 03D80 Applications of computability and recursion theory 68Q30 Algorithmic information theory (Kolmogorov complexity, etc.) 03D28 Other Turing degree structures 52C20 Tilings in \(2\) dimensions (aspects of discrete geometry) Keywords:tilings; Kolmogorov complexity; recursion theory; Turing degrees of unsolvability PDF BibTeX XML Cite \textit{B. Durand} et al., J. Symb. Log. 73, No. 2, 593--613 (2008; Zbl 1141.03021) Full Text: DOI References: [1] DOI: 10.1002/j.1538-7305.1961.tb03975.x · doi:10.1002/j.1538-7305.1961.tb03975.x [2] Proceedings of the Symposium on Mathematical Theory of Automata pp 23– (1962) [3] DOI: 10.1023/A:1004823720305 · Zbl 0973.68158 · doi:10.1023/A:1004823720305 [4] Mathematical Intelligencer 27 pp 64– (2004) [5] STOC pp 732– (2001) [6] DOI: 10.1016/S0304-3975(99)00027-4 · Zbl 1062.05502 · doi:10.1016/S0304-3975(99)00027-4 [7] STACS’00 1770 (2000) [8] The classical decision problem (1996) [9] The undecidability of the domino problem 66 (1966) · Zbl 0199.30802 [10] Appendix A: ”Tiling problems” pp 407– (1996) [11] DOI: 10.1007/BF01418780 · Zbl 0197.46801 · doi:10.1007/BF01418780 [12] Classical recursion theory (1989) [13] Nonrecursive tilings of the plane, ii 39 pp 286– (1974) · Zbl 0299.02054 [14] An introduction to Kolmogorov complexity and its applications (1997) · Zbl 0866.68051 [15] DOI: 10.1093/comjnl/bxh124 · Zbl 05001561 · doi:10.1093/comjnl/bxh124 [16] DOI: 10.1137/0215020 · Zbl 0589.68032 · doi:10.1137/0215020 [17] Quasicrystals. The state of the art pp 185– (1991) [18] Nonrecursive tilings of the plane. I 39 pp 283– (1974) · Zbl 0299.02054 [19] Siberian Journal of Mathematics 13 pp 459– (1972) [20] DOI: 10.1016/0022-0000(91)90007-R · Zbl 0825.68420 · doi:10.1016/0022-0000(91)90007-R This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.