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 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 , there is a and an infinite binary sequence such that if is a substring of , then has Kolmogorov complexity greater than .

The second result says that from the standpoint of computability theory, any behavior possible from an arbitrary effectively closed subset of (i.e., a class) is exhibited by an effectively closed subshift. In technical terms, every Medvedev degree contains a subshift. This answers a question of Simpson.

**1.**Douglas Cenzer, S. Ali Dashti, and Jonathan L. F. King,*Effective symbolic dynamics*, Proceedings of the Fourth International Conference on Computability and Complexity in Analysis (CCA 2007) (Ruth Dillhage, Tanja Grubba, Andrea Sorbi, Klaus Weihrauch, and Ning Zhong, eds.), Electronic Notes in Theoretical Computer Science, vol. 202, Elsevier, 2008, CCA 2007, Siena, Italy, June 16-18, 2007, pp. 89-99. MR**2432730 (2009m:37021)****2.**Bruno Durand, Leonid Levin, and Alexander Shen,*Complex tilings*, Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (New York), ACM, 2001, pp. 732-739 (electronic). MR**2120376****3.**Bruno Durand, Leonid A. Levin, and Alexander Shen,*Complex tilings*, J. Symbolic Logic**73**(2008), no. 2, 593-613. MR**2414467 (2009f:52046)****4.**Ming Li and Paul Vitányi,*An introduction to Kolmogorov complexity and its applications*, third ed., Texts in Computer Science, Springer, New York, 2008. MR**2494387 (2010c:68058)****5.**Douglas Lind and Brian Marcus,*An introduction to symbolic dynamics and coding*, Cambridge University Press, Cambridge, 1995. MR**1369092 (97a:58050)****6.**Yu. T. Medvedev,*Degrees of difficulty of the mass problem*, Doklady Akademii Nauk SSSR**104**(1955), 501-504. MR**0073542 (17:448b)****7.**André Nies,*Computability and randomness*, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. MR**2548883****8.**Hartley Rogers, Jr.,*Theory of recursive functions and effective computability*, second ed., MIT Press, Cambridge, MA, 1987. MR**886890 (88b:03059)****9.**A. Yu. Rumyantsev and M. A. Ushakov,*Forbidden substrings, Kolmogorov complexity and almost periodic sequences*, STACS 2006, Lecture Notes in Comput. Sci., vol. 3884, Springer, Berlin, 2006, pp. 396-407. MR**2249384 (2007c:68119)****10.**Stephen G. Simpson,*Medvedev degrees of -dimensional subshifts of finite type*, to appear.**11.**R. I. Soare,*Recursively enumerable sets and degrees*, A study of computable functions and computably generated sets, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. MR**0882921 (88m:03003)**

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

Email:
jmiller@math.wisc.edu

DOI:
https://doi.org/10.1090/S0002-9939-2011-11000-1

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.