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.
Stephen G. Simpson, Medvedev degrees of -dimensional subshifts of finite type, to appear.
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
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)
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)