We apply some concepts and results from mathematical logic in order to obtain an apparently new counterexample in 2-dimensional symbolic dynamics. A set is said to be Muchnik reducible to a set if each point of can be used as a Turing oracle to compute a point of . The Muchnik degree of is the equivalence class of under the equivalence relation of mutual Muchnik reducibility. There is an extensive recursion-theoretic literature concerning the lattice of Muchnik degrees of nonempty effectively closed sets in Euclidean space. This lattice is known as . We prove that consists precisely of the Muchnik degrees of 2-dimensional subshifts of finite type. We apply this result to obtain an infinite collection of 2-dimensional subshifts of finite type which are, in a certain sense, mutually incompatible. Our application is stated in purely dynamical terms, with no mention of recursion theory. We speculate on possible correlations between the dynamical properties of a 2-dimensional subshift of finite type and its Muchnik degree.
This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)
Copyright © 1993, 1994, 1995, 1996,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 abstract
The translation was initiated by Stephen G Simpson on 2008-11-11