# Medvedev degrees of 2-dimensional subshifts of finite type

Stephen G. Simpson1

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 recursion-theoretic 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 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 be a finite set of symbols. The full 2-dimensional shift on is the dynamical system consisting of the natural action of on the compact set . A 2-dimensional subshift is a nonempty closed set which is invariant under the action of . A 2-dimensional subshift 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 is a 2-dimensional subshift, the shift operators are defined by and for all and . If and are 2-dimensional subshifts, a shift morphism2 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 one-to-one 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 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 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 2-dimensional subshift of finite type. Conversely, given a 2-dimensional 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 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 be the set of positive integers. Let be a finite set of symbols. Let be the space of all functions from into . We endow with the discrete topology and with the product topology.
2. Let be a deterministic Turing machine program with tape symbols . Here is a blank symbol, and we assume that . Given and , we denote by the output of the unique run of with oracle and input provided this run eventually halts. More precisely, means that the program , starting in its initial state with inscribed using elements of at tape positions and inscribed in binary notation using 's and 's at tape positions and blanks at tape positions where , runs for a finite number of deterministic computational steps and then reaches a halting state with the symbol at tape position . 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 be a partial functional from into , i.e., a function whose domain and range are subsets of . The domain of is denoted . We say that is partial recursive (see Rogers [33, §15.3]) or partial computable if there exists a deterministic Turing machine program which computes in the following sense: for all we have if and only if for all there exists such that , in which case . Note that each partial computable functional is continuous on its domain.
2. Let and be subsets of . We say that and are computably homeomorphic if there exist partial computable functionals such that and and maps one-to-one onto and for all .
3. We say that is Medvedev reducible to (see Rogers [33, §13.7] and Medvedev [24]) if there exists a partial computable functional such that and for all . We say that and are Medvedev equivalent if is Medvedev reducible to and is Medvedev reducible to .
4. We say that is Muchnik reducible to (see Muchnik [29]) if for each there exists a partial computable functional such that and . We say that and are Muchnik equivalent if is Muchnik reducible to and is Muchnik reducible to .
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 as the solution set of a so-called 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 .

Definition 1.9 (effectively closed sets)
1. A subset of is said to be effectively closed or (see Rogers [33, Chapter 15]) if it is the complement of the union of a computable sequence of basic open neighborhoods in . Equivalently, is effectively closed if there exists a deterministic Turing machine program such that for all , if and only if never halts.
2. In view of Remark 1.8, each effectively closed set is computably homeomorphic to an effectively closed set . It follows that has the same Medvedev degree as and the same Muchnik degree as .
3. Let (respectively ) be the partial ordering of Medvedev degrees (respectively Muchnik degrees) of nonempty effectively closed subsets of . Here the partial ordering of is given by defining the Medvedev degree of to be the Medvedev degree of if and only if is Medvedev reducible to , and similarly for .
4. The partial orderings and have the same bottom element, namely, the equivalence class consisting of all subsets of which contain at least one computable point. The common bottom element of and is denoted .

Remark 1.10 (the lattices and )
1. 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 .
2. 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 one-to-one correspondence between and . For instance, let be the one-to-one 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 first-order 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 Martin-Lö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], 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 be a 2-dimensional 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 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 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 2-dimensional 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 2-dimensional 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 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 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 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 , we can find a 2-dimensional 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 origin-constrained. Given an effectively closed set , Hanf [19] shows how to construct an origin-constrained tiling system and a projection such that

.
Namely, and are such that each origin-constrained tiling describes a non-halting 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:

1. is a Robinson set of tiles.

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

2. For each tiling , the -images of the center rows of the finite boards of are synchronized.
3. For each tiling , the result of piecing together the -images of the center rows of the finite boards of is for some . Using this piecing-together procedure, we can construct a fixed computable functional which maps to .
4. Given an origin-constrained 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 2-dimensional 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 2-adic coordinate system.

Definition 2.8   Let be the set of all 2-dimensional 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 2-dimensional 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) 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 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 and are 2-dimensional subshifts on and symbols respectively, let and be the disjoint union and Cartesian product of and . These are 2-dimensional subshifts on and symbols respectively. If is a 2-dimensional subshift on symbols, and if are integers such that , let . This is a 2-dimensional subshift on symbols.

Definition 3.3   If is a collection of 2-dimensional subshifts, let be the closure of under the operations of Definition 3.2. In other words, is the smallest collection of 2-dimensional subshifts with the following properties:
1. For all , .
2. For all and , and .
3. For all and all with , .

Theorem 3.4   We can find an infinite collection of 2-dimensional 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 2-dimensional 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 one-to-one extension of the -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 classes.
Journal of Symbolic Logic, 72:81-97, 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:327-335, 2003.

4
Stephen Binns.
Small classes.
Archive for Mathematical Logic, 45:393-410, 2006.

5
Stephen Binns.
Hyperimmunity in .
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 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 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.
In Russian.

25
Joseph S. Miller.
Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension.

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 Pi01 subsets of 2omega.
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.
sets and models of .
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.

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

... Simpson1
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.
... morphism2
Note that a shift morphism need not be onto . In this respect our terminology may differ from that of other authors.

Stephen G Simpson 2012-09-05