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
- Average Case Complete Problems
- Average case completeness
- scientific article; zbMATH DE number 1010621 (Why is no real title available?)
- 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
(28)- From logic to tiling
- Seas of squares with sizes from a \(\Pi_{1}^{0}\) set
- Characterizing entropy dimensions of minimal mutidimensional subshifts of finite type
- Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts
- Countable sofic shifts with a periodic direction
- Quasiperiodicity and non-computability in tilings
- Kolmogorov complexity as a language
- \it \Pi^0_1 Sets and Tilings
- Fixed Point and Aperiodic Tilings
- Effective closed subshifts in 1D can be implemented in 2D
- Asymptotic Cellular Complexity
- High Complexity Tilings with Sparse Errors
- Turing degrees of multidimensional SFTs
- Fixed-point tile sets and their applications
- Cototal enumeration degrees and their applications to effective mathematics
- The expressiveness of quasiperiodic and minimal shifts of finite type
- scientific article; zbMATH DE number 7471005 (Why is no real title available?)
- Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
- Aperiodic tilings and entropy
- On the expressive power of quasiperiodic SFT
- Complex tilings
- Shift-complex sequences
- Deep _1⁰ classes
- Two notes on subshifts
- Bridging computational notions of depth
- Structure and computability of preimages in the Game of Life
- Kolmogorov complexity as a combinatorial tool
- Dimensionality and randomness
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)
