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: 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.
10.
Stephen G. Simpson, Medvedev degrees of -dimensional subshifts of finite type, to appear.
11.Robert
I. Soare, Recursively enumerable sets and degrees,
Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study
of computable functions and computably generated sets. MR 882921
(88m:03003)
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)
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
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)
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)
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)