An automaton group with undecidable order and Engel problems
From MaRDI portal
Abstract: 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 [...[[g,h],h],...,h]$ is the identity or not. This solves a problem raised by Bartholdi.
Recommendations
- The word and order problems for self-similar and automata groups
- Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness
- Algorithmic decidability of Engel's property for automaton groups
- Orbit automata as a new tool to attack the order problem in automaton groups
Cites work
- A concrete view of Rule 110 computation
- A connected 3-state reversible Mealy automaton cannot generate an infinite Burnside group
- Algorithmic decidability of Engel's property for automaton groups
- Amenable semigroups
- An automaton group with undecidable order and Engel problems
- Automata groups.
- Automata, dynamical systems, and groups
- Automaton semigroup constructions.
- Automaton semigroups: new constructions results and examples of non-automaton semigroups
- Automaton semigroups: the two-state case.
- Cellular automata, tilings and (un)computability
- Connected reversible Mealy automata of prime size cannot generate infinite Burnside groups
- Decidability and undecidability in cellular automata
- Finitely Presented Groups with Word Problems of Arbitrary Degrees of Insolubility
- Four Small Universal Turing Machines
- Four states are enough!
- Freeness of automaton groups vs boundary dynamics
- scientific article; zbMATH DE number 4195207 (Why is no real title available?)
- scientific article; zbMATH DE number 3667062 (Why is no real title available?)
- scientific article; zbMATH DE number 3497806 (Why is no real title available?)
- scientific article; zbMATH DE number 3220420 (Why is no real title available?)
- scientific article; zbMATH DE number 3305022 (Why is no real title available?)
- scientific article; zbMATH DE number 3389248 (Why is no real title available?)
- ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
- On Burnside's problem on periodic groups
- On Computable Numbers, with an Application to the Entscheidungsproblem
- On some algorithmic properties of finite state automorphisms of rooted trees.
- On the complexity of the word problem for automaton semigroups and automaton groups
- On the conjugacy problem for finite-state automorphisms of regular rooted trees. With an appendix by Raphaël M. Jungers
- On torsion-free semigroups generated by invertible reversible Mealy automata
- Orbit automata as a new tool to attack the order problem in automaton groups
- Periodicity and Immortality in Reversible Computing
- Permutive one-way cellular automata and the finiteness problem for automaton groups
- Self-similarity and branching in group theory.
- Simple Computation-Universal Cellular Spaces
- Small universal Turing machines
- Some undecidability results for asynchronous transducers and the Brin-Thompson group 2V
- Subgroups of finitely presented groups
- The conjugacy problem in automaton groups is not solvable.
- The finiteness problem for automaton semigroups is undecidable.
- The Nilpotency Problem of One-Dimensional Cellular Automata
- The order problem and the power problem for free product sixth-groups
- The word and order problems for self-similar and automata groups
- Theory of cellular automata: a survey
- Universality in elementary cellular automata
- Unsolvable Problems in Groups With Solvable Word Problem
Cited in
(27)- An automaton group with undecidable order and Engel problems
- The order of a group machine
- On the existence of free subsemigroups in reversible automata semigroups
- Corrigendum to: ``Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness
- Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness
- Generic properties in some classes of automaton groups
- Engel elements in some fractal groups
- Bounds on orders of linear automata
- On a class of poly-context-free groups generated by automata
- An automaton group with \textsf{PSPACE}-complete word problem
- Some undecidability results for asynchronous transducers and the Brin-Thompson group 2V
- The group of reversible Turing machines
- On Turing machines, groupoids, and Atiyah problem
- On orbits and the finiteness of bounded automaton groups
- On the orbits of automaton semigroups and groups
- Graph automaton groups
- The lamplighter group of rank two generated by a bireversible automaton
- Algorithmic decidability of Engel's property for automaton groups
- A new hierarchy for automaton semigroups
- The word problem for finitary automaton groups
- Undecidability of automorphism groups
- Maximal finite orders of linear automata over an arbitrary field
- The freeness problem for automaton semigroups
- The finiteness problem for automaton semigroups of extended bounded activity
- The word and order problems for self-similar and automata groups
- On the structure theory of partial automaton semigroups
- Orbit automata as a new tool to attack the order problem in automaton groups
This page was built for publication: An automaton group with undecidable order and Engel problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1693094)
