Medvedev degrees of
2-dimensional subshifts of finite type

Stephen G. Simpson¹

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 $X$ and $Y$ are said to be Medvedev equivalent if there exist partial computable functionals from $X$ into $Y$ and vice versa. The Medvedev degree of $X$ is the equivalence class of $X$ under Medvedev equivalence. There is an extensive recursion-theoretic literature on the lattices $\mathcal{E}_{\mathrm{s}}$ and $\mathcal{E}_{\mathrm{w}}$ of Medvedev degrees and Muchnik degrees of nonempty effectively closed subsets of $\{0,1\}^\mathbb{N}$. We now prove that $\mathcal{E}_{\mathrm{s}}$ and $\mathcal{E}_{\mathrm{w}}$ consist precisely of the Medvedev degrees and Muchnik degrees of 2-dimensional subshifts of finite type. We apply this result to obtain an infinite collection of 2-dimensional subshifts of finite type which are, in a certain sense, mutually incompatible.

Background

Definition 1.1   Let $A$ be a finite set of symbols. The full 2-dimensional shift on $A$ is the dynamical system consisting of the natural action of $\mathbb{Z}^2$ on the compact set $A^{\mathbb{Z}^2}$. A 2-dimensional subshift is a nonempty closed set $X\subseteq A^{\mathbb{Z}^2}$ which is invariant under the action of $\mathbb{Z}^2$. A 2-dimensional subshift $X$ is said to be of finite type if it is defined by a finite set of forbidden configurations. An interesting paper on 2-dimensional subshifts of finite type is Mozes [27]. A standard reference for the 1-dimensional case is the book of Lind/Marcus [23], which also includes an appendix [23, §13.10] on the 2-dimensional case.

Definition 1.2   If $X$ is a 2-dimensional subshift, the shift operators $S_1,S_2:X\to X$ are defined by $S_1(x)(m,n)=x(m+1,n)$ and $S_2(x)(m,n)=x(m,n+1)$ for all $x\in X$ and $(m,n)\in\mathbb{Z}^2$. If $X$ and $Y$ are 2-dimensional subshifts, a shift morphism² of $X$ into $Y$ is a continuous function $f:X\to Y$ which commutes with the shift operators, i.e., $f(S_1(x))=S_1(f(x))$ and $f(S_2(x))=S_2(f(x))$ for all $x\in X$. It follows that $f$ commutes with the action of $\mathbb{Z}^2$ on $X$ and $Y$. A shift isomorphism of $X$ onto $Y$ is a shift morphism of $X$ one-to-one onto $Y$, i.e., a homeomorphism of $X$ onto $Y$ which commutes with $S_1$ and $S_2$. We say that $X$ and $Y$ are shift isomorphic if there exists a shift isomorphism of $X$ onto $Y$.

Remark 1.3   In the study of 2-dimensional 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 $F$ is a finite set of Wang tiles, let $T_F$ be the set of tilings of the plane by $F$. Identifying $T_F$ as a subset of $F^{\mathbb{Z}^2}$, it is clear that $T_F$ is a 2-dimensional subshift of finite type. Conversely, given a 2-dimensional subshift of finite type, $X$, it is easy to construct a finite set of Wang tiles, $F$, such that $T_F$ is computably isomorphic to $X$. Namely, let $r$ be a positive integer which is greater than or equal to the diameters of all of the forbidden configurations defining $X$, and let $F\subseteq A^{\{1,\ldots,r\}^2}$ be the set of $r\times r$ configurations which do not contain any of the forbidden configurations. Our isomorphism of $X$ onto $T_F$ associates to each point $x\in X$ a tiling $t\in T_F$ defined by $t(m,n)(i,j)=x(m+i,n+j)$ for all $(m,n)\in\mathbb{Z}^2$ and $(i,j)\in\{1,\ldots,r\}^2$. The adjacency rules for $\tau_1,\tau_2\in F$ are: (a) $\tau_1$ is allowed to occur immediately to the left of $\tau_2$ if and only if $\tau_1(i+1,j)=\tau_2(i,j)$ for all $1\le i\le r-1$ and $1\le j\le r$, and (b) $\tau_1$ is allowed to occur immediately below $\tau_2$ if and only if $\tau_1(i,j+1)=\tau_2(i,j)$ for all $1\le i\le r$ and $1\le j\le r-1$.

Mozes [27,28] and recently Hochman/Meyerovitch [20] have used the tiling methods of Wang [50] and Robinson [32] to construct 2-dimensional subshifts of finite type with interesting dynamical properties.

Remark 1.4   In this paper we shall examine 2-dimensional 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 recursion-theoretic concepts which we shall need in §§2 and 3 below.

Definition 1.5 (Turing oracles)  

1. Let $\mathbb{N}=\{1,2,\ldots\}$ be the set of positive integers. Let $A=\{a_1,\ldots,a_k\}$ be a finite set of symbols. Let $A^\mathbb{N}=\{x\mid x:\mathbb{N}\to A\}$ be the space of all functions from $\mathbb{N}$ into $A$. We endow $A$ with the discrete topology and $A^\mathbb{N}$ with the product topology.
2. Let $M$ be a deterministic Turing machine program with tape symbols $a_1,\ldots,a_k,0,1,b$. Here $b$ is a blank symbol, and we assume that $A\cap\{0,1,b\}=\emptyset$. Given $x\in A^\mathbb{N}$ and $n\in\mathbb{N}$, we denote by $M(x,n)$ the output of the unique run of $M$ with oracle $x$ and input $n$ provided this run eventually halts. More precisely, $M(x,n)=a$ means that the program $M$, starting in its initial state with $x$ inscribed using elements of $A$ at tape positions $-1,-2,-3,\ldots$ and $n$ inscribed in binary notation using $0$'s and $1$'s at tape positions $0,1,2,\ldots,j$ and blanks at tape positions $j+1,j+2,\ldots$ where $2^j\le n<2^{j+1}$, runs for a finite number of deterministic computational steps and then reaches a halting state with the symbol $a$ at tape position $0$. For a fuller explanation of Turing's oracle concept, see Davis [15] and Rogers [33, Chapter 9].

Definition 1.6 (Medvedev and Muchnik degrees)  

1. Let $\Phi:{\subseteq}A^\mathbb{N}\to A^\mathbb{N}$ be a partial functional from $A^\mathbb{N}$ into $A^\mathbb{N}$, i.e., a function whose domain and range are subsets of $A^\mathbb{N}$. The domain of $\Phi$ is denoted $\mathrm{dom}(\Phi)$. We say that $\Phi$ is partial recursive (see Rogers [33, §15.3]) or partial computable if there exists a deterministic Turing machine program $M$ which computes $\Phi$ in the following sense: for all $x\in A^\mathbb{N}$ we have $x\in\mathrm{dom}(\Phi)$ if and only if for all $n\in\mathbb{N}$ there exists $a\in A$ such that $M(x,n)=a$, in which case $\Phi(x)(n)=a$. Note that each partial computable functional $\Phi:{\subseteq}A^\mathbb{N}\to A^\mathbb{N}$ is continuous on its domain.
2. Let $X$ and $Y$ be subsets of $A^\mathbb{N}$. We say that $X$ and $Y$ are computably homeomorphic if there exist partial computable functionals $\Phi,\Psi:{\subseteq}A^\mathbb{N}\to A^\mathbb{N}$ such that $X\subseteq\mathrm{dom}(\Phi)$ and $Y\subseteq\mathrm{dom}(\Psi)$ and $\Phi$ maps $X$ one-to-one onto $Y$ and $\Psi(\Phi(x))=x$ for all $x\in X$.
3. We say that $Y$ is Medvedev reducible to $X$ (see Rogers [33, §13.7] and Medvedev [24]) if there exists a partial computable functional $\Phi:{\subseteq}A^\mathbb{N}\to A^\mathbb{N}$ such that $X\subseteq\mathrm{dom}(\Phi)$ and $\Phi(x)\in Y$ for all $x\in X$. We say that $X$ and $Y$ are Medvedev equivalent if $X$ is Medvedev reducible to $Y$ and $Y$ is Medvedev reducible to $Y$.
4. We say that $Y$ is Muchnik reducible to $X$ (see Muchnik [29]) if for each $x\in X$ there exists a partial computable functional $\Phi$ such that $x\in\mathrm{dom}(\Phi)$ and $\Phi(x)\in Y$. We say that $X$ and $Y$ are Muchnik equivalent if $X$ is Muchnik reducible to $Y$ and $Y$ is Muchnik reducible to $X$.
5. Obviously computable homeomorphism implies Medvedev equivalence, and Medvedev equivalence implies Muchnik equivalence. However, the converses do not hold. The equivalence classes under Medvedev equivalence and Muchnik equivalence are known as Medvedev degrees and Muchnik degrees respectively.

Remark 1.7   The idea behind Medvedev and Muchnik degrees is to regard each set $X\subseteq A^\mathbb{N}$ as the solution set of a so-called ``mass problem,'' $\mathrm{prob}(X)$, the problem of finding at one least element of $X$, where ``to find'' means ``to compute in the sense of Turing.'' Accordingly, one says that the problem $\mathrm{prob}(X)$ is ``solvable'' if it has at least one computable solution, i.e., the set $X$ contains at least one point which is Turing computable. Similarly, one could say that $\mathrm{prob}(Y)$ is ``reducible'' to $\mathrm{prob}(X)$ if each solution of $\mathrm{prob}(X)$ can be used as a Turing oracle to compute at least one solution of $\mathrm{prob}(Y)$, or in other words, $Y$ is Muchnik reducible to $X$. Thus for instance $\mathrm{prob}(X)$ is solvable if and only if $X$ is Muchnik reducible to $Y$ for all $Y$, if and only if $X$ is Medvedev reducible to $Y$ for all $Y$. 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 $\vert A\vert\ge2$ it is straightforward to construct a computable homeomorphism of $A^\mathbb{N}$ onto $\{0,1\}^\mathbb{N}$. Therefore, the Medvedev degrees and Muchnik degrees of subsets of $A^\mathbb{N}$ are the same as those of subsets of $\{0,1\}^\mathbb{N}$.

Definition 1.9 (effectively closed sets)  

1. A subset of $A^\mathbb{N}$ is said to be effectively closed or $\Pi^0_1$ (see Rogers [33, Chapter 15]) if it is the complement of the union of a computable sequence of basic open neighborhoods in $A^\mathbb{N}$. Equivalently, $X\subseteq A^\mathbb{N}$ is effectively closed if there exists a deterministic Turing machine program $M$ such that for all $x\in A^\mathbb{N}$, $x\in X$ if and only if $M(x,1)$ never halts.
2. In view of Remark 1.8, each effectively closed set $X\subseteq A^\mathbb{N}$ is computably homeomorphic to an effectively closed set $P\subseteq\{0,1\}^\mathbb{N}$. It follows that $P$ has the same Medvedev degree as $X$ and the same Muchnik degree as $X$.
3. Let $\mathcal{E}_{\mathrm{s}}$ (respectively $\mathcal{E}_{\mathrm{w}}$) be the partial ordering of Medvedev degrees (respectively Muchnik degrees) of nonempty effectively closed subsets of $\{0,1\}^\mathbb{N}$. Here the partial ordering of $\mathcal{E}_{\mathrm{s}}$ is given by defining the Medvedev degree of $P\subseteq\{0,1\}^\mathbb{N}$ to be $\le$ the Medvedev degree of $Q\subseteq\{0,1\}^\mathbb{N}$ if and only if $P$ is Medvedev reducible to $Q$, and similarly for $\mathcal{E}_{\mathrm{w}}$.
4. The partial orderings $\mathcal{E}_{\mathrm{s}}$ and $\mathcal{E}_{\mathrm{w}}$ have the same bottom element, namely, the equivalence class consisting of all subsets of $\{0,1\}^\mathbb{N}$ which contain at least one computable point. The common bottom element of $\mathcal{E}_{\mathrm{s}}$ and $\mathcal{E}_{\mathrm{w}}$ is denoted $\mathbf{0}$.

Remark 1.10 (the lattices $\mathcal{E}_{\mathrm{s}}$ and $\mathcal{E}_{\mathrm{w}}$)  

1. The partial orderings $\mathcal{E}_{\mathrm{s}}$ and $\mathcal{E}_{\mathrm{w}}$ in Definition 1.9 are distributive lattices. Moreover, there is a natural lattice homomorphism of $\mathcal{E}_{\mathrm{s}}$ onto $\mathcal{E}_{\mathrm{w}}$ obtained by mapping the Medvedev degree of $P$ to the Muchnik degree of $P$.
2. The lattices $\mathcal{E}_{\mathrm{s}}$ and $\mathcal{E}_{\mathrm{w}}$ 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 $A^\mathbb{N}$ but also to subsets of $A^{\mathbb{Z}^2}$. In order to do this, we shall use a simple one-to-one correspondence between $\mathbb{Z}^2$ and $\mathbb{N}$. For instance, let $\theta:\mathbb{Z}^2\to\mathbb{N}$ be the one-to-one correspondence given by

$$\theta(m,n)=\frac{(\phi(m)+\phi(n)-1)(\phi(m)+\phi(n)-2)}2+\phi(m)$$

where

$$\phi(m)=\left\{ \begin{array}{ll} 2m & \hbox{if }m>0, [4pt] 1-2m & \hbox{if }m\le0. \end{array} \right.$$

We may then identify subsets of $A^{\mathbb{Z}^2}$ with corresponding subsets of $A^\mathbb{N}$. In this way Definitions 1.6 and 1.9 and Remarks 1.7, 1.8 and 1.10 for subsets of $A^\mathbb{N}$ apply equally well to subsets of $A^{\mathbb{Z}^2}$.

Remark 1.12   Recent research has revealed that $\mathcal{E}_{\mathrm{w}}$ 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 $\mathcal{E}_{\mathrm{w}}$ is the Muchnik degree of the problem of finding a complete, consistent theory which contains the usual axioms for first-order arithmetic. Another interesting degree in $\mathcal{E}_{\mathrm{w}}$ is the Muchnik degree of the problem of finding an infinite sequence of $0$'s and $1$'s which is algorithmically random in the sense of Martin-Löf [40,42]. Other interesting degrees in $\mathcal{E}_{\mathrm{w}}$ are closely related to other interesting topics in the foundations of mathematics. Among these topics are reverse mathematics [37,40], almost everywhere domination [43], measure-theoretic 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 $X$ be a 2-dimensional subshift. In the following theorem we see that the Medvedev degree of $X$, the Muchnik degree of $X$, and the computable homeomorphism type of $X$ depend only on the shift isomorphism type of $X$. This suggests the possibility that Medvedev degrees, Muchnik degrees, and computable homeomorphism types may be useful as invariants for the problem of classifying 2-dimensional 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 $f:X\to Y$ are given by partial computable functionals. If $X$ and $Y$ are shift isomorphic, then $X$ and $Y$ are computably homeomorphic, hence Medvedev equivalent, hence Muchnik equivalent.

Proof.Let $A$ and $B$ be finite sets of symbols such that $X$ and $Y$ are subshifts of the full 2-dimensional shifts $A^{\mathbb{Z}^2}$ and $B^{\mathbb{Z}^2}$ respectively. Let $f:X\to Y$ be a shift morphism. By the Curtis/Hedlund/Lyndon Theorem (see Boyle [8] or Lind/Marcus [23]) $f$ is a block code, i.e., we can find an integer $r\ge0$ and a projection $\pi:A^{\{-r,\ldots,r\}^2}\to B$ such that

$f(x)(m,n)=\pi(S_1^mS_2^n(x)\upharpoonright \{-r,\ldots,r\}^2)$

for all $x\in X$ and $(m,n)\in\mathbb{Z}^2$. In particular $f$ is given by a partial computable functional. If moreover $f$ is a shift isomorphism of $X$ onto $Y$, it follows that $f$ is a computable homeomorphism of $X$ onto $Y$. This completes the proof.$\Box$

Remark 2.3   Let $X$ be a 2-dimensional subshift. If $X$ contains a periodic point, one can easily show (see for instance the second and third paragraphs of [32, §1]) that $X$ contains a point which is Turing computable, so by part 4 of Definition 1.9 the Medvedev degree of $X$ is $\mathbf{0}$, 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 2-dimensional 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 2-dimensional subshifts of finite type. Clearly any 2-dimensional subshift of finite type is an effectively closed subset of $A^{\mathbb{Z}^2}$ and is therefore computably homeomorphic to, hence of the same Medvedev degree and Muchnik degree as, a nonempty effectively closed subset of $\{0,1\}^\mathbb{N}$. We shall now prove a theorem in the opposite direction. Namely, every nonempty effectively closed subset of $\{0,1\}^\mathbb{N}$ is of the same Medvedev degree, hence of the same Muchnik degree, as some 2-dimensional subshift of finite type. This characterization of the Medvedev degrees and Muchnik degrees of 2-dimensional subshifts of finite type appears to be new, but see Remark 2.7 below.

Theorem 2.5   Given a nonempty effectively closed set $P\subseteq\{0,1\}^\mathbb{N}$, we can find a 2-dimensional subshift of finite type which is of the same Medvedev degree as $P$, hence of the same Muchnik degree as $P$.

Proof.Our proof uses the tiling constructions of Robinson [32] and Hanf [19] and Myers [30].

Let $F$ be a finite set of Wang tiles, and let $\tau\in F$ be a distinguished tile in $F$. We write $T_F^\tau=\{t\in T_F\mid t(0,0)=\tau\}$. The tilings in $T_F^\tau$ are said to be origin-constrained. Given an effectively closed set $P\subseteq\{0,1\}^\mathbb{N}$, Hanf [19] shows how to construct an origin-constrained tiling system $F,\tau$ and a projection $\pi:F\to\{0,1\}$ such that

$P=\{\langle\pi(t(n,0))\mid n\in\mathbb{N}\rangle\mid t\in T_F^\tau\}$.

Namely, $F$ and $\tau$ are such that each origin-constrained tiling $t\in T_F^\tau$ describes a non-halting run of a particular deterministic Turing machine $M$ program starting with

$\langle\pi(t(-n,0))\mid n\in\mathbb{N}\rangle\in\{0,1\}^\mathbb{N}$

inscribed at positions $-1,-2,-3,\ldots$ of the Turing machine tape. The distinguished tile $\tau$ represents the initial internal state of $M$. We can then construct a fixed partial computable functional $\Phi:{\subseteq}\{0,1\}^\mathbb{N}\to F^{\mathbb{Z}^2}$ which is independent of $t$ and maps $\langle\pi(t(-n,0))\mid n\in\mathbb{N}\rangle$ to $t$. Thus $T_F^\tau$ and $P$ are computably homeomorphic.

Now, starting with $F$ and $\tau$ as above, Myers [30] shows how to construct a finite set of tiles $F'$ and a projection $\pi':F'\to F$ with the following properties:

1. $F'$ is a Robinson set of tiles.

   (Unexplained terms are defined in Myers' paper [30].)

2. For each tiling $t'\in T_{F'}$, the $\pi'$-images of the center rows of the finite boards of $t'$ are synchronized.
3. For each tiling $t'\in T_{F'}$, the result of piecing together the $\pi'$-images of the center rows of the finite boards of $t'$ is $\langle t(n,0)\mid n\in\mathbb{Z}\rangle$ for some $t\in T_F^\tau$. Using this piecing-together procedure, we can construct a fixed computable functional which maps $t'$ to $t$.
4. Given an origin-constrained tiling $t\in T_F^\tau$, we can find a (nonunique) tiling $t'\in T_{F'}$ such that $\langle t(n,0)\mid n\in\mathbb{Z}\rangle$ is the result of piecing together the $\pi'$-images of the center rows of the finite boards of $t'$. Moreover, we can construct a fixed partial computable functional which maps $t$ to such a $t'$.

Properties 3 and 4 imply that $T_{F'}$ is Medvedev equivalent to $T_F^\tau$. Therefore, $T_{F'}$ is Medvedev equivalent to $P$. Since $T_{F'}$ is a 2-dimensional subshift of finite type, our theorem is proved.$\Box$

Remark 2.6   Actually Hanf [19] and Myers [30] dealt only with effectively closed sets $P\subseteq\{0,1\}^\mathbb{N}$ of the form

$P=S(I,J)=\{x\in\{0,1\}^\mathbb{N}\mid x$ separates $I,J\}$ where $I$ and $J$ are recursively enumerable subsets of $\mathbb{N}$. However, their constructions work just as well for arbitrary effectively closed sets $P\subseteq\{0,1\}^\mathbb{N}$.

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 2-adic coordinate system.

Definition 2.8   Let $\mathcal{S}^2$ be the set of all 2-dimensional subshifts. For $X,Y\in\mathcal{S}^2$ we write $X\ge Y$ if there exists a shift morphism $f:X\to Y$. Obviously $\ge$ is transitive and reflexive. We write $X\equiv Y$ if $X\ge Y$ and $Y\ge X$. Obviously $\equiv$ is an equivalence relation on $\mathcal{S}^2$. Obviously $X\equiv Y$ whenever $X$ and $Y$ are shift isomorphic, but the converse does not hold. Let $\mathcal{S}^2/{\equiv}$ be the set of equivalence classes of $\mathcal{S}^2$ modulo $\equiv$. There is an obvious partial ordering of $\mathcal{S}^2/{\equiv}$ induced by $\ge$. It is easy to verify that, under this partial ordering, $\mathcal{S}^2/{\equiv}$ is a distributive lattice. Let $\mathcal{S}^2_{\mathrm{fin}}$ be the subset of $\mathcal{S}^2$ consisting of the 2-dimensional subshifts of finite type. It is easy to verify that $\mathcal{S}^2_{\mathrm{fin}}/{\equiv}$ is a sublattice of $\mathcal{S}^2/{\equiv}$.

Theorem 2.9   There is a natural lattice homomorphism of $\mathcal{S}^2_{\mathrm{fin}}/{\equiv}$ onto $\mathcal{E}_{\mathrm{s}}$. Namely, for each $X\in\mathcal{S}^2_{\mathrm{fin}}$ we map the $\equiv$-equivalence class of $X$ to the Medvedev degree of $X$.

Proof.The greatest lower bound and least upper bound operations in each of the lattices $\mathcal{S}^2/{\equiv}$, $\mathcal{S}^2_{\mathrm{fin}}/{\equiv}$, $\mathcal{E}_{\mathrm{s}}$, $\mathcal{E}_{\mathrm{w}}$ are given by disjoint union and Cartesian product respectively. In particular, our mapping of $\mathcal{S}^2_{\mathrm{fin}}/{\equiv}$ to $\mathcal{E}_{\mathrm{s}}$ is a lattice homomorphism. By Theorem 2.5 this homomorphism is onto $\mathcal{E}_{\mathrm{s}}$.$\Box$

Remark 2.10   A consequence of Theorem 2.9 is that there is a natural lattice homomorphism of $\mathcal{S}^2_{\mathrm{fin}}/{\equiv}$ onto $\mathcal{E}_{\mathrm{w}}$, obtained by mapping the $\equiv$-equivalence class of $X\in\mathcal{S}^2_{\mathrm{fin}}$ to the Muchnik degree of $X$. In particular we have a new invariant, the Muchnik degree, associated to (shift isomorphism types of) 2-dimensional 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 $\mathcal{E}_{\mathrm{w}}$ 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 2-dimensional subshifts, with no reference to Medvedev degrees or Muchnik degrees. Namely, we shall construct an infinite collection of 2-dimensional subshifts of finite type which are, in a certain sense, mutually incompatible.

Definition 3.2   If $X$ and $Y$ are 2-dimensional subshifts on $k$ and $l$ symbols respectively, let $X+Y$ and $X\times Y$ be the disjoint union and Cartesian product of $X$ and $Y$. These are 2-dimensional subshifts on $k+l$ and $kl$ symbols respectively. If $X=(X,S_1,S_2)$ is a 2-dimensional subshift on $k$ symbols, and if $a,b,c,d$ are integers such that $ad-bc\ne0$, let $X[a,b,c,d]=(X,S_1^aS_2^b,S_1^cS_2^d)$. This is a 2-dimensional subshift on $k^{\vert ad-bc\vert}$ symbols.

Definition 3.3   If $\mathcal{U}$ is a collection of 2-dimensional subshifts, let $\mathrm{cl}(\mathcal{U})$ be the closure of $\mathcal{U}$ under the operations of Definition 3.2. In other words, $\mathrm{cl}(\mathcal{U})$ is the smallest collection of 2-dimensional subshifts with the following properties:

1. For all $X\in\mathcal{U}$, $X\in\mathrm{cl}(\mathcal{U})$.
2. For all $X\in\mathrm{cl}(\mathcal{U})$ and $Y\in\mathrm{cl}(\mathcal{U})$, $X+Y\in\mathrm{cl}(\mathcal{U})$ and $X\times Y\in\mathrm{cl}(\mathcal{U})$.
3. For all $X\in\mathrm{cl}(\mathcal{U})$ and all $a,b,c,d\in\mathbb{Z}$ with $ad-bc\ne0$, $X[a,b,c,d]\in\mathrm{cl}(\mathcal{U})$.

Theorem 3.4   We can find an infinite collection of 2-dimensional subshifts of finite type, $\mathcal{W}$, such that for all partitions of $\mathcal{W}$ into two subcollections, $\mathcal{U}$ and $\mathcal{V}$, there is no shift morphism of $X$ into $Y$ for any $X\in\mathrm{cl}(\mathcal{U})$ and $Y\in\mathrm{cl}(\mathcal{V})$.

Proof.By Binns/Simpson [6] let $P_i$, $i=1,2,\ldots$, be nonempty effectively closed subsets of $\{0,1\}^\mathbb{N}$ whose Muchnik degrees are independent, i.e., $P_{i_i}+\cdots+P_{i_m}$ is not Muchnik reducible to $P_{j_1}\times\cdots\times P_{j_n}$ provided $\{i_1,\ldots,i_m\}\cap\{j_1,\ldots,j_n\}=\emptyset$. By Theorem 2.5, for each $i=1,2,\ldots$ let $X_i$ be a 2-dimensional subshift of finite type which is Medvedev equivalent, to $P_i$, hence Muchnik equivalent to $P_i$. Let $\mathcal{W}$ be the collection $X_i$, $i=1,2,\ldots$, and let $\mathcal{U},\mathcal{V}$ be a partition of $\mathcal{W}$. By induction on $X\in\mathrm{cl}(\mathcal{U})$ and $Y\in\mathrm{cl}(\mathcal{V})$ we can easily show that neither of $X$ and $Y$ is Muchnik reducible to the other. Hence by Theorem 2.2 there is no shift morphism of $X$ into $Y$ or vice versa. Q.E.D.$\Box$

Remark 3.5   In our proof of Theorem 3.4, all of the subshifts in $\mathcal{W}$ 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 $\mathbf{0}$. Namely, for each prime number $p$ choose an almost one-to-one extension of the $p$-adic odometer.

Remark 3.6   In this paper we have dealt only with 2-dimensional subshifts. What about the 1-dimensional 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 1-dimensional 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 1-dimensional subshifts? Cenzer/Dashti/King [10] have constructed a 1-dimensional 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 1-dimensional effectively closed subshifts. And from this plus Binns/Simpson [6] it follows that Theorem 3.4 holds in the same context.

Bibliography

1

Christopher Alfeld.
Non-branching degrees in the Medvedev lattice of $\Pi^0_1$ classes.
Journal of Symbolic Logic, 72:81-97, 2007.

2

Stephen Binns.
The Medvedev and Muchnik Lattices of $\Pi^0_1$ 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:327-335, 2003.

4

Stephen Binns.
Small $\Pi^0_1$ classes.
Archive for Mathematical Logic, 45:393-410, 2006.

5

Stephen Binns.
Hyperimmunity in $2^{\mathbb{N}}$.
Notre Dame Journal of Formal Logic, 48:293-316, 2007.

6

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.

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 57-88, 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 79-89, 2007.

11

Douglas Cenzer and Peter G. Hinman.
Density of the Medvedev lattice of $\Pi^0_1$ classes.
Archive for Mathematical Logic, 42:583-600, 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:125-143, 2008.

14

COMP-THY e-mail list.
http://listserv.nd.edu/archives/comp-thy.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. Springer-Verlag, 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 e-mail 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:283-285, 1974.

20

Michael Hochman and Tom Meyerovitch.
A characterization of the entropies of multidimensional shifts of finite type.
Annals of Mathematics, 171:2011-2038, 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 761-768, 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:501-504, 1955.
In Russian.

25

Joseph S. Miller.
Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension.
Advances in Mathematics, 226:373-384, 2011.

26

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

27

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

28

Shahar Mozes.
A zero entropy, mixing of all orders tiling system.
In [49], pages 319-325, 1992.

29

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

30

Dale Myers.
Nonrecursive tilings of the plane, II.
Journal of Symbolic Logic, 39:286-294, 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:177-209, 1971.

33

Hartley Rogers, Jr.
Theory of Recursive Functions and Effective Computability.
McGraw-Hill, 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 e-mail list [18], 13 August 1999.

36

Stephen G. Simpson.
FOM: priority arguments; Kleene-r.e. degrees; Pi01 classes.
FOM e-mail list [18], 16 August 1999.

37

Stephen G. Simpson.
Subsystems of Second Order Arithmetic.
Perspectives in Mathematical Logic. Springer-Verlag, 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 Pi$\verb\vert^\vert$0$\verb\vert _\vert$1 subsets of 2$\verb\vert^\vert$omega.
COMP-THY e-mail list [14], 9 June 2000.

39

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

40

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

41

Stephen G. Simpson.
$\Pi^0_1$ sets and models of $\mathsf{WKL}_0$.
In [34], pages 352-378, 2005.

42

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

43

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

44

Stephen G. Simpson.
Some fundamental issues concerning degrees of unsolvability.
In [12], pages 313-332, 2008.

45

Stephen G. Simpson.
Mass problems and measure-theoretic regularity.
Bulletin of Symbolic Logic, 15:385-409, 2009.

46

Stephen G. Simpson.
Mass problems associated with effectively closed sets.
Tohoku Mathematical Journal, 63(4):489-517, 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. Springer-Verlag, 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:1-42, 1961.

About this document ...

Medvedev degrees of
2-dimensional 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 2012-09-05

Footnotes

... Simpson¹

The author's research was partially supported by the United States National Science Foundation, grant DMS-0600823, 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²

Note that a shift morphism $f:X\to Y$ need not be onto $Y$. In this respect our terminology may differ from that of other authors.