Symbolic dynamics and degrees of unsolvability

Stephen G. Simpson

Department of Mathematics

Pennsylvania State University

http://www.math.psu.edu/simpson/

December 17, 2008

Stephen G. Simpson

Department of Mathematics

Pennsylvania State University

http://www.math.psu.edu/simpson/

December 17, 2008

This is the abstract of my 15-minute talk at a special session on Logic and Dynamical Systems, sponsored by the American Mathematical Society (AMS) and the Association for Symbolic Logic (ASL). The session is part of the Joint Mathematics Meetings, January 5-8, 2009 in Washington, DC.

Let be a finite set of symbols. The *-dimensional shift
space on* is
with shift operators and given by
and
. A
*-dimensional subshift* is a nonempty, closed subset of
which is invariant under and . A -dimensional subshift
is said to be *of finite type* if it is defined by a finite set
of excluded finite configurations of symbols. We regard real numbers
and points of
as Turing oracles. If and are sets of
Turing oracles, we say that *is Muchnik reducible to* if
each can be used to compute some . The *Muchnik
degree of* is the equivalence class of under mutual Muchnik
reducibility. We prove that the Muchnik degrees of -dimensional
subshifts of finite type are the same as the Muchnik degrees of
nonempty, effectively closed sets of real numbers. We then apply
known results about such Muchnik degrees to obtain an infinite family
of -dimensional subshifts of finite type which are, in a certain
strong sense, mutually independent. Our application is stated purely
in terms of symbolic dynamics, with no mention of Muchnik reducibility.

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-12-17

Stephen G Simpson 2008-12-17