×

zbMATH — the first resource for mathematics

Complex tilings. (English) Zbl 1141.03021
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.

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)
PDF BibTeX XML Cite
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.