Geodesic
The group of reversible turing machines: subgroups, generators, and computability
Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e176

Voir la notice de l'article provenant de la source Cambridge University Press

We study an abstract group of reversible Turing machines. In our model, each machine is interpreted as a homeomorphism over a space which represents a tape filled with symbols and a head carrying a state. These homeomorphisms can only modify the tape at a bounded distance around the head, change the state, and move the head in a bounded way. We study three natural subgroups arising in this model: the group of finite-state automata, which generalizes the topological full groups studied in topological dynamics and the theory of orbit-equivalence; the group of oblivious Turing machines whose movement is independent of tape contents, which generalizes lamplighter groups and has connections to the study of universal reversible logical gates, and the group of elementary Turing machines, which are the machines which are obtained by composing finite-state automata and oblivious Turing machines.We show that both the group of oblivious Turing machines and that of elementary Turing machines are finitely generated, while the group of finite-state automata and the group of reversible Turing machines are not. We show that the group of elementary Turing machines has undecidable torsion problem. From this, we also obtain that the group of cellular automata (more generally, the automorphism group of any uncountable one-dimensional sofic subshift) contains a finitely generated subgroup with undecidable torsion problem. We also show that the torsion problem is undecidable for the topological full group of a full $\mathbb {Z}^d$-shift on a nontrivial alphabet if and only if $d \geq 2$. 
Barbieri, Sebastian; Kari, Jarkko; Salo, Ville. The group of reversible turing machines: subgroups, generators, and computability. Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e176. doi: 10.1017/fms.2025.10118
@article{10_1017_fms_2025_10118,
     author = {Barbieri, Sebastian and Kari, Jarkko and Salo, Ville},
     title = {The group of reversible turing machines: subgroups, generators, and computability},
     journal = {Forum of Mathematics, Sigma},
     pages = {e176},
     year = {2025},
     volume = {13},
     number = {1},
     doi = {10.1017/fms.2025.10118},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10118/}
}
TY  - JOUR
AU  - Barbieri, Sebastian
AU  - Kari, Jarkko
AU  - Salo, Ville
TI  - The group of reversible turing machines: subgroups, generators, and computability
JO  - Forum of Mathematics, Sigma
PY  - 2025
SP  - e176
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10118/
DO  - 10.1017/fms.2025.10118
ID  - 10_1017_fms_2025_10118
ER  - 
%0 Journal Article
%A Barbieri, Sebastian
%A Kari, Jarkko
%A Salo, Ville
%T The group of reversible turing machines: subgroups, generators, and computability
%J Forum of Mathematics, Sigma
%D 2025
%P e176
%V 13
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10118/
%R 10.1017/fms.2025.10118
%F 10_1017_fms_2025_10118

[1] Aaronson, S., Grier, D. and Schaeffer, L., ‘The classification of reversible bit operations’, in 8th Innovations in Theoretical Computer Science Conference, vol. 67 of LIPIcs. Leibniz Int. Proc. Inform. (Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017), Art. No. 23, 34 pp. Google Scholar

[2] Aubrun, N., Barbieri, S. and Sablik, M., ‘A notion of effectiveness for subshifts on finitely generated groups’, Theoret. Comput. Sci. 661 (2017), 35–55. Google Scholar | DOI

[3] Aubrun, N. and Sablik, M., ‘Simulation of effective subshifts by two-dimensional subshifts of finite type’, Acta Appl. Math. 126 (2013), 35–63. Google Scholar | DOI

[4] Barbieri, S., Kari, J. and Salo, V., ‘The group of reversible Turing machines’, in Cellular Automata and Discrete Complex Systems, vol. 9664 of Lecture Notes in Comput. Sci. (Springer, Cham, 2016), 49–62. Google Scholar | DOI

[5] Belk, J. and Bleak, C., ‘Some undecidability results for asynchronous transducers and the Brin–Thompson group 2V’, Trans. Amer. Math. Soc. 369(5) (2017), 3157–3172. Google Scholar | DOI

[6] Belk, J. and Matucci, F., ‘Conjugacy and dynamics in Thompson’s groups’, Geom. Dedicata 169 (2014), 239–261. Google Scholar | DOI

[7] Blondel, V. D., Cassaigne, J. and Nichitiu, C., ‘On the presence of periodic configurations in Turing machines and in counter machines’, Theoret. Comput. Sci. 289(1) (2002), 573–590. Google Scholar | DOI

[8] Boykett, T., Kari, J. and Salo, V., ‘Strongly universal reversible gate sets’, in Reversible Computation, vol. 9720 of Lecture Notes in Comput. Sci. (Springer, Cham, 2016), 239–254. Google Scholar | DOI

[9] Ceccherini-Silberstein, T. and Coornaert, M., Cellular Automata and Groups, 2nd ed, Springer Monographs in Mathematics (Springer, Cham, 2023). Google Scholar

[10] Ceccherini-Silberstein, T. and Coornaert, M., Exercises in Cellular Automata and Groups, Springer Monographs in Mathematics (Springer, Cham, 2023). With a foreword by R. I. Grigorchuk. Google Scholar

[11] Czeizler, E. and Kari, J., ‘A tight linear bound on the synchronization delay of bijective automata’, Theoret. Comput. Sci. 380(1–2) (2007), 23–36. Google Scholar | DOI

[12] Delvenne, J.-C., Kůrka, P. and Blondel, V., ‘Decidability and universality in symbolic dynamical systems’, Fund. Inform. 74(4) (2006), 463–490. Google Scholar

[13] Durand, B., Romashchenko, A. and Shen, A., ‘Effective closed subshifts in 1D can be implemented in 2D’, in Fields of Logic and Computation, vol. 6300 of Lecture Notes in Comput. Sci. (Springer, Berlin, 2010), 208–226. Google Scholar | DOI

[14] Elek, G. and Monod, N., ‘On the topological full group of a minimal Cantor -system’, Proc. Amer. Math. Soc. 141(10) (2013), 3549–3552. Google Scholar | DOI

[15] Gajardo, A. and Guillon, P., ‘Zigzags in Turing machines’, in Computer Science—Theory and Applications, vol. 6072 of Lecture Notes in Comput. Sci. (Springer, Berlin, 2010), 109–119. Google Scholar | DOI

[16] Gajardo, A. and Mazoyer, J., ‘One head machines from a symbolic approach’, Theoret. Comput. Sci. 370(1–3) (2007), 34–47. Google Scholar | DOI

[17] Gajardo, A., Ollinger, N. and Torres-Avilés, R., ‘The transitivity problem of Turing machines’, in Mathematical Foundations of Computer Science 2015. Part I, vol. 9234 of Lecture Notes in Comput. Sci. (Springer, Heidelberg, 2015), 231–242. Google Scholar | DOI

[18] Giordano, T., Putnam, I. F. and Skau, C. F., ‘Full groups of Cantor minimal systems’, Israel J. Math. 111 (1999), 285–320. Google Scholar | DOI

[19] Grigorchuk, R. I. and Medinets, K. S., ‘On the algebraic properties of topological full groups’, Mat. Sb. 205(6) (2014), 87–108. Google Scholar

[20] Hochman, M., ‘On the dynamics and recursive properties of multidimensional symbolic systems’, Invent. Math. 176(1) (2009), 131–167. Google Scholar | DOI

[21] Jeandel, E., ‘Computability of the entropy of one-tape Turing machines’, in 31st International Symposium on Theoretical Aspects of Computer Science, vol. 25 of LIPIcs. Leibniz Int. Proc. Inform. (Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2014), 421–432. Google Scholar

[22] Juschenko, K. and Monod, N., ‘Cantor systems, piecewise translations and simple amenable groups’, Ann. of Math. (2) 178(2) (2013), 775–787. Google Scholar | DOI

[23] Kari, J., ‘Representation of reversible cellular automata with block permutations’, Math. Systems Theory 29(1) (1996), 47–61. Google Scholar | DOI

[24] Kari, J., ‘Infinite snake tiling problems’, in Developments in Language Theory, vol. 2450 of Lecture Notes in Comput. Sci. (Springer, Berlin, 2003), 67–77. Google Scholar | DOI

[25] Kari, J. and Ollinger, N., ‘Periodicity and immortality in reversible computing’, in Mathematical Foundations of Computer Science 2008, vol. 5162 of Lecture Notes in Comput. Sci. (Springer, Berlin, 2008), 419–430. Google Scholar

[26] Kazda, A., ‘The chain relation in sofic subshifts’, Fund. Inform. 84(3–4) (2008), 375–390. Google Scholar

[27] Kůrka, P., ‘On topological dynamics of Turing machines’, Theoret. Comput. Sci. 174(1–2) (1997), 203–216. Google Scholar | DOI

[28] Kůrka, P., ‘Erratum to: Entropy of Turing machines with moving head’, Theoret. Comput. Sci. 411(31–33) (2010), 2999–3000. Google Scholar | DOI

[29] Langton, C. G., ‘Studying artificial life with cellular automata’, Phys. D 22(1–3) (1986), 120–149. Evolution, games and learning (Los Alamos, N.M., 1985). Google Scholar | DOI

[30] Lind, D. and Marcus, B., An Introduction to Symbolic Dynamics and Coding (Cambridge University Press, Cambridge, 1995). Google Scholar | DOI

[31] Matui, H., ‘Some remarks on topological full groups of Cantor minimal systems’, Internat. J. Math. 17(2) (2006), 231–251. Google Scholar | DOI

[32] Matui, H., ‘Topological full groups of one-sided shifts of finite type’, J. Reine Angew. Math. 705 (2015), 35–84. Google Scholar | DOI

[33] Moore, C., ‘Generalized shifts: unpredictability and undecidability in dynamical systems’, Nonlinearity 4(2) (1991), 199–230. Google Scholar | DOI

[34] Pavlov, R. and Schraudner, M., ‘Classification of sofic projective subdynamics of multidimensional shifts of finite type’, Trans. Amer. Math. Soc. 367(5) (2015), 3371–3421. Google Scholar | DOI

[35] Salo, V., ‘A note on subgroups of automorphism groups of full shifts’, Ergodic Theory Dynam. Systems 38(4) (2018), 1588–1605. Google Scholar | DOI

[36] Salo, V., ‘Subshifts with sparse traces’, Studia Math. 255(2) (2020), 159–207. Google Scholar | DOI

[37] Salo, V. and Törmä, I., ‘Group-walking automata’, in Cellular Automata and Discrete Complex Systems, vol. 9099 of Lecture Notes in Comput. Sci. (Springer, Heidelberg, 2015), 224–237. Google Scholar | DOI

[38] Salo, V. and Törmä, I., ‘Plane-walking automata’, in Cellular Automata and Discrete Complex Systems, vol. 8996 of Lecture Notes in Comput. Sci. (Springer, Cham, 2015), 135–148. Google Scholar | DOI

[39] Selinger, P., Reversible k-valued logic circuits are finitely generated for odd k, preprint (2016). . Google Scholar | arXiv

[40] Xu, S., Reversible logic synthesis with minimal usage of ancilla bits, Master’s thesis, MIT, 2015. Google Scholar

Cité par Sources :