{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,19]],"date-time":"2025-05-19T09:26:16Z","timestamp":1747646776431,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319401881"},{"type":"electronic","value":"9783319401898"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-40189-8_13","type":"book-chapter","created":{"date-parts":[[2016,6,13]],"date-time":"2016-06-13T11:34:07Z","timestamp":1465817647000},"page":"124-131","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Computability in Symbolic Dynamics"],"prefix":"10.1007","author":[{"given":"Emmanuel","family":"Jeandel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,6,14]]},"reference":[{"key":"13_CR1","unstructured":"Aubrun, N., Sablik, M.: An order on sets of tilings corresponding to an order on languages. In: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, 26\u201328 February 2009, Freiburg, Germany, pp. 99\u2013110 (2009)"},{"key":"13_CR2","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s10440-013-9808-5","volume":"126","author":"N Aubrun","year":"2013","unstructured":"Aubrun, N., Sablik, M.: Simulation of effective subshifts by two-dimensional subshifts of finite type. Acta Applicandae Math. 126, 35\u201363 (2013)","journal-title":"Acta Applicandae Math."},{"key":"13_CR3","unstructured":"Berger, R.: The undecidability of the domino problem. Ph.D. thesis, Harvard University (1964)"},{"issue":"5","key":"13_CR4","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1002\/malq.200710066","volume":"54","author":"D Cenzer","year":"2008","unstructured":"Cenzer, D., Dashti, A., King, J.L.F.: Computable symbolic dynamics. Math. Log. Q. 54(5), 460\u2013469 (2008)","journal-title":"Math. Log. Q."},{"key":"13_CR5","unstructured":"Cenzer, D., Remmel, J.B.: \n                      \n                        \n                      \n                      \n$${\\Pi }_1^0$$\n\n                      \n                        \n                          \n                            \u03a0\n                            1\n                            0\n                          \n                        \n                      \n                     classes in mathematics. In: Handbook of Recursive Mathematics - Volume 2: Recursive Algebra, Analysis and Combinatorics, vol. 139, Studies in Logic and the Foundations of Mathematics, pp. 623\u2013821. Elsevier (1998). Chap. 13"},{"key":"13_CR6","unstructured":"Dashti, A.: Effective symbolic dynamics. Ph.D. thesis, University of Florida (2008)"},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-642-15025-8_12","volume-title":"Fields of Logic and Computation","author":"B Durand","year":"2010","unstructured":"Durand, B., Romashchenko, A., Shen, A.: Effective closed subshifts in 1D can be implemented in 2D. In: Blass, A., Dershowitz, N., Reisig, W. (eds.) Fields of Logic and Computation. LNCS, vol. 6300, pp. 208\u2013226. Springer, Heidelberg (2010)"},{"key":"13_CR8","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1002\/malq.19590050703","volume":"5","author":"RM Friedberg","year":"1959","unstructured":"Friedberg, R.M., Rogers, H.: Reducibility and completeness for sets of integers. Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik 5, 117\u2013125 (1959)","journal-title":"Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik"},{"issue":"1311","key":"13_CR9","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1098\/rspa.1961.0132","volume":"262","author":"G Higman","year":"1961","unstructured":"Higman, G.: Subgroups of finitely presented groups. Proc. Roy. Soc. Lond. Ser. A Math. Phys. Sci. 262(1311), 455\u2013475 (1961)","journal-title":"Proc. Roy. Soc. Lond. Ser. A Math. Phys. Sci."},{"issue":"1","key":"13_CR10","doi-asserted-by":"publisher","first-page":"2009","DOI":"10.1007\/s00222-008-0161-7","volume":"176","author":"M Hochman","year":"2009","unstructured":"Hochman, M.: On the dynamics and recursive properties of multidimensional symbolic systems. Invent. Math. 176(1), 2009 (2009)","journal-title":"Invent. Math."},{"key":"13_CR11","volume-title":"Existentially Closed Groups","author":"G Higman","year":"1988","unstructured":"Higman, G., Scott, E.: Existentially Closed Groups. Oxford University Press, New York (1988)"},{"key":"13_CR12","unstructured":"Hochman, M., Vanier, P.: On the turing degrees of minimal subshifts. \n                      arXiv:1408.6487"},{"issue":"3","key":"13_CR13","doi-asserted-by":"publisher","first-page":"605","DOI":"10.2140\/pjm.1972.40.605","volume":"40","author":"CG Jockusch","year":"1972","unstructured":"Jockusch, C.G., Soare, R.I.: Degrees of members of \n                      \n                        \n                      \n                      \n$${\\Pi }_1^0$$\n\n                      \n                        \n                          \n                            \u03a0\n                            1\n                            0\n                          \n                        \n                      \n                     classes. Pac. J. Math. 40(3), 605\u2013616 (1972)","journal-title":"Pac. J. Math."},{"key":"13_CR14","first-page":"33","volume":"173","author":"CG Jockusch Jr","year":"1972","unstructured":"Jockusch Jr., C.G., Soare, R.I.: \n                      \n                        \n                      \n                      \n$$\\prod \\nolimits _{1}^{0}$$\n\n                      \n                        \n                          \n                            \u220f\n                            \n                              1\n                            \n                            0\n                          \n                        \n                      \n                     classes and degrees of theories. Trans. Am. Math. Soc. 173, 33\u201356 (1972)","journal-title":"Trans. Am. Math. Soc."},{"key":"13_CR15","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.tcs.2012.08.027","volume":"505","author":"E Jeandel","year":"2013","unstructured":"Jeandel, E., Vanier, P.: Turing degrees of multidimensional SFTs. Theoret. Comput. Sci. 505, 81\u201392 (2013)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"13_CR16","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1017\/etds.2013.60","volume":"35","author":"E Jeandel","year":"2015","unstructured":"Jeandel, E., Vanier, P.: Characterizations of periods of multidimensional shifts. Ergod. Theory Dyn. Syst. 35(2), 431\u2013460 (2015)","journal-title":"Ergod. Theory Dyn. Syst."},{"issue":"14","key":"13_CR17","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1093\/bjps\/IV.14.107","volume":"4","author":"G Kreisel","year":"1953","unstructured":"Kreisel, G.: A variant to Hilbert\u2019s theory of the foundations of arithmetic. Br. J. Philos. Sci. 4(14), 107\u2013129 (1953)","journal-title":"Br. J. Philos. Sci."},{"key":"13_CR18","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/S0304-3975(96)00025-4","volume":"174","author":"P Kurka","year":"1997","unstructured":"Kurka, P.: On topological dynamics of turing machines. Theoret. Comput. Sci. 174, 203\u2013216 (1997)","journal-title":"Theoret. Comput. Sci."},{"key":"13_CR19","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1090\/psapm\/060\/2078846","volume-title":"Symbolic Dynamics and its Applications, Proceedings of Symposia in Applied Mathematics","author":"DA Lind","year":"2004","unstructured":"Lind, D.A.: Multi-dimensional symbolic dynamics. In: Williams, S.G. (ed.) Symbolic Dynamics and its Applications, Proceedings of Symposia in Applied Mathematics, vol. 60, pp. 61\u201379. American Mathematical Society, Providence (2004)"},{"key":"13_CR20","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626302","volume-title":"An Introduction to Symbolic Dynamics and Coding","author":"DA Lind","year":"1995","unstructured":"Lind, D.A., Marcus, B.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, New York (1995)"},{"issue":"5","key":"13_CR21","doi-asserted-by":"publisher","first-page":"1617","DOI":"10.1090\/S0002-9939-2011-11000-1","volume":"140","author":"JS Miller","year":"2012","unstructured":"Miller, J.S.: Two notes on subshifts. Proc. Am. Math. Soc. 140(5), 1617\u20131622 (2012)","journal-title":"Proc. Am. Math. Soc."},{"issue":"3","key":"13_CR22","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1088\/0951-7715\/4\/3\/006","volume":"4","author":"C Moore","year":"1991","unstructured":"Moore, C.: Generalized one-sided shifts and maps of the interval. Nonlinearity 4(3), 727\u2013745 (1991)","journal-title":"Nonlinearity"},{"issue":"2","key":"13_CR23","doi-asserted-by":"publisher","first-page":"286","DOI":"10.2307\/2272641","volume":"39","author":"D Myers","year":"1974","unstructured":"Myers, D.: Non recursive tilings of the plane II. J. Symb. Log. 39(2), 286\u2013294 (1974)","journal-title":"J. Symb. Log."},{"issue":"3","key":"13_CR24","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/BF01418780","volume":"12","author":"RM Robinson","year":"1971","unstructured":"Robinson, R.M.: Undecidability and nonperiodicity for tilings of the plane. Invent. Math. 12(3), 177\u2013209 (1971)","journal-title":"Invent. Math."},{"key":"13_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/11672142_32","volume-title":"STACS 2006","author":"AY Rumyantsev","year":"2006","unstructured":"Rumyantsev, A.Y., Ushakov, M.A.: Forbidden substrings, kolmogorov complexity and almost periodic sequences. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 396\u2013407. Springer, Heidelberg (2006)"},{"issue":"3","key":"13_CR26","doi-asserted-by":"publisher","first-page":"233","DOI":"10.2307\/2964680","volume":"25","author":"JR Shoenfield","year":"1960","unstructured":"Shoenfield, J.R.: Degrees of models. J. Symb. Log. 25(3), 233\u2013237 (1960)","journal-title":"J. Symb. Log."},{"issue":"4","key":"13_CR27","doi-asserted-by":"publisher","first-page":"489","DOI":"10.2748\/tmj\/1325886278","volume":"63","author":"SG Simpson","year":"2011","unstructured":"Simpson, S.G.: Mass problems associated with effectively closed sets. Tohoku Math. J. 63(4), 489\u2013517 (2011)","journal-title":"Tohoku Math. J."},{"key":"13_CR28","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1017\/etds.2012.152","volume":"34","author":"SG Simpson","year":"2014","unstructured":"Simpson, S.G.: Medvedev degrees of two-dimensional subshifts of finite type. Ergod. Theory Dyn. Syst. 34, 679\u2013688 (2014)","journal-title":"Ergod. Theory Dyn. Syst."}],"container-title":["Lecture Notes in Computer Science","Pursuit of the Universal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-40189-8_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T00:58:49Z","timestamp":1558313929000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-40189-8_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319401881","9783319401898"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-40189-8_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"14 June 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}