[ LLM Generated ]

Transitions between formalisms

Claude Fable 5
Abstract.
An iterated finite automaton is presented in three ways — as a wreath recursion, as a Mealy transducer, and as a rule list with its numeric code — and the presentations carry the same information: the conversions are mutually inverse up to the naming of states, verified on all 64 invertible rule lists on 2 states and 2 colors. The published wreath recursion of the Grigorchuk automaton has numeric code 8950703898 on 5 states and 2 colors. The five states of the Grigorchuk automaton have orders 2, 2, 2, 2, 1 in the automaton group, each decided by the word problem rather than tested level by level. The evolution of the adding machine on
n
cells from the zero tape has period exactly
n
2
, verified for all
n≤12
.
1
.

Definitions

Definition
1
.
1
.
Fix an integer
k≥2
and let
X={0,…,k-1}
. The rooted
k
-ary tree
T
k
is the graph whose vertices are the finite words over
X
, with an edge from
w
to
wx
for every word
w
and every letter
x∈X
. The root is the empty word.
Definition
1
.
2
.
An automorphism of
T
k
is a bijection of the vertex set that preserves adjacency and the root. Every automorphism preserves each level, so it acts on the words of length
L
for every
L
, and it is determined by its action on the infinite sequences over
X
.
Definition
1
.
3
.
The wreath decomposition of an automorphism
g
of
T
k
consists of a permutation
σ
of
X
— the action of
g
on the first letter — and the automorphisms
g
0
,…,
g
k-1
, where
g
x
is the automorphism induced by
g
on the subtree below the vertex
x
. We write
g=(
g
0
,…,
g
k-1
)σ
and the action on a sequence is
g(
x
1
x
2
x
3
…)=σ(
x
1
)
g
x
1
(
x
2
x
3
…).
Definition
1
.
4
.
An automaton is a finite set
S
of automorphisms of
T
k
closed under sections: for every
g∈S
and every
x∈X
the section
g
x
lies in
S
. The wreath presentation of the automaton assigns to each
g∈S
its permutation
σ
and its list of sections.
Definition
1
.
5
.
The Mealy presentation of an automaton with state set
S
assigns to each state
g
and each input letter
x
the pair consisting of the output letter
σ(x)
and the next state
g
x
. A state is a transducer that reads one letter and emits one letter.
Definition
1
.
6
.
The rule list of an automaton with states indexed
1,…,s
is the set of pairs
{r,i}→{f,o}
, one for each state index
r
and each input letter
i
, where
o
is the output letter and
f
the index of the next state.
Definition
1
.
7
.
The numeric code of a rule list on
s
states and
k
colors is the integer
m
whose
sk
digits in base
sk
, one digit per state and input letter, encode the transition
{r,i}→{f,o}
by the digit
(f-1)k+o
. The pair
{m,{s,k}}
determines the rule list, and there are
sk
(sk)
rule lists on
s
states and
k
colors.
Example
1
.
8
.
The number of steps until a row repeats, over all 256 rule lists on 2 states and 2 colors, from the zero tape of length 8. The maximum 256 is attained by exactly four rule lists — the codes 52, 62, 148 and 158 — and the four form two classes under renaming of states and colors, represented by 52 and 62; the adding machine 62 is not a renaming of 52.
stepCounts=Table[Length@IteratedFiniteAutomatonPeriodicStop[{m,{2,2}},1,ConstantArray[0,8],300]-1,{m,0,255}];​​maximal=Flatten@Position[stepCounts,256]-1;​​{maximal,Union[CanonicalAutomatonCode[{#,{2,2}}]&/@maximal]}
{{52,62,148,158},{{52,{2,2}},{62,{2,2}}}}
ArrayPlot[Partition[Log2@stepCounts,16],ColorFunction->"Pastel",ColorFunctionScaling->True,Frame->False,PlotLegends->BarLegend[Automatic,LegendLabel->"log2 steps"],ImageSize->320,PlotLabel->"steps until a row repeats, all 256 rule lists"]
log2 steps
BarChart[Values@KeySort@Counts@stepCounts,ChartLabels->Keys@KeySort@Counts@stepCounts,ChartStyle->"Pastel",AxesLabel->{"steps","rule lists"},ImageSize->380]
Remark
1
.
9
.
The three presentations carry the same information, so a statement about one is a statement about all three. The wreath presentation exposes the group element, the Mealy presentation exposes the transducer, and the rule list indexes the states by integers. Passing to the rule list forgets the state names, which is why the conversions from the wreath and Mealy presentations are surjective and not injective, while the numeric code is a bijection with the rule lists of a fixed signature.
2
.

Conversions and identities

Claim
2
.
1
.
For every invertible rule list on 2 states and 2 colors, the composite rule list
⟶
wreath presentation
⟶
rule list is the identity, on all 64 invertible codes. On the adding machine the wreath recursion and the Mealy transducer with the same transitions produce the same rule list.
Example
2
.
2
.
The composite over the 64 invertible rule lists, the agreement of the two conversions on the adding machine, and the 24 classes of the 64 invertible rule lists under renaming of states and colors: 4 classes of size 1, 10 of size 2, 10 of size 4.
{AllTrue[InvertibleAutomatonCodes[{2,2}],m|->AutomatonCodeFromRule[IteratedFiniteAutomatonFromWreath[AutomatonWreathRecursion[{m,{2,2}}],1]["Rule"]]==={m,{2,2}}],Sort@adding["Rule"]===Sort@addingMealy["Rule"]}
{True,True}
classSizes=Values@Counts[CanonicalAutomatonCode[{#,{2,2}}]&/@InvertibleAutomatonCodes[{2,2}]];​​BarChart[Values@KeySort@Counts@classSizes,ChartLabels->Keys@KeySort@Counts@classSizes,ChartStyle->"Pastel",AxesLabel->{"class size","classes"},ImageSize->300,PlotLabel->"invertible rule lists under renaming"]
Claim
2
.
3
.
The wreath recursion
a=σ
,
b=(a,c)
,
c=(a,d)
,
d=(1,b)
of the Grigorchuk automaton has numeric code 8950703898 on 5 states and 2 colors: the two presentations have the same transition diagram and the same evolution.
Example
2
.
4
.
The transition diagrams of the code and of the converted wreath recursion, equal as edge sets, and the two evolutions from the same initial tape.
{Sort@EdgeList@IteratedFiniteAutomatonStateGraph[{8950703898,{5,2}}]===Sort@EdgeList@IteratedFiniteAutomatonStateGraph[grigorchuk["Rule"]],IteratedFiniteAutomaton[{8950703898,{5,2}},1,PadRight[{1},20],12]===IteratedFiniteAutomaton[grigorchuk["Rule"],1,PadRight[{1},20],12]}
{True,True}
GraphicsRow[{IteratedFiniteAutomatonStateGraph[{8950703898,{5,2}}],IteratedFiniteAutomatonStateGraph[grigorchuk["Rule"]]},ImageSize->460]
Claim
2
.
5
.
The five states of the Grigorchuk automaton have orders 2, 2, 2, 2, 1 in the automaton group, each decided by the word problem:
m
w
=1
in the group exactly when every word in the section closure of
m
w
fixes the first letter, a finite computation. In particular
2
a
=1
, so evolving any tape twice returns it, at every tape length.
Example
2
.
6
.
The orders of the five states in the automaton group, and the order of
a
on the tapes of length
L
for
L=1,…,8
— constant at 2, as the order in the group requires.
{Table[AutomatonWordOrder[{8950703898,{5,2}},{s},4],{s,5}],AutomatonWordOrders[{8950703898,{5,2}},{1},Range@8]}
{{2,2,2,2,1},{2,2,2,2,2,2,2,2}}
Conjecture
2
.
7
.
For every
n≥1
the evolution of the adding machine on
n
cells from the zero tape has period exactly
n
2
. Status: verified for all
n≤12
; the evolution is the binary counter with the least significant bit on the left, so a proof should be an induction on
n
.
Example
2
.
8
.
The period on
n
cells for
n=1,…,12
against
n
2
, and the evolution on 6 cells: the binary counter.
periods=Table[{n,Length@IteratedFiniteAutomatonPeriodicStop[adding["Rule"],1,ConstantArray[0,n],2^n+2]-1},{n,12}];​​{ListLogPlot[periods,Joined->True,Mesh->All,PlotStyle->RGBColor[0.55,0.72,0.88],MeshStyle->RGBColor[0.35,0.55,0.75],AxesLabel->{"n","period"},ImageSize->300],AllTrue[periods,p|->Last@p==2^First@p]}

,True
ArrayPlot[IteratedFiniteAutomaton[adding["Rule"],1,ConstantArray[0,6],64],ColorRules->IteratedFiniteAutomatonColors[2],Mesh->True,MeshStyle->GrayLevel[0.85],ImageSize->200,PlotLabel->"adding machine on 6 cells"]
3
.

Questions

4
.

References

[Zuk2026]
\.{Z, Iterated Finite Automata, 2026, https://community.wolfram.com/groups/-/m/t/3761828
[Wolfram2003]
Wolfram, Stephen, Iterated finite automata, 2003, https://www.stephenwolfram.com/publications/iterated-finite-automata/
[Nekrashevych2005]
Nekrashevych, Volodymyr, Self-Similar Groups, 2005, https://doi.org/10.1090/surv/117
[GNS2000]
Grigorchuk, Rostislav I. and Nekrashevych, Volodymyr V. and Sushchanskii, Vitaly I., Automata, dynamical systems, and groups, Proceedings of the Steklov Institute of Mathematics, 2000, https://www.mathnet.ru/eng/tm515
[Zuk2008]
\.{Z, Groupes engendr\'{e, 2008, https://www.numdam.org/book-part/AST_2008__317__141_0/
5
.

Symbols

Constructions:
◼
  • CanonicalAutomatonCode — the least numeric code under renaming of states and colors
    • ◼
  • InvertibleAutomatonCodes — the codes of the invertible rule lists of a signature
    • Operations:
    ◼
  • IteratedFiniteAutomaton — the evolution of a rule list from an initial tape
    • ◼
  • IteratedFiniteAutomatonEvolve — the evolution of a converted automaton
    • ◼
  • IteratedFiniteAutomatonPeriodicStop — the evolution stopped at the first repeated row
    • Invariants and predicates:
    ◼
  • AutomatonWordOrders — the orders of a word on the tapes of each given length
    • ◼
  • AutomatonWordIdentityQ — whether a word is the identity of the automaton group
    • Visualisation: