On groups with EDT0L word problem
By: Alex Bishop , Murray Elder , Alex Evetts and more
Potential Business Impact:
Proves some math problems are too hard for computers.
We prove that the word problem for the infinite cyclic group is not EDT0L, and obtain as a corollary that a finitely generated group with EDT0L word problem must be torsion. In addition, we show that the property of having an EDT0L word problem is invariant under change of generating set and passing to finitely generated subgroups. This represents significant progress towards the conjecture that all groups with EDT0L word problem are finite (i.e. precisely the groups with regular word problem).
Similar Papers
On groups with EDT0L word problem
Group Theory
Groups with simple math problems can't be infinite.
On finite extensions of lamplighter groups
Group Theory
Answers math puzzles with tricky group rules.
Word problems and embedding-obstructions in cellular automata groups on groups
Group Theory
Makes computers solve harder puzzles faster.