Complex Tilings

Details Complex Tilings Complex Tilings

2001-07-04

arxiv.org/abs/cs/0107008v3

Computer Science

Computational Complexity

An extended abstract of a weaker version of this article appeared in Proceedings of the Annual ACM Symposium on Theory of Comp

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Complex Tilings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complex Tilings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complex Tilings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-652388