Complex tilings
From MaRDI portal
Abstract: 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
Recommendations
Cites work
- scientific article; zbMATH DE number 1010621 (Why is no real title available?)
- Average Case Complete Problems
- Average case completeness
- Nonrecursive tilings of the plane. I
- Reliable cellular automata with self-organization
- The undecidability of the domino problem
- Tilings and quasiperiodicity.
- Undecidability and nonperiodicity for tilings of the plane
Cited in
(27)- Turing degrees of multidimensional SFTs
- Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
- High Complexity Tilings with Sparse Errors
- Two notes on subshifts
- Effective closed subshifts in 1D can be implemented in 2D
- From logic to tiling
- The expressiveness of quasiperiodic and minimal shifts of finite type
- Quasiperiodicity and non-computability in tilings
- On the expressive power of quasiperiodic SFT
- Structure and computability of preimages in the Game of Life
- Deep _1⁰ classes
- Kolmogorov complexity as a combinatorial tool
- Kolmogorov complexity as a language
- \it \Pi^0_1 Sets and Tilings
- Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts
- Characterizing entropy dimensions of minimal mutidimensional subshifts of finite type
- Cototal enumeration degrees and their applications to effective mathematics
- Asymptotic Cellular Complexity
- Fixed Point and Aperiodic Tilings
- Complex tilings
- Bridging computational notions of depth
- scientific article; zbMATH DE number 7471005 (Why is no real title available?)
- Shift-complex sequences
- Seas of squares with sizes from a \(\Pi_{1}^{0}\) set
- Fixed-point tile sets and their applications
- Aperiodic tilings and entropy
- Countable sofic shifts with a periodic direction
This page was built for publication: Complex tilings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3503757)
