SYMBOLIC DYNAMICS AND DEGREES OF UNSOLVABILITY

Stephen G. Simpson
Department of Mathematics
Pennsylvania State University
http://www.personal.psu.edu/t20/

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.

ABSTRACT

Let A be a finite set of symbols.  The 2-dimensional shift space on A
is A^ZxZ with shift operators S_1 and S_2 given by
S_1(x)(m,n)=x(m+1,n) and S_2(x)(m,n)=x(m,n+1).  A 2-dimensional
subshift is a nonempty, closed subset of A^ZxZ which is invariant
under S_1 and S_2.  A 2-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 A^ZxZ
as Turing oracles.  If X and Y are sets of Turing oracles, we say that
X is Muchnik reducible to Y if each y\in Y can be used to compute some
x\in X.  The Muchnik degree of X is the equivalence class of X under
mutual Muchnik reducibility.  We prove that the Muchnik degrees of
2-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 2-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.