Hostname: page-component-76fb5796d-skm99 Total loading time: 0 Render date: 2024-04-26T05:48:08.465Z Has data issue: false hasContentIssue false
  • English
  • Français

Medvedev degrees of two-dimensional subshifts of finite type

Published online by Cambridge University Press:  29 November 2012

STEPHEN G. SIMPSON
STEPHEN G. SIMPSON*
Affiliation:
Department of Mathematics, Pennsylvania State University, McAllister Building, Porlock Road, University Park, PA 16802, USA (email: simpson@math.psu.edu)
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, we apply some fundamental concepts and results from recursion theory in order to obtain an apparently new example in symbolic dynamics. Two sets X and Y are said to be Medvedev equivalent if there exist partial computable functionals from X into Y and vice versa. The Medvedev degree of X is the equivalence class of X under Medvedev equivalence. There is an extensive recursion-theoretic literature on the lattices ℰs and ℰw of Medvedev degrees and Muchnik degrees of non-empty effectively closed subsets of {0,1}ℕ. We now prove that ℰs and ℰwconsist precisely of the Medvedev degrees and Muchnik degrees of two-dimensional subshifts of finite type. We apply this result to obtain an infinite collection of two-dimensional subshifts of finite type which are, in a certain sense, mutually incompatible.

Type
Research Article
Information
Ergodic Theory and Dynamical Systems , Volume 34 , Issue 2 , April 2014 , pp. 679 - 688
Copyright
©2012 Cambridge University Press 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Alfeld, C.. Non-branching degrees in the Medvedev lattice of Π01 classes. J. Symbolic Logic 72 (2007), 81–97.Google Scholar
[2]Binns, S.. The Medvedev and Muchnik lattices of Π01 classes. PhD Thesis, Pennsylvania State University, August 2003.CrossRefGoogle Scholar
[3]Binns, S.. A splitting theorem for the Medvedev and Muchnik lattices. Math. Log. Q. 49 (2003), 327–335.Google Scholar
[4]Binns, S.. Small Π01 classes. Arch. Math. Logic 45 (2006), 393–410.Google Scholar
[5]Binns, S.. Hyperimmunity in 2ℕ. Notre Dame J. Form. Log. 48 (2007), 293–316.CrossRefGoogle Scholar
[6]Binns, S. and Simpson, S. G.. Embeddings into the Medvedev and Muchnik lattices of Π01 classes. Arch. Math. Logic 43 (2004), 399–414.Google Scholar
[7]Boyle, M.. Algebraic aspects of symbolic dynamics. Topics in Symbolic Dynamics and Applications (Temuco, 1997) (London Mathematical Society Lecture Note Series, 279). Eds. Blanchard, F., Maass, A. and Nogueira, A.. Cambridge University Press, Cambridge, 2000, pp. 57–88.Google Scholar
[8]Cenzer, D., Dashti, S. A. and King, J. L. F.. Effective symbolic dynamics. Math. Log. Q. 54 (2008), 460–469.Google Scholar
[9]Cenzer, D. and Hinman, P. G.. Density of the Medvedev lattice of Π01 classes. Arch. Math. Logic 42 (2003), 583–600.CrossRefGoogle Scholar
[10]Cole, J. A. and Simpson, S. G.. Mass problems and hyperarithmeticity. J. Math. Logic 7 (2008), 125–143.Google Scholar
[11]Davis, M.. Computability and Unsolvability. Dover Publications, New York, 1982.Google Scholar
[12]Downey, R. G. and Hirschfeldt, D. R.. Algorithmic Randomness and Complexity. Springer, New York, 2010.Google Scholar
[13]Hanf, W.. Nonrecursive tilings of the plane, I. J. Symbol. Logic 39 (1974), 283–285.Google Scholar
[14]Hochman, M. and Meyerovitch, T.. A characterization of the entropies of multidimensional shifts of finite type. Ann. of Math. (2) 171 (2010), 2011–2038.Google Scholar
[15]Hudelson, P.. Mass problems and initial segment complexity. 2010, submitted for publication.Google Scholar
[16]Levin, L. A.. Forbidden information. FOCS 2002: The 43rd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, 2002, pp. 761–768.Google Scholar
[17]Lind, D. and Marcus, B.. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge, 1995.CrossRefGoogle Scholar
[18]Medvedev, Y. T.. Degrees of difficulty of mass problems. Dokl. Akad. Nauk SSSR, n.s. 104 (1955), 501–504 (in Russian).Google Scholar
[19]Miller, J. S.. Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension. Adv. Math. 226 (2011), 373–384.Google Scholar
[20]Miller, J. S.. Two notes on subshifts. Proc. Amer. Math. Soc. 140(5) (2012), 1617–1622.Google Scholar
[21]Mozes, S.. Tilings, substitution systems, and the dynamical systems generated by them. J. Anal. Math. 53 (1989), 139–186.Google Scholar
[22]Mozes, S.. A zero entropy, mixing of all orders tiling system. Symbolic Dynamics and its Applications (Contemporary Mathematics, 135). Ed. Walters, P.. American Mathematical Society, Providence, RI, 1992, pp. 319–325.Google Scholar
[23]Muchnik, A. A.. On strong and weak reducibilities of algorithmic problems. Sibirsk. Mat. Zh. 4 (1963), 1328–1341 (in Russian).Google Scholar
[24]Myers, D.. Nonrecursive tilings of the plane, II. J. Symbol. Logic 39 (1974), 286–294.Google Scholar
[25]Nies, A.. Computability and Randomness. Oxford University Press, Oxford, 2009.Google Scholar
[26]Robinson, R. M.. Undecidability and nonperiodicity of tilings of the plane. Invent. Math. 12 (1971), 177–209.CrossRefGoogle Scholar
[27]Rogers, H.. Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.Google Scholar
[28]Simpson, S. G.. FOM: natural r.e. degrees; Pi01 classes. FOM e-mail list. http://www.cs.nyu.edu/mailman/listinfo/fom/. 13 August 1999.Google Scholar
[29]Simpson, S. G.. FOM: priority arguments; Kleene-r.e. degrees; Pi01 classes. FOM e-mail list. http://www.cs.nyu.edu/mailman/listinfo/fom/. 16 August 1999.Google Scholar
[30]Simpson, S. G.. Subsystems of Second Order Arithmetic. Springer, New York, 1999; 2nd edn, Cambridge University Press, Cambridge, 2009.Google Scholar
[31]Simpson, S. G.. Medvedev degrees of non-empty Π01 subsets of 2ω. COMP-THY e-mail list.http://listserv.nd.edu/archives/comp-thy.html. 9 June 2000.Google Scholar
[32]Simpson, S. G.. FOM: natural r.e. degrees. FOM e-mail listhttp://www.cs.nyu.edu/mailman/listinfo/fom/. 27 February 2005.Google Scholar
[33]Simpson, S. G.. Mass problems and randomness. Bull. Symbolic Logic 11 (2005), 1–27.CrossRefGoogle Scholar
[34]Simpson, S. G.. Π01 sets and models of WKL0. Reverse Mathematics 2001 (Lecture Notes in Logic, 21). Ed. Simpson, S. G.. Association for Symbolic Logic, Wellesley, MA, 2005, pp. 352–378.Google Scholar
[35]Simpson, S. G.. An extension of the recursively enumerable Turing degrees. J. Lond. Math. Soc. 75 (2007), 287–297.Google Scholar
[36]Simpson, S. G.. Mass problems and almost everywhere domination. Math. Logic Q. 53 (2007), 483–492.Google Scholar
[37]Simpson, S. G.. Some fundamental issues concerning degrees of unsolvability. Computational Prospects of Infinity: Proceedings of the Logic Workshop at the Institute for Mathematical Sciences, June 20–August 15, 2005, Part II: Presented Talks (Lecture Notes Series, Institute for Mathematical Sciences, 15). Eds. Chong, C.-T., Feng, Q., Slaman, T. A., Woodin, W. H. and Yang, Y.. World Scientific, Singapore, 2008, pp. 313–332.Google Scholar
[38]Simpson, S. G.. Mass problems and measure-theoretic regularity. Bull. Symbol. Logic 15 (2009), 385–409.Google Scholar
[39]Simpson, S. G.. Mass problems associated with effectively closed sets. Tohoku Math. J. 63(4) (2011), 489–517.Google Scholar
[40]Simpson, S. G.. Symbolic dynamics: entropy = dimension = complexity. Preprint, 2011, submitted for publication.Google Scholar
[41]Soare, R. I.. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer, New York, 1987.Google Scholar
[42]Walters (Ed), P.. Symbolic Dynamics and its Applications (Contemporary Mathematics, 135). American Mathematical Society, Providence, RI, 1992.Google Scholar
[43]Wang, H.. Proving theorems by pattern recognition, II. Bell Syst. Techn. J. 40 (1961), 1–42.Google Scholar