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)



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?)

  • 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 $ 2$-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)

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.

American Mathematical Society