Symbolic dynamics and degrees of unsolvability

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.

Abstract

Let $A$ be a finite set of symbols. The $2$-dimensional shift space on $A$ is $A^{\mathbb{Z}\times\mathbb{Z}}$ 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^{\mathbb{Z}\times\mathbb{Z}}$ 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^{\mathbb{Z}\times\mathbb{Z}}$ 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.

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