Abstract
We show that the values of entropies of multidimensional shifts of finite type (SFTs) are characterized by a certain computation-theoretic property: a real number $h\geq0$ is the entropy of such an SFT if and only if it is right recursively enumerable, i.e. there is a computable sequence of rational numbers converging to $h$ from above. The same characterization holds for the entropies of sofic shifts. On the other hand, the entropy of strongly irreducible SFTs is computable.
-
[AW70] R. L. Adler and B. Weiss, Similarity of Automorphisms of the Torus, Providence, R.I.: Amer. Math. Soc., 1970, vol. 98.
@book {AW70, MRKEY = {0257315},
AUTHOR = {Adler, Roy L. and Weiss, Benjamin},
TITLE = {Similarity of Automorphisms of the Torus},
SERIES = {Mem. Amer. Math. Soc.},
VOLUME={98},
PUBLISHER = {Amer. Math. Soc.},
ADDRESS = {Providence, R.I.},
YEAR = {1970},
PAGES = {ii+43},
MRCLASS = {28.70},
MRNUMBER = {41 \#1966},
MRREVIEWER = {D. Newton},
ZBLNUMBER = {0195.06104},
} -
[B66] R. Berger, The Undecidability of the Domino Problem, Providence, RI: Amer. Math. Soc., 1966, vol. 66.
@book {B66, MRKEY = {0216954},
AUTHOR = {Berger, Robert},
TITLE = {The Undecidability of the Domino Problem},
SERIES = {Mem. Amer. Math. Soc. No.},
FJOURNAL = {Memoirs of the American Mathematical Society},
VOLUME = {66},
YEAR = {1966},
PUBLISHER={Amer. Math. Soc.},
ADDRESS={Providence, RI},
PAGES = {72},
ISSN = {0065-9266},
MRCLASS = {02.74},
MRNUMBER = {36 \#49},
MRREVIEWER = {J. R. B{ü}chi},
ZBLNUMBER = {0199.30802},
} -
[B78] R. Bowen, On Axiom A Diffeomorphisms, Reg. Conf. Series in Math., No. 35, Providence, R.I.: Amer. Math. Soc., 1978.
@book {B78, MRKEY = {0482842},
AUTHOR = {Bowen, Rufus},
TITLE = {On {A}xiom {A} Diffeomorphisms, Reg. Conf. Series in Math., {\rm No. 35}},
PUBLISHER = {Amer. Math. Soc.},
ADDRESS = {Providence, R.I.},
YEAR = {1978},
PAGES = {vii+45},
ISBN = {0-8218-1685-3},
MRCLASS = {58F15 (28A65)},
MRNUMBER = {58 \#2888},
MRREVIEWER = {L. A. Bunimovic},
ZBLNUMBER = {0383.58010},
} -
[burton94] R. Burton and J. E. Steif, "Non-uniqueness of measures of maximal entropy for subshifts of finite type," Ergodic Theory Dynam. Systems, vol. 14, iss. 2, pp. 213-235, 1994.
@article {burton94, MRKEY = {1279469},
AUTHOR = {Burton, Robert and Steif, Jeffrey E.},
TITLE = {Non-uniqueness of measures of maximal entropy for subshifts of finite type},
JOURNAL = {Ergodic Theory Dynam. Systems},
FJOURNAL = {Ergodic Theory and Dynamical Systems},
VOLUME = {14},
YEAR = {1994},
NUMBER = {2},
PAGES = {213--235},
ISSN = {0143-3857},
MRCLASS = {28D20 (22D40 54H20 82B20 82B26)},
MRNUMBER = {95f:28023},
MRREVIEWER = {Meir Smorodinsky},
ZBLNUMBER = {0807.58023},
} -
[CP75]
E. M. Coven and M. E. Paul, "Sofic systems," Israel J. Math., vol. 20, iss. 2, pp. 165-177, 1975.@article {CP75, MRKEY = {0383379},
AUTHOR = {Coven, Ethan M. and Paul, Michael E.},
TITLE = {Sofic systems},
JOURNAL = {Israel J. Math.},
FJOURNAL = {Israel Journal of Mathematics},
VOLUME = {20},
YEAR = {1975},
NUMBER = {2},
PAGES = {165--177},
ISSN = {0021-2172},
MRCLASS = {54H20},
MRNUMBER = {52 \#4260},
MRREVIEWER = {R. L. Adler},
DOI = {10.1007/BF02757884},
ZBLNUMBER = {0307.28015},
} -
[MCK76] M. Denker, C. Grillenberger, and K. Sigmund, Ergodic Theory on Compact Spaces, New York: Springer-Verlag, 1976, vol. 527.
@book {MCK76, MRKEY = {0457675},
AUTHOR = {Denker, Manfred and Grillenberger, Christian and Sigmund, Karl},
TITLE = {Ergodic Theory on Compact Spaces},
SERIES = {Lecture Notes in Math.},
VOLUME={527},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
YEAR = {1976},
PAGES = {iv+360},
MRCLASS = {28A65 (54H20)},
MRNUMBER = {56 \#15879},
MRREVIEWER = {W. Parry},
ZBLNUMBER = {0328.28008},
} -
[D06] A. Desai, "Subsystem entropy for $\Bbb Z^d$ sofic shifts," Indag. Math., vol. 17, iss. 3, pp. 353-359, 2006.
@article {D06, MRKEY = {2321105},
AUTHOR = {Desai, Angela},
TITLE = {Subsystem entropy for {$\Bbb Z\sp d$} sofic shifts},
JOURNAL = {Indag. Math.},
FJOURNAL = {Koninklijke Nederlandse Akademie van Wetenschappen. Indagationes Mathematicae. New Series},
VOLUME = {17},
YEAR = {2006},
NUMBER = {3},
PAGES = {353--359},
ISSN = {0019-3577},
MRCLASS = {37B10 (37B40)},
MRNUMBER = {2321105},
DOI = {10.1016/S0019-3577(06)80037-6},
ZBLNUMBER = {1104.37006},
} -
[FJ99] S. Forchhammer and J. Justesen, "Entropy bounds for constrained two-dimensional random fields," IEEE Trans. Inform. Theory, vol. 45, iss. 1, pp. 118-127, 1999.
@article {FJ99, MRKEY = {1677852},
AUTHOR = {Forchhammer, Søren and Justesen, Jørn},
TITLE = {Entropy bounds for constrained two-dimensional random fields},
JOURNAL = {{\rm IEEE} Trans. Inform. Theory},
FJOURNAL = {Institute of Electrical and Electronics Engineers. Transactions on Information Theory},
VOLUME = {45},
YEAR = {1999},
NUMBER = {1},
PAGES = {118--127},
ISSN = {0018-9448},
CODEN = {IETTAW},
MRCLASS = {94A29 (94A17)},
MRNUMBER = {99k:94023},
DOI = {10.1109/18.746776},
ZBLNUMBER = {0946.94011},
} -
[friedland97] S. Friedland, "On the entropy of $\Bbb Z^d$ subshifts of finite type," Linear Algebra Appl., vol. 252, pp. 199-220, 1997.
@article {friedland97, MRKEY = {1428636},
AUTHOR = {Friedland, Shmuel},
TITLE = {On the entropy of {$\bold Z\sp d$} subshifts of finite type},
JOURNAL = {Linear Algebra Appl.},
FJOURNAL = {Linear Algebra and its Applications},
VOLUME = {252},
YEAR = {1997},
PAGES = {199--220},
ISSN = {0024-3795},
CODEN = {LAAPAW},
MRCLASS = {54H20 (28D99 54C70 82B05)},
MRNUMBER = {98b:54052},
MRREVIEWER = {Manfred Denker},
DOI = {10.1016/0024-3795(95)00676-1},
ZBLNUMBER = {0893.54031},
} -
[F05] S. Friedland and U. N. Peled, "Theory of computation of multidimensional entropy with an application to the monomer-dimer problem," Adv. in Applied Math., vol. 34, iss. 3, pp. 486-522, 2005.
@article {F05, MRKEY = {2123547},
AUTHOR = {Friedland, Shmuel and Peled, Uri N.},
TITLE = {Theory of computation of multidimensional entropy with an application to the monomer-dimer problem},
JOURNAL = {Adv. in Applied Math.},
FJOURNAL = {Advances in Applied Mathematics},
VOLUME = {34},
YEAR = {2005},
NUMBER = {3},
PAGES = {486--522},
ISSN = {0196-8858},
MRCLASS = {82B20 (05B45)},
MRNUMBER = {2005m:82020},
MRREVIEWER = {Andr{á}s Kr{á}mli},
DOI = {10.1016/j.aam.2004.08.005},
ZBLNUMBER = {1076.82009},
} -
[GS98] C. Goodman-Strauss, "Matching rules and substitution tilings," Ann. of Math., vol. 147, iss. 1, pp. 181-223, 1998.
@article {GS98, MRKEY = {1609510},
AUTHOR = {Goodman-Strauss, Chaim},
TITLE = {Matching rules and substitution tilings},
JOURNAL = {Ann. of Math.},
FJOURNAL = {Annals of Mathematics. Second Series},
VOLUME = {147},
YEAR = {1998},
NUMBER = {1},
PAGES = {181--223},
ISSN = {0003-486X},
CODEN = {ANMAAH},
MRCLASS = {52C22},
MRNUMBER = {99m:52027},
MRREVIEWER = {E. Hertel},
DOI = {10.2307/120988},
ZBLNUMBER = {0941.52018},
} -
[HU79] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publ. Co., Reading, MA, 1979.
@book {HU79, MRKEY = {645539},
AUTHOR = {Hopcroft, John E. and Ullman, Jeffrey D.},
TITLE = {Introduction to Automata Theory, Languages, and Computation},
SERIES = {Addison-Wesley Series in Computer Science},
PUBLISHER = {Addison-Wesley Publ. Co., Reading, MA},
YEAR = {1979},
PAGES = {x+418},
ISBN = {0-201-02988-X},
MRCLASS = {68-01 (03-01 03Dxx 68D05 68F05)},
MRNUMBER = {83j:68002},
MRREVIEWER = {S. Istrail},
ZBLNUMBER = {0426.68001},
} -
[Hurd92] L. P. Hurd, J. Kari, and K. Culik, "The topological entropy of cellular automata is uncomputable," Ergodic Theory Dynam. Systems, vol. 12, iss. 2, pp. 255-265, 1992.
@article {Hurd92, MRKEY = {1176622},
AUTHOR = {Hurd, Lyman P. and Kari, Jarkko and Culik, Karel},
TITLE = {The topological entropy of cellular automata is uncomputable},
JOURNAL = {Ergodic Theory Dynam. Systems},
FJOURNAL = {Ergodic Theory and Dynamical Systems},
VOLUME = {12},
YEAR = {1992},
NUMBER = {2},
PAGES = {255--265},
ISSN = {0143-3857},
MRCLASS = {58F08 (68Q80)},
MRNUMBER = {93f:58124},
MRREVIEWER = {M. L. Blank},
ZBLNUMBER = {0770.58017},
} -
[K98] B. P. Kitchens, Symbolic Dynamics, One-Sided, Two-Sided and Countable State Markov Shifts, New York: Springer-Verlag, 1998.
@book {K98, MRKEY = {1484730},
AUTHOR = {Kitchens, Bruce P.},
TITLE = {Symbolic Dynamics, One-Sided, Two-Sided and Countable State Markov Shifts},
SERIES = {Universitext},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
YEAR = {1998},
PAGES = {x+252},
ISBN = {3-540-62738-3},
MRCLASS = {58F03 (54H20)},
MRNUMBER = {98k:58079},
MRREVIEWER = {Doris Fiebig},
ZBLNUMBER = {0892.58020},
} -
[KO91] K. Ko, Complexity Theory of Real Functions, Boston: Birkhäuser, 1991.
@book {KO91, MRKEY = {1137517},
AUTHOR = {Ko, Ker-I},
TITLE = {Complexity Theory of Real Functions},
SERIES = {Prog. Theoret. Comput. Sci.},
PUBLISHER = {Birkhäuser},
ADDRESS = {Boston},
YEAR = {1991},
PAGES = {x+309},
ISBN = {0-8176-3586-6},
MRCLASS = {03D15 (03-02 03F60 26E40 65Y20 68Q15)},
MRNUMBER = {93i:03057},
MRREVIEWER = {Douglas S. Bridges},
ZBLNUMBER = {0791.03019},
} -
[lind84] D. A. Lind, "The entropies of topological Markov shifts and a related class of algebraic integers," Ergodic Theory Dynam. Systems, vol. 4, iss. 2, pp. 283-300, 1984.
@article {lind84, MRKEY = {766106},
AUTHOR = {Lind, D. A.},
TITLE = {The entropies of topological {M}arkov shifts and a related class of algebraic integers},
JOURNAL = {Ergodic Theory Dynam. Systems},
FJOURNAL = {Ergodic Theory and Dynamical Systems},
VOLUME = {4},
YEAR = {1984},
NUMBER = {2},
PAGES = {283--300},
ISSN = {0143-3857},
MRCLASS = {58F11 (15A48 28D20)},
MRNUMBER = {86c:58092},
MRREVIEWER = {W. Krieger},
ZBLNUMBER = {0546.58035},
} -
[LM95] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge: Cambridge Univ. Press, 1995.
@book {LM95, MRKEY = {1369092},
AUTHOR = {Lind, Douglas and Marcus, Brian},
TITLE = {An Introduction to Symbolic Dynamics and Coding},
PUBLISHER = {Cambridge Univ. Press},
ADDRESS = {Cambridge},
YEAR = {1995},
PAGES = {xvi+495},
ISBN = {0-521-55124-2; 0-521-55900-6},
MRCLASS = {58F03 (15A48 54H20 58F20 94A24 94B60)},
MRNUMBER = {97a:58050},
MRREVIEWER = {Petr K{\.u}rka},
ZBLNUMBER = {1106.37301},
} -
[LS90] D. Lind, K. Schmidt, and T. Ward, "Mahler measure and entropy for commuting automorphisms of compact groups," Invent. Math., vol. 101, iss. 3, pp. 593-629, 1990.
@article {LS90, MRKEY = {1062797},
AUTHOR = {Lind, Douglas and Schmidt, Klaus and Ward, Tom},
TITLE = {Mahler measure and entropy for commuting automorphisms of compact groups},
JOURNAL = {Invent. Math.},
FJOURNAL = {Inventiones Mathematicae},
VOLUME = {101},
YEAR = {1990},
NUMBER = {3},
PAGES = {593--629},
ISSN = {0020-9910},
CODEN = {INVMBH},
MRCLASS = {22D40 (28D20)},
MRNUMBER = {92j:22013},
MRREVIEWER = {Meir Smorodinsky},
DOI = {10.1007/BF01231517},
ZBLNUMBER = {0774.22002},
} -
[M76] M. Misiurewicz, "A short proof of the variational principle for a ${\bf Z}_{+}^{N}$ action on a compact space," in International Conference on Dynamical Systems in Mathematical Physics, Paris: Soc. Math. France, 1976, vol. 40, pp. 147-157.
@incollection {M76, MRKEY = {0444904},
AUTHOR = {Misiurewicz, Micha{\l}},
TITLE = {A short proof of the variational principle for a {${\bf Z}\sb{+}\sp{N}$} action on a compact space},
BOOKTITLE = {International {C}onference on {D}ynamical {S}ystems in {M}athematical {P}hysics},
VENUE={{R}ennes, 1975},
PAGES = {147--157},
SERIES={Astérisque},
VOLUME={40},
PUBLISHER = {Soc. Math. France},
ADDRESS = {Paris},
YEAR = {1976},
MRCLASS = {28A65 (58F99)},
MRNUMBER = {56 \#3250},
MRREVIEWER = {P. Walters},
ZBLNUMBER = {0368.54013},
} -
[mozes89] S. Mozes, "Tilings, substitution systems and dynamical systems generated by them," J. Analyse Math., vol. 53, pp. 139-186, 1989.
@article {mozes89, MRKEY = {1014984},
AUTHOR = {Mozes, Shahar},
TITLE = {Tilings, substitution systems and dynamical systems generated by them},
JOURNAL = {J. Analyse Math.},
FJOURNAL = {Journal d'Analyse Mathématique},
VOLUME = {53},
YEAR = {1989},
PAGES = {139--186},
ISSN = {0021-7670},
CODEN = {JOAMAV},
MRCLASS = {58F03 (54H20 58F11)},
MRNUMBER = {91h:58038},
MRREVIEWER = {Peter Walters},
ZBLNUMBER = {0745.52013},
} -
[P64] W. Parry, "Intrinsic Markov chains," Trans. Amer. Math. Soc., vol. 112, pp. 55-66, 1964.
@article {P64, MRKEY = {0161372},
AUTHOR = {Parry, William},
TITLE = {Intrinsic {M}arkov chains},
JOURNAL = {Trans. Amer. Math. Soc.},
FJOURNAL = {Transactions of the American Mathematical Society},
VOLUME = {112},
YEAR = {1964},
PAGES = {55--66},
ISSN = {0002-9947},
MRCLASS = {60.65},
MRNUMBER = {28 \#4579},
MRREVIEWER = {H. P. Edmundson},
DOI = {10.2307/1994009},
ZBLNUMBER = {0127.35301},
} -
[robinson71] R. M. Robinson, "Undecidability and nonperiodicity for tilings of the plane," Invent. Math., vol. 12, pp. 177-209, 1971.
@article {robinson71, MRKEY = {0297572},
AUTHOR = {Robinson, Raphael M.},
TITLE = {Undecidability and nonperiodicity for tilings of the plane},
JOURNAL = {Invent. Math.},
FJOURNAL = {Inventiones Mathematicae},
VOLUME = {12},
YEAR = {1971},
PAGES = {177--209},
ISSN = {0020-9910},
MRCLASS = {02G05 (05B45 52A45 68A10)},
MRNUMBER = {45 \#6626},
MRREVIEWER = {D. A. Klarner},
DOI = {10.1007/BF01418780},
ZBLNUMBER = {0197.46801},
} -
[R04] D. Ruelle, Thermodynamic Formalism, The Mathematical Structures of Equilibrium Statistical Mechanics, Second ed., Cambridge: Cambridge Univ. Press, 2004.
@book {R04, MRKEY = {2129258},
AUTHOR = {Ruelle, David},
TITLE = {Thermodynamic Formalism, The Mathematical Structures of Equilibrium Statistical Mechanics},
SERIES = {Cambridge Math. Lib.},
EDITION = {Second},
PUBLISHER = {Cambridge Univ. Press},
ADDRESS = {Cambridge},
YEAR = {2004},
PAGES = {xx+174},
ISBN = {0-521-54649-4},
MRCLASS = {82B05 (37A60 37D35 37N20 82-02)},
MRNUMBER = {2006a:82008},
ZBLNUMBER = {1062.82001},
} -
[S48] C. E. Shannon, "A mathematical theory of communication," Bell System Tech. J., vol. 27, pp. 379-423, 623, 1948.
@article {S48, MRKEY = {0026286},
AUTHOR = {Shannon, C. E.},
TITLE = {A mathematical theory of communication},
JOURNAL = {Bell System Tech. J.},
FJOURNAL = {The Bell System Technical Journal},
VOLUME = {27},
YEAR = {1948},
PAGES = {379--423, 623--656},
ISSN = {0005-8580},
MRCLASS = {60.0X},
MRNUMBER = {10,133e},
MRREVIEWER = {J. L. Doob},
ZBLNUMBER = {1154.94303},
} -
[S06] J. G. Simonsen, "On the computability of the topological entropy of subshifts," Discrete Math. Theor. Comput. Sci., vol. 8, iss. 1, pp. 83-95, 2006.
@article {S06, MRKEY = {2247517},
AUTHOR = {Simonsen, Jakob Grue},
TITLE = {On the computability of the topological entropy of subshifts},
JOURNAL = {Discrete Math. Theor. Comput. Sci.},
FJOURNAL = {Discrete Mathematics \& Theoretical Computer Science. DMTCS.},
VOLUME = {8},
YEAR = {2006},
NUMBER = {1},
PAGES = {83--95},
ISSN = {1365-8050},
MRCLASS = {37B40 (03B25 37B10 37B15 68Q05 68Q45)},
MRNUMBER = {2008b:37025},
MRREVIEWER = {Enrico Formenti},
ZBLNUMBER = {1153.37320},
} -
[W94] T. Ward, "Automorphisms of $\Bbb Z^d$-subshifts of finite type," Indag. Math., vol. 5, iss. 4, pp. 495-504, 1994.
@article {W94, MRKEY = {1307966},
AUTHOR = {Ward, Thomas},
TITLE = {Automorphisms of {$\bold Z\sp d$}-subshifts of finite type},
JOURNAL = {Indag. Math.},
FJOURNAL = {Koninklijke Nederlandse Akademie van Wetenschappen. Indagationes Mathematicae. New Series},
VOLUME = {5},
YEAR = {1994},
NUMBER = {4},
PAGES = {495--504},
ISSN = {0019-3577},
MRCLASS = {28D15 (54H20)},
MRNUMBER = {97a:28014},
DOI = {10.1016/0019-3577(94)90020-5},
ZBLNUMBER = {0823.28007},
} -
[W77] B. Weiss, "Subshifts of finite type and sofic systems," Monatsh. Math., vol. 77, pp. 462-474, 1973.
@article {W77, MRKEY = {0340556},
AUTHOR = {Weiss, Benjamin},
TITLE = {Subshifts of finite type and sofic systems},
JOURNAL = {Monatsh. Math.},
VOLUME = {77},
YEAR = {1973},
PAGES = {462--474},
MRCLASS = {28A65 (54H20)},
MRNUMBER = {49 \#5308},
MRREVIEWER = {R. L. Adler},
DOI = {10.1007/BF01295322},
ZBLNUMBER = {0285.28021},
} -
[W73] R. F. Williams, "Classification of subshifts of finite type," Ann. of Math., vol. 98, pp. 120-153; errata, ibid. 99 (1974), 380, 1973.
@article {W73, MRKEY = {0331436},
AUTHOR = {Williams, R. F.},
TITLE = {Classification of subshifts of finite type},
JOURNAL = {Ann. of Math.},
FJOURNAL = {Annals of Mathematics. Second Series},
VOLUME = {98},
YEAR = {1973},
PAGES = {120--153; errata, {\it ibid.} 99 (1974), 380--381},
ISSN = {0003-486X},
MRCLASS = {58F20 (28A65)},
MRNUMBER = {48 \#9769},
MRREVIEWER = {C. B. Thomas},
DOI = {10.2307/1970908},
ZBLNUMBER = {0282.58008},
}
Full Article