DEGREES OF UNSOLVABILITY OF 2-DIMENSIONAL SUBSHIFTS OF FINITE TYPE

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

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 P_s.  We prove that 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.

REFERENCES

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.

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

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.

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

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

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

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