Degrees of unsolvability of
2-dimensional subshifts of finite type

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

August 21, 2007

This is an abstract and references for a talk to be given at a Dynamical Systems Workshop at the Pennsylvania State University, Department of Mathematics, October 18-21, 2007.

Abstract

We apply some fundamental concepts and results from mathematical logic in order to obtain an apparently new counterexample in symbolic dynamics. Two sets $X$ and $Y$ are said to be strongly equivalent if there exist partial recursive functionals from $X$ into $Y$ and vice versa. The strong degree of $X$ is the equivalence class of $X$ under strong equivalence. There is an extensive recursion-theoretic literature on the lattice of strong degrees of nonempty $\Pi^0_1$ subsets of the Cantor space. This lattice is known as $\mathcal{P}_s$. We prove that $\mathcal{P}_s$ consists precisely of the strong degrees of 2-dimensional subshifts of finite type. We use this result to obtain an infinite collection of 2-dimensional subshifts of finite type which are, in a certain sense, mutually incompatible.

Bibliography

1

Stephen Binns and Stephen G. Simpson.
Embeddings into the Medvedev and Muchnik lattices of $\Pi^0_1$ classes.
Archive for Mathematical Logic, 43:399-414, 2004.

2

Albert A. Muchnik.
On strong and weak reducibilities of algorithmic problems.
Sibirskii Matematicheskii Zhurnal, 4:1328-1341, 1963.
In Russian.

3

Stephen G. Simpson.
Medvedev degrees of 2-dimensional subshifts of finite type.
Ergodic Theory and Dynamical Systems, to appear.
Preprint, 8 pages, 1 May 2007.

4

Stephen G. Simpson.
Mass problems and randomness.
Bulletin of Symbolic Logic, 11:1-27, 2005.

5

Stephen G. Simpson.
An extension of the recursively enumerable Turing degrees.
Journal of the London Mathematical Society, 75:287-297, 2007.

6

Stephen G. Simpson.
Mass problems and almost everywhere domination.
Mathematical Logic Quarterly, 53:483-492, 2007.

7

Stephen G. Simpson.
Mass problems and intuitionism.
Preprint, 9 pages, 1 August 2007, submitted for publication.

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 2007-10-02