2012/04/01 by STEPHEN G. SIMPSON · 1 citation
paper · doi:10.1017/etds.2012.152
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 ℰ w consist 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.