Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 


Two notes on subshifts

Author: Joseph S. Miller
Journal: Proc. Amer. Math. Soc. 140 (2012), 1617-1622
MSC (2010): Primary 37B10, 03D30; Secondary 03D32, 68Q30
Published electronically: August 31, 2011
MathSciNet review: 2869146
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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,\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$, there is a $ b\in\mathbb{N}$ and an infinite binary sequence $ X$ such that if $ \tau$ is a substring of $ X$, then $ \tau$ has Kolmogorov complexity greater than $ d \vert\tau\vert-b$.

The second result says that from the standpoint of computability theory, any behavior possible from an arbitrary effectively closed subset of $ n^{\mathbb{N}}$ (i.e., a $ \Pi^0_1$ class) is exhibited by an effectively closed subshift. In technical terms, every $ \Pi^0_1$ Medvedev degree contains a $ \Pi^0_1$ subshift. This answers a question of Simpson.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 37B10, 03D30, 03D32, 68Q30

Retrieve articles in all journals with MSC (2010): 37B10, 03D30, 03D32, 68Q30

Additional Information

Joseph S. Miller
Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706-1388

Received by editor(s): March 17, 2010
Received by editor(s) in revised form: August 12, 2010, and January 8, 2011
Published electronically: August 31, 2011
Additional Notes: The author was supported by the National Science Foundation under grants DMS-0945187 and DMS-0946325, the latter being part of a Focused Research Group in Algorithmic Randomness.
Communicated by: Julia Knight
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.