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

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

University of Maryland

Thursday, November 13, 2008

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
**LaTeX**2`HTML` 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

Stephen G Simpson 2008-11-11