We develop a qualitative classification of the dynamical behavior arising from iterated evolution of finite automata, with emphasis on the emergence of complex or apparently unpredictable behavior in automata with many states. We explain why automata with chaotic iterated behavior are of interest from a group-theoretic perspective.

Iterated Finite Automata

Infinite groups

In 1902, Burnside published a paper that is sometimes regarded as the beginning of the theory of infinite groups. In it, he asked whether there exists an infinite finitely generated group in which every element has finite order. This problem has a fascinating history, marked by the spectacular achievement of Adyan and Novikov in the 1960s. They proved the existence of an infinite group generated by two elements such that every element raised to the 665th power is the identity. It is still unknown what the smallest exponent is for which this statement holds.

Automata groups

In 1972, a theory of groups generated by finite automata emerged, together with a very simple construction of an infinite finitely generated group in which all elements have bounded order. While automata with a small number of states have been analyzed in detail, automata with a large number of states remain largely uncharted territory, and Mathematica is a unique tool for investigating them.

Iteration of automata

In this setting, a group element is defined by its action on a sequence over a finite alphabet. The function “IteratedFiniteAutomaton”, introduced by Wolfram, makes it possible to observe this action on arbitrarily long sequences. One can iterate this action in the same spirit as cellular automata. For group elements of finite order, the behavior is periodic, and there are no interesting pictures to display.
​

Non periodic orbits

By contrast, when the picture is not periodic, this indicates that the corresponding group element is not of finite order.
Out[]=
Out[]=

Chaotic behaviour

Groups in which all elements have infinite order are called torsion-free. For this class of groups, some conjectures were formulated almost a century ago and remain open. This may be due in part to limitations in the ways we construct groups. From this perspective, new examples exhibiting chaotic behavior may be especially interesting to investigate.
Out[]=
Out[]=
​

Open problems

In this context, let us mention the zero-divisor problem, formulated by Kaplansky in the 1950s. It concerns the group ring Z[G] of a torsion-free group group G, whose elements are formal finite sums of elements of G with integer coefficients. The conjecture states that the product of two nonzero elements of the group ring is never zero. This conjecture remains open for torsion-free groups, and even the special case that A(A−1) ≠0 for A∈Z[G], unless A=0 or A=1, is still open.

Concluding Remarks

We explain the interest of studying automata with chaotic iterated behavior from a group-theoretic perspective.

Acknowledgments

I would like to thank Stephen Wolfram for his suggestion to explore the ideas presented in his essay “Iterated Finite Automata”, as well as for the numerous inspiring discussions that accompanied this work.
​
The possibilities of the Wolfram Language could not have been better introduced to me than through the guidance of Pavel Hajek, whose explanations of why the IteratedFiniteAutomaton function needed to be updated were invaluable.

References

1
.
A. Zuk, Groupes engendrés par les automates - Séminaire Bourbaki, Astérisque 311, 2008, p. 141 – 174.
2
.
A. Zuk, Automata groups - Topics in noncommutative geometry, 165–196, Clay Math. Proc., 16, Amer. Math. Soc., Providence, RI, 2012.
3
.
A. Zuk, From partial differential equations to groups - ”Analysis and Geometry on Graphs and Manifolds”, Cambridge University Press, p. 368-381, 2020.

Code

There is a resource function due to Stephen Wolfram
In[]:=
ResourceFunction["IteratedFiniteAutomaton"]
We include a version suitable for the latest version of Wolfram language.

IteratedFiniteAutomaton


IteratedFiniteAutomatonPeriodicStop


IteratedFiniteAutomatonStateTransitions


IteratedFiniteAutomatonStateGraph


IteratedFiniteAutomatonColors


AI Disclosure

No generative AI tools were used in this project.

Cite This Notebook

“[Title of Community Post]”
by [Author Name]
Wolfram Community, [Date of publication on Community]