Degrees of unsolvability of
2-dimensional subshifts of finite type

Stephen G. Simpson
Pennsylvania State University
NSF DMS-0600823, DMS-0652637
http://www.math.psu.edu/simpson/
simpson@math.psu.edu

Dynamical Systems Seminar
University of Maryland
Thursday, November 13, 2008

Abstract

We apply some concepts and results from mathematical logic in order to obtain an apparently new counterexample in 2-dimensional symbolic dynamics. A set $X$ is said to be Muchnik reducible to a set $Y$ if each point of $Y$ can be used as a Turing oracle to compute a point of $X$. The Muchnik degree of $X$ is the equivalence class of $X$ 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 $\mathcal{P}_w$. We prove that $\mathcal{P}_w$ 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.

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, 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