Two notes on subshifts
Author:
Open Access
- 31 August 2011
- journal article
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 140 (5) , 1617-1622
Abstract
We prove two unrelated results about subshifts. First, we give a condition on the lengths of forbidden words that is sufficient to guarantee that the corresponding subshift is nonempty. The condition implies that, for example, any sequence of binary words of lengths 5 , 6 , 7 , … 5,6,7,\dots is avoidable. As another application, we derive a result of Durand, Levin and Shen that there are infinite sequences such that every substring has high Kolmogorov complexity. In particular, for any d > 1 d>1 , there is a b ∈ N b\in \mathbb {N} and an infinite binary sequence X X such that if τ \tau is a substring of X X , then τ \tau has Kolmogorov complexity greater than d | τ | − b d\,|\tau |-b . The second result says that from the standpoint of computability theory, any behavior possible from an arbitrary effectively closed subset of n N n^{\mathbb {N}} (i.e., a Π 1 0 \Pi ^0_1 class) is exhibited by an effectively closed subshift. In technical terms, every Π 1 0 \Pi ^0_1 Medvedev degree contains a Π 1 0 \Pi ^0_1 subshift. This answers a question of Simpson.Keywords
This publication has 8 references indexed in Scilit:
- Computability and Randomness2009
- Complex tilingsThe Journal of Symbolic Logic, 2008
- Effective Symbolic DynamicsElectronic Notes in Theoretical Computer Science, 2008
- An Introduction to Kolmogorov Complexity and Its Applications2008
- Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences2006
- Complex tilings2001
- An Introduction to Symbolic Dynamics and Coding1995
- Recursively Enumerable Sets and Degrees1987