[LLM Generated]

Periodicity of iterated finite automata

Claude Opus 5
Abstract.
We study when the evolution of an iterated finite automaton on a finite tape closes into a cycle, and how the period relates to the order of the acting group element. In the Definitions section we define the one-pass map on tapes of length L, its orbit length, transient and period, and the level permutations of the automaton's states. In the Classification section we identify the evolution on length-L tapes with the action of a state on level L of the rooted tree, deduce that invertible automata have no transient and that every period divides the level order, and give the census over the 256 automata on 2 states and 2 colors that separates these predicates. In the Conjectures section we state that the adding machine has period exactly 2 to the L for every initial condition, that the lamplighter automaton's level order at level L is 2 to the ceiling of the base-2 logarithm of L + 1, and that the automata attaining maximal period on the zero tape are the same four codes for every L. In the Demonstrations section we exhibit each function on the adding machine and the lamplighter automaton.
1
.

Setup

PacletInstall["https://www.wolframcloud.com/obj/hajek_pavel/IteratedFiniteAutomaton.paclet",​​ForceVersionInstall->True];​​Needs["WolframInstitute`IteratedFiniteAutomaton`"];
SeedRandom[1];
Row[{"IteratedFiniteAutomaton ",PacletObject["WolframInstitute/IteratedFiniteAutomaton"]["Version"],​​" — built ",DateString["ISODate"]}]
IteratedFiniteAutomaton 0.2.0 — built 2026-07-27
The adding machine and the lamplighter automaton are the two running examples, both on 2 states and 2 colors. They are built from their wreath recursions so the notebook is self-contained.
IteratedFiniteAutomatonFromWreath
returns an association, and the group-layer functions consume a rule list, so the rule is extracted explicitly.
addingWreath=IteratedFiniteAutomatonFromWreath[<|​​"a"->{{1,0},{"id","a"}},​​"id"->{{0,1},{"id","id"}}|>,"a"];​​adding=addingWreath["Rule"];
lamplighterWreath=IteratedFiniteAutomatonFromWreath[<|​​"a"->{{1,0},{"a","b"}},​​"b"->{{0,1},{"a","b"}}|>,"a"];​​lamplighter=lamplighterWreath["Rule"];
Column[{AutomatonCodeFromRule[adding],AutomatonCodeFromRule[lamplighter]}]
{62,{2,2}}
{156,{2,2}}
The transient and period of one orbit, read off the list
IteratedFiniteAutomatonPeriodicStop
returns: its last row is the first repeated row, so the position of that row among the earlier ones splits the orbit into transient and period.
transientPeriod[rule_,init_,cap_]:=​​Module[{orbit=IteratedFiniteAutomatonPeriodicStop[rule,init,cap],p},​​p=First[FirstPosition[Most[orbit],Last[orbit]]];​​{p-1,Length[orbit]-p}];
2
.

Functions

The symbols this notebook uses, grouped by role.
Constructions
◼
  • IteratedFiniteAutomatonFromWreath
    — wreath recursion to rule list
    • ◼
  • AutomatonCodeFromRule
    — rule list to numeric code
    • ◼
  • AutomatonRuleFromCode
    — numeric code to rule list
    • Operations
    ◼
  • IteratedFiniteAutomaton
    — evolve a rule list or numeric code for t steps
    • ◼
  • IteratedFiniteAutomatonPeriodicStop
    — evolve until a row repeats
    • ◼
  • AutomatonLevelPermutations
    — each state as a permutation of the k to the L vertices at level L
    • Invariants and predicates
    ◼
  • AutomatonWordOrders
    — order of a word in the level quotients, one level at a time
    • ◼
  • InvertibleAutomatonQ
    — the outputs permute the colors at every state
    • ◼
  • PermutationOrder
    — order of a permutation given in image form
    • Visualisation
    ◼
  • IteratedFiniteAutomatonStateGraph
    — the transition diagram
    • ◼
  • IteratedFiniteAutomatonColors
    — color rules for k symbols
    • 3
    .

    Definitions

    Definition
    3
    .
    1
    .
    Fix a rule list on s states and k colors and an initial state index r. For a tape x of length L over the color alphabet X = {0, …, k−1}, the one-pass map F sends x to the tape obtained by reading x left to right from state r, emitting one color per cell. We write F(x) for the image and Fⁿ for the n-fold iterate.
    Definition
    3
    .
    2
    .
    The orbit of x is the sequence x, F(x), F²(x), …. Since the tape space is finite, there are integers t ≥ 0 and p ≥ 1 for which iterating t + p times agrees with iterating t times. The transient τ(x) is the least such t and the period π(x) is the least such p. The orbit length is ℓ(x) = τ(x) + π(x) + 1, the number of rows up to and including the first repeated row.
    Definition
    3
    .
    3
    .
    The automaton is periodic at the initial condition x if τ(x) = 0, that is, the orbit of x returns to x. It is periodic at all initial conditions with period dividing n if Fⁿ is the identity on the tapes of length L.
    Definition
    3
    .
    4
    .
    For a rule list on s states and k colors, the level-L permutation of state r is the permutation of the k to the L words of length L induced by reading each word from state r. Its order is the level-L order of r, and the order of r as an automorphism of the rooted k-ary tree is the supremum of its level orders over all L.
    Remark
    3
    .
    5
    .
    The one-pass map on tapes of length L is exactly the level-L permutation of the initial state: reading a word of length L and emitting a word of length L is the action of the state on level L of the tree. Every statement about the evolution on a fixed tape length is therefore a statement about a finite permutation, and every statement about all tape lengths at once is a statement about a tree automorphism. This identification is what the rest of the notebook uses.
    3
    .
    1
    .

    Example

    The adding machine's one-pass map on tapes of length L is a bijection, and its cycle type agrees with that of the level-L permutation, for L = 1, …, 8.
    evolutionImages[rule_,L_]:=Table[FromDigits[IteratedFiniteAutomaton[rule,1,IntegerDigits[n,2,L]],2],{n,0,2^L-1}];
    ListStepPlot[​​Table[{PermutationOrder[Ordering[Ordering[evolutionImages[adding,L]]]],​​PermutationOrder[AutomatonLevelPermutations[adding,L][1]]},{L,8}]//Transpose,​​DataRange->{1,8},PlotLegends->{"evolution","level permutation"},​​AxesLabel->{"L","order"},ScalingFunctions->"Log2",Filling->Axis,Mesh->All]
    evolution
    level permutation
    4
    .

    Classification

    The predicates on a rule list, and how they relate. Both implications hold at every tape length, and neither converse does:
    invertible(rule)⟹τ(x)=0foreveryx∈
    L
    X
    ord(r)=n<∞⟹π(x)dividesnforeveryLandeveryx
    The second converse fails at the adding machine, whose periods are finite at every tape length while its order is infinite; the first fails because a non-invertible rule can still act injectively on a particular tape length.
    Observation
    4
    .
    1
    .
    If the automaton is invertible then F is a bijection of the finite set of tapes of length L, so every orbit is purely periodic and τ(x) = 0 for every x. Conversely a non-invertible automaton can have transient as long as the tape.
    Observation
    4
    .
    2
    .
    For an invertible automaton, π(x) divides the level-L order of the initial state, by Lagrange's theorem applied to the cyclic group generated by the level-L permutation.
    The census over all 256 rule codes on 2 states and 2 colors, on the zero tape of length 8, backs both statements and separates invertibility from the rest.
    invertibleCodes=Select[Range[0,255],InvertibleAutomatonQ[{#,{2,2}}]&];​​Length[invertibleCodes]
    64
    transients=AssociationMap[​​code|->First[transientPeriod[{code,{2,2}},ConstantArray[0,8],600]],​​Range[0,255]];
    ArrayPlot[Partition[Values[transients],16],​​ColorFunction->"Pastel",ColorFunctionScaling->True,Frame->False,​​PlotLegends->Automatic,PlotLabel->"transient on the zero tape, L = 8, code 0 … 255"]
    BarChart[​​{Max[Lookup[transients,invertibleCodes]],Max[Lookup[transients,Complement[Range[0,255],invertibleCodes]]]},​​ChartLabels->{"invertible","not invertible"},ChartStyle->"Pastel",​​AxesLabel->{None,"greatest transient"}]
    Question
    4
    .
    3
    .
    Periodicity at every initial condition for each fixed L does not imply that the acting element has finite order. The adding machine is periodic at every initial condition of every length, with period 2 to the L, and these periods are unbounded, so the element has infinite order. Is there a rule list on 2 states and 2 colors whose level orders are unbounded but not eventually a power of 2?
    Conjecture
    5
    .
    1
    .
    For every L ≥ 1 and every initial condition x of length L over two colors, the adding machine has τ(x) = 0 and π(x) = 2 to the L. Status: verified up to L = 9.
    The orbit length takes a single value, 2 to the L plus one, across all initial conditions of length L, for each L up to 9.
    Conjecture
    5
    .
    2
    .
    For every L ≥ 1 the level-L order of the generator a of the lamplighter automaton is 2 to the ceiling of the base-2 logarithm of L + 1. Status: verified up to L = 16.
    The level orders plateau and then double; against the formula they agree at every level up to 16.
    Conjecture
    5
    .
    3
    .
    For every L ≥ 4 the rule codes on 2 states and 2 colors attaining the maximal orbit length, 2 to the L plus one, on the zero tape are exactly 52, 62, 148 and 158. Status: verified for 4 ≤ L ≤ 10.
    The maximal-period codes are the same four at every tape length tested; the adding machine is code 62.
    6
    .

    IteratedFiniteAutomaton

    The evolution for a given number of steps, as a list of rows.
    The evolution up to the first repeated row, capped at t steps. The returned length is the transient plus the period plus one.
    8
    .

    AutomatonWordOrders

    The order of a word in the generators, computed in each level quotient in turn. A constant value across well-separated levels is evidence of finite order, not a proof, since orders can plateau and then resume.
    9
    .

    AutomatonLevelPermutations

    Each state as a permutation of the k to the L words of length L, in image form.
    The transition diagram of the rule list.
    12
    .

    Literature