Medvedev degrees of
2dimensional subshifts of finite type
Stephen G. Simpson^{1}
Department of Mathematics
Submitted: May 1, 2007
This draft: September 5, 2012
Pennsylvania State University
Abstract:
In this paper we apply some fundamental concepts and results from
recursion theory in order to obtain an apparently new example in
symbolic dynamics. Two sets
and
are said to be
Medvedev equivalent if there exist partial computable
functionals from
into
and vice versa. The
Medvedev
degree of
is the equivalence class of
under Medvedev
equivalence. There is an extensive recursiontheoretic literature
on the lattices
and
of Medvedev degrees and Muchnik
degrees of nonempty effectively closed subsets of
. We
now prove that
and
consist precisely of the Medvedev
degrees and Muchnik degrees of 2dimensional subshifts of finite
type. We apply this result to obtain an infinite collection of
2dimensional subshifts of finite type which are, in a certain
sense, mutually incompatible.
Background
Definition 1.1
Let
be a finite set of symbols. The
full 2dimensional
shift on
is the dynamical system consisting of the natural
action of
on the compact set
. A
2dimensional subshift is a nonempty closed set
which is invariant under the action of
. A
2dimensional subshift
is said to be
of finite type if it
is defined by a finite set of forbidden configurations. An
interesting paper on 2dimensional subshifts of finite type is Mozes
[
27]. A standard reference for the 1dimensional
case is the book of Lind/Marcus [
23], which also
includes an appendix [
23, §13.10] on the
2dimensional case.
Definition 1.2
If
is a 2dimensional subshift, the
shift operators
are defined by
and
for all
and
. If
and
are 2dimensional subshifts, a
shift
morphism^{2} of
into
is a continuous function
which commutes with the shift operators, i.e.,
and
for all
.
It follows that
commutes with the action of
on
and
. A
shift isomorphism of onto is a shift morphism
of
onetoone onto
, i.e., a homeomorphism of
onto
which commutes with
and
. We say that
and
are
shift isomorphic if there exists a shift isomorphism of
onto
.
Remark 1.3
In the study of 2dimensional subshifts of finite type, it has been
useful to note that they are essentially the same thing as
tiling problems in the sense of Wang [
50].
On the one hand, if is a finite set of Wang tiles, let be
the set of tilings of the plane by . Identifying as a
subset of
, it is clear that is a 2dimensional
subshift of finite type. Conversely, given a 2dimensional subshift
of finite type, , it is easy to construct a finite set of Wang
tiles, , such that is computably isomorphic to .
Namely, let be a positive integer which is greater than or equal
to the diameters of all of the forbidden configurations defining
, and let
be the set of
configurations which do not contain any of the forbidden
configurations. Our isomorphism of onto associates to
each point a tiling defined by
for all
and
. The adjacency rules for
are: (a) is allowed to occur
immediately to the left of if and only if
for all and , and (b) is allowed to occur immediately below
if and only if
for all and
.
Mozes [27,28] and
recently Hochman/Meyerovitch [20] have used the
tiling methods of Wang [50] and Robinson
[32] to construct 2dimensional subshifts of finite
type with interesting dynamical properties.
Remark 1.4
In this paper we shall examine 2dimensional subshifts of finite
type from the viewpoint of
recursion theory, also known as
computability theory, the branch of mathematics which grew
out of Turing's celebrated theory of computability and
unsolvability. Some classical references for
recursion/computability theory are [
15,
33,
48]. Two
recent references are [
16,
31]. The purpose of
the next few definitions and remarks is to briefly explain the
recursiontheoretic concepts which we shall need in
§§
2 and
3 below.
Remark 1.7
The idea behind Medvedev and Muchnik degrees is to regard each set
as the solution set of a socalled ``mass
problem,''
, the problem of finding at one least element
of
, where ``to find'' means ``to compute in the sense of
Turing.'' Accordingly, one says that the problem
is
``solvable'' if it has at least one computable solution, i.e., the
set
contains at least one point which is Turing computable.
Similarly, one could say that
is ``reducible'' to
if each solution of
can be used as a Turing
oracle to compute at least one solution of
, or in other
words,
is Muchnik reducible to
. Thus for instance
is solvable if and only if
is Muchnik reducible to
for all
, if and only if
is Medvedev reducible to
for
all
. In general, the Medvedev or Muchnik degree of a mass
problem is a measure of the ``degree of unsolvability'' or ``degree
of difficulty'' which is inherent in the problem. In this way one
can use Medvedev and Muchnik degrees to classify unsolvable
mathematical problems.
Remark 1.8
For
it is straightforward to construct a computable
homeomorphism of
onto
. Therefore, the
Medvedev degrees and Muchnik degrees of subsets of
are the
same as those of subsets of
.
Remark 1.10 (the lattices
and
)
 The partial orderings
and
in Definition
1.9 are distributive lattices. Moreover, there is a
natural lattice homomorphism of
onto
obtained by
mapping the Medvedev degree of to the Muchnik degree of .
 The lattices
and
are mathematically rich and have
been studied extensively. See Alfeld [1], Binns
[2,3,4,5],
Binns/Simpson [6], Cenzer/Hinman [11],
Cole/Simpson [13], Hudelson [21], and
Simpson
[35,36,38,39,40,41,42,43,44,45,46].
Remark 1.11
For our purposes in this paper, we shall need to apply the above
concepts not only to subsets of
but also to subsets of
. In order to do this, we shall use a simple onetoone
correspondence between
and
. For instance, let
be the onetoone correspondence given by
where
We may then identify subsets of
with corresponding
subsets of
. In this way Definitions
1.6 and
1.9 and Remarks
1.7,
1.8 and
1.10 for subsets of
apply equally well to subsets
of
.
Remark 1.12
Recent research has revealed that
contains a large number of
specific, interesting Muchnik degrees associated with particular
mass problems which are of foundational interest. For example, the
top degree in
is the Muchnik degree of the problem of finding
a complete, consistent theory which contains the usual axioms for
firstorder arithmetic. Another interesting degree in
is the
Muchnik degree of the problem of finding an infinite sequence of
's and
's which is algorithmically random in the sense of
MartinLöf [
40,
42]. Other interesting degrees in
are closely related to other interesting topics in the
foundations of mathematics. Among these topics are reverse
mathematics [
37,
40], almost everywhere domination
[
43], measuretheoretic regularity [
45], the
hyperarithmetical hierarchy [
13,
45], effective
Hausdorff dimension [
25,
47] and Kolmogorov
complexity [
21]. A new survey of this research area is
[
46].
Medvedev degrees of subshifts
Remark 2.1
Let
be a 2dimensional subshift. In the following theorem we
see that the Medvedev degree of
, the Muchnik degree of
, and
the computable homeomorphism type of
depend only on the shift
isomorphism type of
. This suggests the possibility that
Medvedev degrees, Muchnik degrees, and computable homeomorphism
types may be useful as invariants for the problem of classifying
2dimensional subshifts up to shift isomorphism. More evidence for
such a possibility is presented in Theorems
2.5,
2.9 and
3.4 below.
Theorem 2.2
All shift morphisms are given by partial computable
functionals. If and are shift isomorphic, then and
are computably homeomorphic, hence Medvedev equivalent, hence
Muchnik equivalent.
Proof.Let and be finite sets of symbols such that and are
subshifts of the full 2dimensional shifts
and
respectively. Let be a shift morphism. By
the Curtis/Hedlund/Lyndon Theorem (see Boyle
[8] or Lind/Marcus [23])
is a block code, i.e., we can find an integer and a
projection
such that
for all and
. In particular is given by
a partial computable functional. If moreover is a shift
isomorphism of onto , it follows that is a computable
homeomorphism of onto . This completes the proof.
Remark 2.3
Let
be a 2dimensional subshift. If
contains a periodic
point, one can easily show (see for instance the second and third
paragraphs of [
32, §1]) that
contains a point
which is Turing computable, so by part 4 of Definition
1.9 the Medvedev degree of
is
, the degree of
solvable problems. Thus Medvedev degrees and Muchnik degrees are of
no interest in the case of subshifts with periodic orbits. However,
there are many 2dimensional subshifts of finite type which do not
have periodic points
[
19,
27,
28,
30,
32],
and in this case the Medvedev degrees and Muchnik degrees could well
serve as a useful classification tool. See also Remarks
1.12 and
2.10.
Remark 2.4
An open problem is to characterize the computable homeomorphism
types of 2dimensional subshifts of finite type. Clearly any
2dimensional subshift of finite type is an effectively closed
subset of
and is therefore computably homeomorphic to,
hence of the same Medvedev degree and Muchnik degree as, a nonempty
effectively closed subset of
. We shall now prove a
theorem in the opposite direction. Namely, every nonempty
effectively closed subset of
is of the same Medvedev
degree, hence of the same Muchnik degree, as some 2dimensional
subshift of finite type. This characterization of the Medvedev
degrees and Muchnik degrees of 2dimensional subshifts of finite
type appears to be new, but see Remark
2.7 below.
Theorem 2.5
Given a nonempty effectively closed set
, we
can find a 2dimensional subshift of finite type which is of the
same Medvedev degree as , hence of the same Muchnik degree as
.
Proof.Our proof uses the tiling constructions of Robinson
[32] and Hanf [19] and Myers
[30].
Let be a finite set of Wang tiles, and let be a
distinguished tile in . We write
. The tilings in are said to be
originconstrained. Given an effectively closed set
, Hanf [19] shows how to
construct an originconstrained tiling system and a
projection
such that
.
Namely, and are such that each originconstrained tiling
describes a nonhalting run of a particular
deterministic Turing machine program starting with
inscribed at positions
of the Turing machine tape.
The distinguished tile represents the initial internal state
of . We can then construct a fixed partial computable functional
which is independent of
and maps
to . Thus
and are computably homeomorphic.
Now, starting with and as above, Myers
[30] shows how to construct a finite set of tiles
and a projection with the following properties:
 is a Robinson set of tiles.
(Unexplained terms are defined in Myers' paper
[30].)
 For each tiling , the images of the
center rows of the finite boards of are
synchronized.
 For each tiling , the result of piecing
together the images of the center rows of the finite
boards of is
for some
. Using this piecingtogether procedure, we can
construct a fixed computable functional which maps to .
 Given an originconstrained tiling , we can
find a (nonunique) tiling such that
is the result of piecing together the
images of the center rows of the finite boards of .
Moreover, we can construct a fixed partial computable functional
which maps to such a .
Properties 3 and 4 imply that is Medvedev equivalent to
. Therefore, is Medvedev equivalent to .
Since is a 2dimensional subshift of finite type, our
theorem is proved.
Remark 2.6
Actually Hanf [
19] and Myers [
30]
dealt only with effectively closed sets
of
the form
separates
where
and
are recursively enumerable subsets of
.
However, their constructions work just as well for arbitrary
effectively closed sets
.
Remark 2.7
Leonid A. Levin has kindly informed us that our Theorem
2.5 was already implicit in his remark
[
22, last paragraph of §3] concerning
tilings of the plane with a 2adic coordinate system.
Definition 2.8
Let
be the set of all 2dimensional subshifts. For
we write
if there exists a shift morphism
. Obviously
is transitive and reflexive. We write
if
and
. Obviously
is an
equivalence relation on
. Obviously
whenever
and
are shift isomorphic, but the converse does not hold. Let
be the set of equivalence classes of
modulo
.
There is an obvious partial ordering of
induced by
.
It is easy to verify that, under this partial ordering,
is a
distributive lattice. Let
be the subset of
consisting of the 2dimensional subshifts of finite type. It is
easy to verify that
is a sublattice of
.
Theorem 2.9
There is a natural lattice homomorphism of
onto
.
Namely, for each
we map the equivalence class
of to the Medvedev degree of .
Proof.The greatest lower bound and least upper bound operations in each of
the lattices
,
,
,
are given by disjoint
union and Cartesian product respectively. In particular, our
mapping of
to
is a lattice homomorphism. By
Theorem 2.5 this homomorphism is onto
.
Remark 2.10
A consequence of Theorem
2.9 is that there is a natural
lattice homomorphism of
onto
, obtained by mapping
the
equivalence class of
to the Muchnik degree
of
. In particular we have a new invariant, the Muchnik degree,
associated to (shift isomorphism types of) 2dimensional subshifts
of finite type. Obviously this invariant is qualitatively different
from other such invariants which have been considered previously in
the symbolic dynamics literature. Moreover, this new invariant is
of clear interest, inasmuch as
is known to contain many
specific, natural Muchnik degrees which are closely related to
significant topics in the foundations of mathematics. See also
Remark
1.12 above.
An application
Remark 3.1
We shall now present an application which is stated purely in terms
of 2dimensional subshifts, with no reference to Medvedev degrees or
Muchnik degrees. Namely, we shall construct an infinite collection
of 2dimensional subshifts of finite type which are, in a certain
sense, mutually incompatible.
Definition 3.2
If
and
are 2dimensional subshifts on
and
symbols
respectively, let
and
be the disjoint union and
Cartesian product of
and
. These are 2dimensional subshifts
on
and
symbols respectively. If
is a
2dimensional subshift on
symbols, and if
are integers
such that
, let
.
This is a 2dimensional subshift on
symbols.
Theorem 3.4
We can find an infinite collection of 2dimensional subshifts of
finite type, , such that for all partitions of into two
subcollections, and , there is no shift morphism of
into for any
and
.
Proof.By Binns/Simpson [6] let , , be
nonempty effectively closed subsets of
whose Muchnik
degrees are independent, i.e.,
is
not Muchnik reducible to
provided
. By
Theorem 2.5, for each let be a
2dimensional subshift of finite type which is Medvedev equivalent,
to , hence Muchnik equivalent to . Let be the
collection , , and let
be a partition
of . By induction on
and
we can
easily show that neither of and is Muchnik reducible to the
other. Hence by Theorem 2.2 there is no shift
morphism of into or vice versa. Q.E.D.
Remark 3.5
In our proof of Theorem
3.4, all of the subshifts in
are of different Muchnik degrees, hence of different Medvedev
degrees. The referee has kindly informed us that, using classical
methods, one can obtain a similar result in Medvedev degree
.
Namely, for each prime number
choose an almost onetoone
extension of the
adic odometer.
Remark 3.6
In this paper we have dealt only with 2dimensional subshifts. What
about the 1dimensional case? Clearly Theorem
2.2
holds in this context. On the other hand, Theorems
2.5
and
2.9 and
3.4 fail, because all
1dimensional subshifts of finite type contain periodic points and
are therefore of Medvedev degree zero. (We thank the referee for
pointing out the failure of Theorem
3.4 in this
context.) What about effectively closed 1dimensional subshifts?
Cenzer/Dashti/King [
10] have constructed a 1dimensional
effectively closed subshift which is of nonzero Medvedev degree.
Recently Miller [
26] improved this result by
showing that Theorems
2.5 and
2.9 hold for
1dimensional effectively closed subshifts. And from this plus
Binns/Simpson [
6] it follows that Theorem
3.4 holds in the same context.
 1

Christopher Alfeld.
Nonbranching degrees in the Medvedev lattice of
classes.
Journal of Symbolic Logic, 72:8197, 2007.
 2

Stephen Binns.
The Medvedev and Muchnik Lattices of
Classes.
PhD thesis, Pennsylvania State University, August 2003.
VII + 80 pages.
 3

Stephen Binns.
A splitting theorem for the Medvedev and Muchnik lattices.
Mathematical Logic Quarterly, 49:327335, 2003.
 4

Stephen Binns.
Small classes.
Archive for Mathematical Logic, 45:393410, 2006.
 5

Stephen Binns.
Hyperimmunity in
.
Notre Dame Journal of Formal Logic, 48:293316, 2007.
 6

Stephen Binns and Stephen G. Simpson.
Embeddings into the Medvedev and Muchnik lattices of
classes.
Archive for Mathematical Logic, 43:399414, 2004.
 7

F. Blanchard, A. Maass, and A. Nogueira, editors.
Topics in Symbolic Dynamics and Applications (Temuco,
1997).
Number 279 in London Mathematical Society Lecture Note Series.
Cambridge University Press, 2000.
XVI + 245 pages.
 8

Mike Boyle.
Algebraic aspects of symbolic dynamics.
In [7], pages 5788, 2000.
 9

CCA 2007: Fourth International Conference on Computability and Complexity
in Analysis.
Informatik Berichte, Universität Hagen, 2007.
 10

Douglas Cenzer, S. Ali Dashti, and Jonathan L. F. King.
Effective symbolic dynamics.
In [9], pages 7989, 2007.
 11

Douglas Cenzer and Peter G. Hinman.
Density of the Medvedev lattice of classes.
Archive for Mathematical Logic, 42:583600, 2003.
 12

C.T. Chong, Q. Feng, T. A. Slaman, W. H. Woodin, and Y. Yang, editors.
Computational Prospects of Infinity: Proceedings of the
Logic Workshop at the Institute for Mathematical Sciences, June 20
 August 15, 2005, Part II: Presented Talks.
Number 15 in Lecture Notes Series, Institute for Mathematical
Sciences, National University of Singapore. World Scientific, 2008.
432 pages.
 13

Joshua A. Cole and Stephen G. Simpson.
Mass problems and hyperarithmeticity.
Journal of Mathematical Logic, 7:125143, 2008.
 14

COMPTHY email list.
http://listserv.nd.edu/archives/compthy.html, September 1995 to the
present.
 15

Martin Davis.
Computability and Unsolvability.
Dover Publications, New York, 1982.
XXV + 248 pages.
 16

Rodney G. Downey and Denis R. Hirschfeldt.
Algorithmic Randomness and Complexity.
Theory and Applications of Computability. SpringerVerlag, 2010.
XXVIII + 855 pages.
 17

FOCS 2002: The 43rd Annual IEEE Symposium on Foundations of
Computer Science.
IEEE Computer Society, 2002.
XII + 811 pages.
 18

FOM email list.
http://www.cs.nyu.edu/mailman/listinfo/fom/.
September 1997 to the present.
 19

William Hanf.
Nonrecursive tilings of the plane, I.
Journal of Symbolic Logic, 39:283285, 1974.
 20

Michael Hochman and Tom Meyerovitch.
A characterization of the entropies of multidimensional shifts of
finite type.
Annals of Mathematics, 171:20112038, 2010.
 21

Phil Hudelson.
Mass problems and initial segment complexity.
2010.
20 pages, submitted for publication.
 22

Leonid A. Levin.
Forbidden information.
In [17], pages 761768, 2002.
 23

Douglas Lind and Brian Marcus.
An Introduction to Symbolic Dynamics and Coding.
Cambridge University Press, 1995.
XVI + 495 pages.
 24

Yuri T. Medvedev.
Degrees of difficulty of mass problems.
Doklady Akademii Nauk SSSR, n.s., 104:501504, 1955.
In Russian.
 25

Joseph S. Miller.
Extracting information is hard: a Turing degree of nonintegral
effective Hausdorff dimension.
Advances in Mathematics, 226:373384, 2011.
 26

Joseph S. Miller.
Two notes on subshifts.
Proceedings of the American Mathematical Society,
140(5):16171622, 2012.
 27

Shahar Mozes.
Tilings, substitution systems, and the dynamical systems generated by
them.
Journal d'Analyse Mathématique, 53:139186, 1989.
 28

Shahar Mozes.
A zero entropy, mixing of all orders tiling system.
In [49], pages 319325, 1992.
 29

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

Dale Myers.
Nonrecursive tilings of the plane, II.
Journal of Symbolic Logic, 39:286294, 1974.
 31

André Nies.
Computability and Randomness.
Oxford University Press, 2009.
XV + 433 pages.
 32

Raphael M. Robinson.
Undecidability and nonperiodicity of tilings of the plane.
Inventiones Mathematicae, 12:177209, 1971.
 33

Hartley Rogers, Jr.
Theory of Recursive Functions and Effective
Computability.
McGrawHill, 1967.
XIX + 482 pages.
 34

S. G. Simpson, editor.
Reverse Mathematics 2001.
Number 21 in Lecture Notes in Logic. Association for Symbolic
Logic, 2005.
X + 401 pages.
 35

Stephen G. Simpson.
FOM: natural r.e. degrees; Pi01 classes.
FOM email list [18], 13 August 1999.
 36

Stephen G. Simpson.
FOM: priority arguments; Kleener.e. degrees; Pi01 classes.
FOM email list [18], 16 August 1999.
 37

Stephen G. Simpson.
Subsystems of Second Order Arithmetic.
Perspectives in Mathematical Logic. SpringerVerlag, 1999.
XIV + 445 pages; Second Edition, Perspectives in Logic, Association
for Symbolic Logic, Cambridge University Press, 2009, XVI+ 444 pages.
 38

Stephen G. Simpson.
Medvedev degrees of nonempty Pi01 subsets of
2omega.
COMPTHY email list [14], 9 June 2000.
 39

Stephen G. Simpson.
FOM: natural r.e. degrees.
FOM email list [18], 27 February 2005.
 40

Stephen G. Simpson.
Mass problems and randomness.
Bulletin of Symbolic Logic, 11:127, 2005.
 41

Stephen G. Simpson.
sets and models of
.
In [34], pages 352378, 2005.
 42

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

Stephen G. Simpson.
Mass problems and almost everywhere domination.
Mathematical Logic Quarterly, 53:483492, 2007.
 44

Stephen G. Simpson.
Some fundamental issues concerning degrees of unsolvability.
In [12], pages 313332, 2008.
 45

Stephen G. Simpson.
Mass problems and measuretheoretic regularity.
Bulletin of Symbolic Logic, 15:385409, 2009.
 46

Stephen G. Simpson.
Mass problems associated with effectively closed sets.
Tohoku Mathematical Journal, 63(4):489517, 2011.
 47

Stephen G. Simpson.
Symbolic dynamics: entropy = dimension = complexity.
2011.
Preprint, 19 pages, submitted for publication.
 48

Robert I. Soare.
Recursively Enumerable Sets and Degrees.
Perspectives in Mathematical Logic. SpringerVerlag, 1987.
XVIII + 437 pages.
 49

P. Walters, editor.
Symbolic Dynamics and its Applications.
Number 135 in Contemporary Mathematics. American Mathematical
Society, 1992.
XVI + 451 pages.
 50

Hao Wang.
Proving theorems by pattern recognition, II.
Bell System Technical Journal, 40:142, 1961.
Medvedev degrees of
2dimensional subshifts of finite type
This document was generated using the
LaTeX2HTML translator Version 2008 (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 2dim
The translation was initiated by Stephen G Simpson on 20120905
Footnotes
 ... Simpson^{1}
 The author's research was partially
supported by the United States National Science Foundation, grant
DMS0600823, and by the Cada and Susan Grove Mathematics
Enhancement Endowment at the Pennsylvania State University. In
addition, the author thanks Ali Dashti for telling him of the
results in Cenzer/Dashti/King [10], and Benjamin Weiss
for calling his attention to the papers of Hochman/Meyerovitch
[20] and Mozes [27], and the
referee for helpful remarks.
 ... morphism^{2}
 Note that a shift morphism need not
be onto . In this respect our terminology may differ from that
of other authors.
Stephen G Simpson
20120905