An automaton group with undecidable order and Engel problems. (English) Zbl 1427.20040
Summary: For every Turing machine, we construct an automaton group that simulates it. Precisely, starting from an initial configuration of the Turing machine, we explicitly construct an element of the group such that the Turing machine stops if, and only if, this element is of finite order. If the Turing machine is universal, the corresponding automaton group has an undecidable order problem. This solves a problem raised by Grigorchuk.
The above group also has an undecidable Engel problem: there is no algorithm that, given \(g\), \(h\) in the group, decides whether there exists an integer \(n\) such that the \(n\)-iterated commutator \([\ldots [[g,h],h], \ldots, h]\) is the identity or not. This solves a problem raised by Bartholdi.
The above group also has an undecidable Engel problem: there is no algorithm that, given \(g\), \(h\) in the group, decides whether there exists an integer \(n\) such that the \(n\)-iterated commutator \([\ldots [[g,h],h], \ldots, h]\) is the identity or not. This solves a problem raised by Bartholdi.
MSC:
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
| 20F45 | Engel conditions |
| 68Q80 | Cellular automata (computational aspects) |
| 68Q04 | Classical models of computation (Turing machines, etc.) |
References:
| [1] | Akhavi, A.; Klimann, I.; Lombardy, S.; Mairesse, J.; Picantin, M., On the finiteness problem for automaton (semi)groups, Internat. J. Algebra Comput., 22, 6, Article 1250052 pp. (2012), 26 p · Zbl 1280.20038 |
| [2] | Alešin, S. V., Finite automata and the Burnside problem for periodic groups, Akad. Nauk SSSR Mat. Zametki, 11, 319-328 (1972), (Russian) · Zbl 0246.20024 |
| [3] | Bartholdi, L., Algorithmic Decidability of Engel’s Property for Automaton Groups, Lecture Notes in Computer Science, vol. 9691 (2016), Springer: Springer Cham · Zbl 1477.20067 |
| [4] | Bartholdi, L., Decidability problems in automaton semigroups, 21 p |
| [5] | Bartholdi, L.; Mitrofanov, I., The word and order problems for self-similar and automata groups, 15 p · Zbl 1496.20056 |
| [6] | Belk, J.; Bleak, C., Some undecidability results for asynchronous transducers and the Brin-Thompson group 2V, Trans. Amer. Math. Soc., 369, 5, 3157-3172 (2017) · Zbl 1364.20015 |
| [7] | Bondarenko, I. V.; Bondarenko, N. V.; Sidki, S. N.; Zapata, F. R., On the conjugacy problem for finite-state automorphisms of regular rooted trees, Groups Geom. Dyn., 7, 2, 323-355 (2013), with an appendix by R.M. Jungers · Zbl 1286.20034 |
| [8] | Brough, T.; Cain, A., Automaton semigroup constructions, Semigroup Forum, 90, 3, 763-774 (2015) · Zbl 1336.20062 |
| [9] | Brough, T.; Cain, A., Automaton semigroups: new constructions results and examples of non-automaton semigroups, Theoret. Comput. Sci., 674, 1-15 (2017) · Zbl 1381.20052 |
| [10] | Carlitz, L.; Wilansky, A.; Milnor, J.; Struble, R. A.; Felsinger, N.; Simoes, J. M.S.; Power, E. A.; Shafer, R. E.; Maas, R. E., Problems and solutions: advanced problems: 5600-5609, Amer. Math. Monthly, 75, 6, 685-687 (1968) |
| [11] | Clapham, C. R.J., Finitely presented groups with word problems of arbitrary degrees of insolubility, Proc. Lond. Math. Soc. (3), 14, 633-676 (1964) · Zbl 0232.20063 |
| [12] | Cook, M., Universality in elementary cellular automata, Complex Systems, 15, 1, 1-40 (2004) · Zbl 1167.68387 |
| [13] | Cook, M., A concrete view of Rule 110 computation, (Proceedings International Workshop on The Complexity of Simple Programs. Proceedings International Workshop on The Complexity of Simple Programs, Electronic Proceedings in Theoretical Computer Science (EPTCS), vol. 1 (2009)), 31-55 · Zbl 1456.68101 |
| [14] | Day, M., Amenable semigroups, Illinois J. Math., 1, 509-544 (1957) · Zbl 0078.29402 |
| [15] | D’Angeli, D.; Rodaro, E., Freeness of automaton groups vs boundary dynamics, J. Algebra, 462, 115-136 (2016) · Zbl 1454.20069 |
| [16] | D’Angeli, D.; Rodaro, E.; Wächter, J. P., On the complexity of the word problem for automaton semigroups and automaton groups, Adv. in Appl. Math., 90, 160-187 (2017) · Zbl 1393.20014 |
| [17] | D’Angeli, D.; Godin, T.; Klimann, I.; Picantin, M.; Rodaro, E., Boundary action of automaton groups without singular points and Wang tilings, 40 p |
| [18] | Delacourt, M.; Ollinger, N., Permutive one-way cellular automata and the finiteness problem for automaton groups, (Unveiling Dynamics and Complexity. Unveiling Dynamics and Complexity, Lecture Notes in Computer Science, vol. 10307 (2017)), 234-245 · Zbl 1489.68146 |
| [19] | Eilenberg, S., Automata, Languages, and Machines, vol. A, Pure Appl. Math., vol. 58 (1974), Academic Press (A subsidiary of Harcourt Brace Jovanovich, Publishers): Academic Press (A subsidiary of Harcourt Brace Jovanovich, Publishers) New York, xvi+451 p · Zbl 0317.94045 |
| [20] | Gillibert, P., The finiteness problem for automaton semigroups is undecidable, Internat. J. Algebra Comput., 24, 1, 1-9 (2014) · Zbl 1292.20040 |
| [21] | Gillibert, P., Simulating Turing machines with invertible Mealy automata (July 2017) |
| [22] | Gillibert, P., An automaton group with undecidable order and Engel problems, 22 p · Zbl 1427.20040 |
| [23] | Godin, T.; Klimann, I.; Picantin, M., On torsion-free semigroups generated by invertible reversible Mealy automata, (Language and Automata Theory and Applications. Language and Automata Theory and Applications, Lecture Notes in Computer Science, vol. 8977 (2015)), 328-339 · Zbl 1405.68197 |
| [24] | Godin, T.; Klimann, I., Connected reversible Mealy automata of prime size cannot generate infinite Burnside groups, (41st International Symposium on Mathematical Foundations of Computer Science. 41st International Symposium on Mathematical Foundations of Computer Science, LIPIcs. Leibniz International Proceedings in Informatics, vol. 58 (2016)), art. no. 44, 14 p · Zbl 1398.68309 |
| [25] | Golod, E. S., On nil-algebras and finitely approximable p-groups, Izv. Akad. Nauk SSSR Ser. Mat., 28, 273-276 (1964), (Russian) |
| [26] | Golod, E. S.; Shafarevich, I. R., On the class field tower, Izv. Akad. Nauk SSSR Ser. Mat., 28, 261-272 (1964), (Russian) · Zbl 0136.02602 |
| [27] | Grigorchuk, R. I., On Burnside’s problem on periodic groups, Funktsional. Anal. i Prilozhen., 14, 1, 53-54 (1980), (Russian) · Zbl 0595.20029 |
| [28] | Grigorchuk, R. I., On the Milnor problem of group growth, Dokl. Akad. Nauk SSSR, 271, 1, 30-33 (1983), (Russian) |
| [29] | Grigorchuk, R. I., Degrees of growth of finitely generated groups and the theory of invariant means, Izv. Akad. Nauk SSSR Ser. Mat., 48, 5, 939-985 (1984), (Russian) |
| [30] | Grigorchuk, R. I.; Šunić, Z., Self-Similarity and Branching in Group Theory, London Mathematical Society Lecture Note Series. London Mathematical Society Lecture Note Series, Groups St. Andrews, vol. 1, 36-95 (2005) · Zbl 1185.20044 |
| [31] | Grigorchuk, R. I.; Nekrashevych, V. V.; Sushchanskiĭ, V. I., Automata, dynamical systems, and groups, Tr. Mat. Inst. Steklova, 231 (2000), Din. Sist., Avtom. i Beskon. Gruppy, 134-214 · Zbl 1155.37311 |
| [32] | Higman, G., Subgroups of finitely presented groups, Proc. R. Soc. Ser. A Math. Phys. Sci., 262, 455-475 (1961) · Zbl 0104.02101 |
| [33] | Kari, J., The nilpotency problem of one-dimensional cellular automata, SIAM J. Comput., 21, 571-586 (1992) · Zbl 0761.68067 |
| [34] | Kari, J., Theory of cellular automata: a survey, Theoret. Comput. Sci., 334, 3-33 (2005) · Zbl 1080.68070 |
| [35] | Kari, J., Decidability and undecidability in cellular automata, Int. J. Gen. Syst., 41, 6, 539-554 (2012) · Zbl 1277.68152 |
| [36] | Kari, J., Tiling problem and undecidability in cellular automata, Comput. Complexity, 6, 3198-3211 (2012) |
| [37] | Kari, J., Cellular automata, tilings and (un)computability, (Combinatorics, Words and Symbolic Dynamics. Combinatorics, Words and Symbolic Dynamics, Encyclopedia of Mathematics and Its Applications, vol. 159 (2016)), 241-295 · Zbl 1383.68052 |
| [38] | Kari, J.; Ollinger, N., Periodicity and immortality in reversible computing, (Mathematical Foundations of Computer Science 2008. Mathematical Foundations of Computer Science 2008, Lecture Notes in Computer Science, vol. 5162 (2008)), 419-430 · Zbl 1173.68521 |
| [39] | Klimann, I., Automaton semigroups: the two-state case, Theory Comput. Syst., 58, 4, 664-680 (2016) · Zbl 1345.20074 |
| [40] | Klimann, I.; Picantin, M.; Savchuk, D., A connected 3-state reversible Mealy automaton cannot generate an infinite Burnside group, (Developments in Language Theory. Developments in Language Theory, Lecture Notes in Computer Science, vol. 9168 (2015)), 313-325 · Zbl 1386.68106 |
| [41] | Klimann, I.; Picantin, M.; Savchuk, D., Orbit automata as a new tool to attack the order problem in automaton groups, J. Algebra, 445, 433-457 (2016) · Zbl 1383.20018 |
| [42] | Lindgren, K.; Nordahl, M., Universal computation in simple one-dimensional cellular automata, Complex Systems, 4, 3, 299-318 (1990) · Zbl 0724.68072 |
| [43] | McCool, J., The order problem and the power problem for free product sixth-groups, Glasg. Math. J., 10, 1-9 (1969) · Zbl 0195.30602 |
| [44] | McCool, J., Unsolvable problems in groups with solvable word problem, Canad. J. Math., 22, 836-838 (1970) · Zbl 0216.08702 |
| [45] | Minsky, M. L., Size and Structure of Universal Turing Machines Using Tag Systems, Proceedings of Symposia on Pure Mathematics, vol. V, 229-238 (1962), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 0192.06601 |
| [46] | Neary, T.; Woods, D., Four small universal Turing machines, Fund. Inform., 91, 1, 123-144 (2009) · Zbl 1191.68307 |
| [47] | Ollinger, N.; Richard, G., Four states are enough!, Theoret. Comput. Sci., 412, 1-2, 22-32 (2011) · Zbl 1207.68217 |
| [48] | Olukoya, F., The growth rates of automaton groups generated by reset automata, 48 p |
| [49] | Rogozhin, Y., Small universal Turing machines, (Universal Machines and Computations, no. 2. Universal Machines and Computations, no. 2, Paris, 1995. Universal Machines and Computations, no. 2. Universal Machines and Computations, no. 2, Paris, 1995, Theoret. Comput. Sci., vol. 168 (1996)), 215-240 · Zbl 0874.68106 |
| [50] | Silva, P. V.; Steinberg, B., On a class of automata groups generalizing lamplighter groups, Internat. J. Algebra Comput., 15, 5-6, 1213-1234 (2005) · Zbl 1106.20028 |
| [51] | Smith, A. R., Simple computation-universal cellular spaces, J. ACM, 18, 339-353 (1971) · Zbl 0221.94071 |
| [52] | Steinberg, B., On some algorithmic properties of finite state automorphisms of rooted trees, (Algorithmic Problems of Group Theory, Their Complexity, and Applications to Cryptography. Algorithmic Problems of Group Theory, Their Complexity, and Applications to Cryptography, Contemporary Mathematics, vol. 633 (2015)), 115-123 · Zbl 1326.20037 |
| [53] | Šunić, Z.; Ventura, E., The conjugacy problem in automaton groups is not solvable, J. Algebra, 364, 148-154 (2012) · Zbl 1261.20034 |
| [54] | Sushchanskiĭ, V. I., Periodic p-groups of permutations and the unrestricted Burnside problem, Dokl. Akad. Nauk SSSR, 247, 3, 557-561 (1979), (Russian) · Zbl 0428.20023 |
| [55] | Turing, A. M., On computable numbers, with an application to the entscheidungsproblem, Proc. Lond. Math. Soc. (2), 42, 1, 230-265 (1936) · Zbl 0016.09701 |
| [56] | Żuk, A., Automata groups, (Topics in Noncommutative Geometry. Topics in Noncommutative Geometry, Clay Mathematics Proceedings, vol. 16 (2012)), 165-196 · Zbl 1332.20039 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
