{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T15:07:38Z","timestamp":1791299258852,"version":"4.1.0"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319392998","type":"print"},{"value":"9783319393001","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"vor","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-39300-1_5","type":"book-chapter","created":{"date-parts":[[2016,6,1]],"date-time":"2016-06-01T08:17:10Z","timestamp":1464769030000},"page":"49-62","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["The Group of Reversible Turing Machines"],"prefix":"10.1007","author":[{"given":"Sebasti\u00e1n","family":"Barbieri","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jarkko","family":"Kari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ville","family":"Salo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,6,2]]},"reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"Ollinger, N., Gajardo, A., Torres-Avil\u00e9s, R.: The transitivity problem of turing machines (2015)","DOI":"10.1007\/978-3-662-48057-1_18"},{"key":"5_CR2","unstructured":"Aaronson, S., Grier, D., Schaeffer, L.: The classification of reversible bit operations. ArXiv e-prints, April 2015"},{"key":"5_CR3","unstructured":"Aubrun, N., Barbieri, S., Sablik, M.: A notion of effectiveness for subshifts on finitely generated groups. ArXiv e-prints, December 2014"},{"issue":"1","key":"5_CR4","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(1), 35\u201363 (2013)","journal-title":"Acta Applicandae Math."},{"key":"5_CR5","unstructured":"Belk, J., Bleak, C.: Some undecidability results for asynchronous transducers and the Brin-Thompson group 2V. ArXiv e-prints, May 2014"},{"issue":"1","key":"5_CR6","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s10711-013-9853-2","volume":"169","author":"J Belk","year":"2014","unstructured":"Belk, J., Matucci, F.: Conjugacy and dynamics in Thompson\u2019s groups. Geom. Dedicata 169(1), 239\u2013261 (2014)","journal-title":"Geom. Dedicata"},{"key":"5_CR7","series-title":"Springer Monographs in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14034-1","volume-title":"Cellular Automata and Groups","author":"T Ceccherini-Silberstein","year":"2010","unstructured":"Ceccherini-Silberstein, T., Coornaert, M.: Cellular Automata and Groups. Springer Monographs in Mathematics. Springer, Heidelberg (2010)"},{"issue":"12","key":"5_CR8","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.tcs.2007.02.052","volume":"380","author":"E Czeizler","year":"2007","unstructured":"Czeizler, E., Kari, J.: A tight linear bound on the synchronization delay of bijective automata. Theor. Comput. Sci. 380(12), 23\u201336 (2007). Automata, Languages and Programming","journal-title":"Theor. Comput. Sci."},{"key":"5_CR9","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":"5_CR10","doi-asserted-by":"crossref","unstructured":"Elek, G., Monod, N.: On the topological full group of a minimal Cantor Z$$^2$$-system. ArXiv e-prints, December 2012","DOI":"10.1090\/S0002-9939-2013-11654-0"},{"key":"5_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/978-3-642-13182-0_11","volume-title":"Computer Science \u2013 Theory and Applications","author":"A Gajardo","year":"2010","unstructured":"Gajardo, A., Guillon, P.: Zigzags in turing machines. In: Ablayev, F., Mayr, E.W. (eds.) CSR 2010. LNCS, vol. 6072, pp. 109\u2013119. Springer, Heidelberg (2010)"},{"issue":"13","key":"5_CR12","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.tcs.2006.10.004","volume":"370","author":"A Gajardo","year":"2007","unstructured":"Gajardo, A., Mazoyer, J.: One head machines from a symbolic approach. Theor. Comput. Sci. 370(13), 34\u201347 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"5_CR13","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/BF02810689","volume":"111","author":"T Giordano","year":"1999","unstructured":"Giordano, T., Putnam, I., Skau, C.: Full groups of cantor minimal systems. Isr. J. Math. 111(1), 285\u2013320 (1999)","journal-title":"Isr. J. Math."},{"key":"5_CR14","unstructured":"Grigorchuk, R., Medynets, K.: On algebraic properties of topological full groups. ArXiv e-prints, May 2011"},{"issue":"4","key":"5_CR15","first-page":"463","volume":"74","author":"P K\u016frka","year":"2006","unstructured":"K\u016frka, P., Delvenne, J., Blondel, V.: Decidability and universality in symbolic dynamical systems. Fund. Inform. 74(4), 463\u2013490 (2006)","journal-title":"Fund. Inform."},{"key":"5_CR16","unstructured":"Jeandel, E.: Computability of the entropy of one-tape Turing machines. arXiv preprint (2013). arXiv:1302.1170"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"Juschenko, K., Monod, N.: Cantor systems, piecewise translations and simple amenable groups. Ann. Math. (2012)","DOI":"10.4007\/annals.2013.178.2.7"},{"key":"5_CR18","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF01201813","volume":"29","author":"J Kari","year":"1996","unstructured":"Kari, J.: Representation of reversible cellular automata with block permutations. Theor. Comput. Syst. 29, 47\u201361 (1996). doi: 10.1007\/BF01201813","journal-title":"Theor. Comput. Syst."},{"key":"5_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/978-3-540-85238-4_34","volume-title":"Mathematical Foundations of Computer Science 2008","author":"J Kari","year":"2008","unstructured":"Kari, J., Ollinger, N.: Periodicity and immortality in reversible computing. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol. 5162, pp. 419\u2013430. Springer, Heidelberg (2008)"},{"issue":"1\u20132","key":"5_CR20","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/S0304-3975(96)00025-4","volume":"174","author":"P K\u016frka","year":"1997","unstructured":"K\u016frka, P.: On topological dynamics of turing machines. Theor. Comput. Sci. 174(1\u20132), 203\u2013216 (1997)","journal-title":"Theor. Comput. Sci."},{"issue":"31\u201333","key":"5_CR21","doi-asserted-by":"publisher","first-page":"2999","DOI":"10.1016\/j.tcs.2010.04.033","volume":"411","author":"P K\u016frka","year":"2010","unstructured":"K\u016frka, P.: Erratum to: entropy of turing machines with moving head. Theor. Comput. Sci. 411(31\u201333), 2999\u20133000 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"5_CR22","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626302","volume-title":"An Introduction to Symbolic Dynamics and Coding","author":"D Lind","year":"1995","unstructured":"Lind, D., Marcus, B.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge (1995)"},{"issue":"1","key":"5_CR23","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1090\/S0002-9947-1988-0927684-2","volume":"306","author":"D Lind","year":"1988","unstructured":"Lind, D., Boyle, M., Rudolph, D.: The automorphism group of a shift of finite type. Trans. Am. Math. Soc. 306(1), 71\u2013114 (1988)","journal-title":"Trans. Am. Math. Soc."},{"key":"5_CR24","doi-asserted-by":"crossref","unstructured":"Matui, H.: Topological full groups of one-sided shifts of finite type. ArXiv e-prints, October 2012","DOI":"10.1515\/crelle-2013-0041"},{"key":"5_CR25","unstructured":"Salo, V., Schraudner, M.: in preparation"},{"key":"5_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/978-3-662-47221-7_17","volume-title":"Cellular Automata and Discrete Complex Systems","author":"V Salo","year":"2015","unstructured":"Salo, V., T\u00f6rm\u00e4, I.: Group-walking automata. In: Kari, J. (ed.) AUTOMATA 2015. LNCS, vol. 9099, pp. 224\u2013237. Springer, Heidelberg (2015)"},{"key":"5_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-319-18812-6_11","volume-title":"Cellular Automata and Discrete Complex Systems","author":"V Salo","year":"2015","unstructured":"Salo, V., T\u00f6rm\u00e4, I.: Plane-walking automata. In: Isokawa, T., Imai, K., Matsui, N., Peper, F., Umeo, H. (eds.) AUTOMATA 2014. LNCS, vol. 8996, pp. 135\u2013148. Springer, Heidelberg (2015)"},{"issue":"1","key":"5_CR28","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1016\/S0304-3975(01)00382-6","volume":"289","author":"J Cassaigne","year":"2002","unstructured":"Cassaigne, J., Blondel, V., Nichitiu, C.: On the presence of periodic configurations in turing machines and in counter machines. Theor. Comput. Sci. 289(1), 573\u2013590 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"5_CR29","first-page":"71","volume":"9","author":"A Vershik","year":"1997","unstructured":"Vershik, A., Gordon, E.: Groups that are locally embeddable in the class of finite groups. Algebra i Analiz 9(1), 71\u201397 (1997)","journal-title":"Algebra i Analiz"},{"key":"5_CR30","first-page":"350","volume":"62","author":"B Weiss","year":"2000","unstructured":"Weiss, B.: Sofic groups and dynamical systems. Sankhy\u0101 Indian J. Stat. Ser. A 62, 350\u2013359 (2000)","journal-title":"Sankhy\u0101 Indian J. Stat. Ser. A"},{"issue":"3","key":"5_CR31","doi-asserted-by":"crossref","first-page":"837","DOI":"10.1215\/ijm\/1258130987","volume":"46","author":"M Ziman","year":"2002","unstructured":"Ziman, M., et al.: On finite approximations of groups and algebras. Ill. J. Math. 46(3), 837\u2013839 (2002)","journal-title":"Ill. J. Math."}],"container-title":["Lecture Notes in Computer Science","Cellular Automata and Discrete Complex Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-39300-1_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,18]],"date-time":"2023-08-18T18:10:39Z","timestamp":1692382239000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-39300-1_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319392998","9783319393001"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-39300-1_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"2 June 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}