zbMATH — the first resource for mathematics

A notion of effectiveness for subshifts on finitely generated groups. (English) Zbl 1356.68057
Summary: We generalize the classical definition of effectively closed subshift to finitely generated groups. We study classical stability properties of this class and then extend this notion by allowing the usage of an oracle to the word problem of a group. This new class of subshifts forms a conjugacy class that contains all sofic subshifts. Motivated by the question of whether there exists a group where the class of sofic subshifts coincides with that of effective subshifts, we show that the inclusion is strict for several groups, including recursively presented groups with undecidable word problem, amenable groups and groups with more than two ends. We also provide an extended model of Turing machine which uses the group itself as a tape and characterizes our extended notion of effectiveness. As applications of these machines we prove that the origin constrained domino problem is undecidable for any group of the form \(G \times \mathbb{Z}\) subject to a technical condition on \(G\) and we present a simulation theorem which is valid in any finitely generated group.

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
37B10 Symbolic dynamics
Full Text: DOI arXiv
[1] Aubrun, Nathalie; Sablik, Mathieu, Row-constrained effective sets of colourings in the 2-fold horocyclic tessellations of \(\mathbb{H}^2\) are sofic · Zbl 1433.37009
[2] Nathalie Aubrun, Jarkko Kari, Tiling problems on Baumslag-Solitar groups, preprint, 2013.
[3] Aubrun, Nathalie; Sablik, Mathieu, Simulation of effective subshifts by two-dimensional subshifts of finite type, Acta Appl. Math., 126, 35-63, (2013) · Zbl 1283.37014
[4] Ballier, Alexis; Stein, Maya, The domino problem on groups of polynomial growth, (2013) · Zbl 1386.37017
[5] Berger, Robert, The undecidability of the domino problem, (1966), American Mathematical Society · Zbl 0199.30802
[6] Boone, William W., The word problem, Proc. Natl. Acad. Sci. USA, 44, 1061-1065, (1958) · Zbl 0086.24701
[7] Tullio, Ceccherini-Silberstein; Coornaert, Michel, Cellular automata and groups, (2009), Springer · Zbl 1160.37317
[8] da Cunha, Aubrey, Turing machines on Cayley graphs, (Beklemishev, Lev D.; de Queiroz, Ruy, Logic, Language, Information and Computation, Lecture Notes in Computer Science, vol. 6642, (2011), Springer Berlin Heidelberg), 84-94 · Zbl 1326.68137
[9] François Dahmani, private communication.
[10] Dahmani, François; Yaman, Asli, Symbolic dynamics and relatively hyperbolic groups, Groups Geom. Dyn., 2, 2, 165-184, (2008) · Zbl 1169.20022
[11] Durand, Bruno; Romashchenko, Andrei E.; Shen, Alexander, Effective closed subshifts in 1D can be implemented in 2D, (Fields of Logic and Computation, (2010)), 208-226 · Zbl 1287.37012
[12] Gajardo, Anahí; Mazoyer, Jacques, One head machines from a symbolic approach, Theoret. Comput. Sci., 370, 1-3, 34-47, (2007) · Zbl 1118.68064
[13] Grigorchuk, Rostislav, Degrees of growth of finitely generated groups, and the theory of invariant means, Math. USSR, Izv., 48, 5, (1984)
[14] Hedlund, Gustav; Morse, Marston, Symbolic dynamics, Amer. J. Math., 60, 4, 815-866, (1938) · Zbl 0019.33502
[15] Hochman, Mike, On the dynamics and recursive properties of multidimensional symbolic systems, Invent. Math., 176, 1, 131-167, (2009) · Zbl 1168.37002
[16] Hochman, Mike; Meyerovitch, Tom, A characterization of the entropies of multidimensional shifts of finite type, Ann. of Math., 171, 3, 2011-2038, (2010) · Zbl 1192.37022
[17] Lind, Douglas A.; Marcus, Brian, An introduction to symbolic dynamics and coding, (1995), Cambridge University Press · Zbl 1106.37301
[18] Lyndon, Roger C.; Schupp, Paul E., Combinatorial group theory, (1977), Springer-Verlag · Zbl 0368.20023
[19] Novikov, Pyotr, On the algorithmic unsolvability of the word problem in group theory, Proc. Steklov Inst. Math., 44, 143, (1955), (in Russian)
[20] Salo, Ville; Törmä, Ilkka, Group-walking automata, (Cellular Automata and Discrete Complex Systems: 21st IFIP WG 1.5 International Workshop, AUTOMATA 2015, Proceedings, Turku, Finland, June 8-10, 2015, (2015)), 224-237 · Zbl 1435.37027
[21] Robinson, R. M., Undecidable tiling problems in the hyperbolic plane, Invent. Math., 44, 159-264, (1978) · Zbl 0354.50006
[22] Robinson, Raphael, Undecidability and nonperiodicity for tilings of the plane, Invent. Math., 12, 177-209, (1971) · Zbl 0197.46801
[23] Stallings, John R., On torsion-free groups with infinitely many ends, Ann. of Math., 88, 2, 312-334, (1968) · Zbl 0238.20036
[24] Asli Yaman, private communication.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.