[LLM Generated]

Constructive families of many-state automata

Claude Opus 5

Abstract.

We study iterated finite automata with many states, where the space of automata is too large to enumerate and the automata have to be constructed. In the Definitions section we define the space and its size, three families of automata parameterized by the state count — a cascade of odometers, a program on a sliding window, and the composition of two automata — and the two properties by which we separate them, being finitary and being active. In the Classification section we place the three families in the lattice of properties, compute the group each generates as an exact order in the level quotient rather than as a ball count, and census the whole design space of window programs at window lengths 1, 2 and 3. In the Conjectures section we state that the cascade over two symbols generates the full automorphism group of the truncated tree, verified to 6 states, and that the window program generates an infinite group, verified through level 5 at window lengths 1 to 3, and we record that the composition automaton multiplies the state count while its group is contained in the group of its factors, which is a proposition and not a conjecture. In the Cost section we measure the largest level and the largest ball radius each invariant of the paclet reaches inside a fixed time budget as the state count grows, and read off which parameter each invariant is expensive in. In the Demonstrations section we exhibit the three constructions and the pictures they make. We then ask, and do not answer, whether many states can carry a group-ring counterexample: no automaton among the ones constructed here is even a torsion-free candidate.

Setup

PacletInstall["https://www.wolframcloud.com/obj/hajek_pavel/IteratedFiniteAutomaton.paclet",ForceVersionInstall->True];Needs["WolframInstitute`IteratedFiniteAutomaton`"];

Row[{"IteratedFiniteAutomaton ",PacletObject["WolframInstitute/IteratedFiniteAutomaton"]["Version"]," — built ",DateString["ISODate"]}]

IteratedFiniteAutomaton 0.4.0 — built 2026-07-28

The exact order of the group an automaton generates in the automorphism group of the tree truncated at a level. The paclet's

AutomatonElementCount

counts the elements a ball of words reaches, which is a lower bound; this is the group, computed from the generating permutations by Schreier–Sims. It belongs to the notebook rather than to the paclet because it is a question about a permutation group and not about an automaton.

levelGroupOrder[rule_,level_]:=With[{perms=Values@AutomatonLevelPermutations[rule,level]},GroupOrder@PermutationGroup[PermutationCycles/@DeleteCases[perms,Range[Length@First@perms]]]];

The largest value of a knob — a level, a ball radius — for which one measurement of an invariant fits in a time budget. The cost of every invariant here is monotone in its knob, so the first failure is the frontier.

SetAttributes[measure,HoldFirst];measure[expression_,budget_]:=With[{result=TimeConstrained[First@AbsoluteTiming[expression],budget,$Aborted]},If[result===$Aborted,Missing["OverBudget"],result]];frontier[budget_,run_,knobs_]:=Module[{affordable={}},Do[If[MissingQ[measure[run[knob],budget]],Break[],AppendTo[affordable,knob]],{knob,knobs}];If[affordable==={},0,Max[affordable]]];

Functions

Constructions:

◼

AutomatonAdderCascade

— the cascade of odometers on s states

◼

AutomatonWindowProgram

— the program on the window of the m symbols last read

◼

AutomatonProduct

— the composition automaton on the pairs of states

◼

AutomatonRuleFromCode

— the rule of a numbered automaton

◼

IteratedFiniteAutomatonFromWreath

— a wreath recursion as a rule

Evolution and its pictures:

◼

IteratedFiniteAutomaton

— the evolution of a tape

◼

IteratedFiniteAutomatonStateGraph

— the Moore diagram

◼

IteratedFiniteAutomatonStateSubgraph

— the part of the diagram one tape traverses

◼

IteratedFiniteAutomatonStateSubgraphFamily

— that part over all tapes of a length

◼

IteratedFiniteAutomatonsByInitialCondition

— one evolution picture per tape

Invariants and predicates:

◼

InvertibleAutomatonQ

— the outputs permute the symbols at every state

◼

CanonicalAutomatonCode

— the least code under relabelling states and symbols

◼

AutomatonLevelPermutations

— each state as a permutation of the vertices at a level

◼

AutomatonWordOrders

— the order of a word at each of several levels

◼

AutomatonElementCount

— the elements a ball of words reaches in a level quotient

◼

AutomatonGroupFingerprint

— commutativity and ball growth of a level quotient

◼

AutomatonNucleus

— the sections of a ball, by depth

◼

AutomatonTorsionFreeCandidateQ

— no word's order has stopped growing

◼

AutomatonWreathRecursion

— the wreath presentation, as a printable string

◼

GroupRingZeroDivisorSurvival

— elements of the group ring with a nonzero annihilator at every level

Pictures of an element:

◼

AutomatonTreePortrait

— the tree with each vertex coloured by the section there

◼

AutomatonBoundaryGraph

— the permutation of the vertices at a level, as its functional graph

Definitions

Definition

An iterated finite automaton on s states over k symbols is a Mealy transducer with state set {1, ..., s}, symbol set {0, ..., k − 1}, transition function δ and output function λ, presented as the rule list of pairs {q, x} → {δ(q, x), λ(q, x)}. It is invertible when x ↦ λ(q, x) is a permutation for every state q, and then each state acts as an automorphism of the rooted k-ary tree, with the group generated by the states written G(A).

Remark

The space of automata on s states over k symbols has (s k)^(s k) elements, so it is enumerable at (2, 2) and (3, 2), where every exhaustive result of this project lives, and not at (4, 2) and beyond. The many-state regime is therefore not a larger sweep but a construction followed by a verification.

ListLogPlot[Table[(s2)^(s2),{s,2,8}],DataRange->{2,8},Joined->True,Mesh->All,ImageSize->420,AxesLabel->{"states s","automata on s states, 2 symbols"},PlotStyle->RGBColor[0.55,0.75,0.9],Epilog->{RGBColor[0.85,0.5,0.5],Dashed,Line[{{2,Log[10^10]},{8,Log[10^10]}}],Text[Style["a sweep of this project's size",9],{5.5,Log[3*10^10]}]}]

Construction

The adder cascade on s states over k symbols,

AutomatonAdderCascade[s, k]

, advances the symbol it reads at every state and passes the carry one state along, the carry dying in the identity state s: δ(i, x) = s and λ(i, x) = x + 1 for i < s and x < k − 1; δ(i, k − 1) = i + 1 and λ(i, k − 1) = 0 for i < s; δ(s, x) = s and λ(s, x) = x.

Construction

The window program of length m over k symbols with active set A,

AutomatonWindowProgram[m, A, k]

, has one state per word w of length m, so s = k^m, and reads δ(w, x) = w₂ ⋯ w_m x, λ(w, x) = x + 1 mod k when w ∈ A and λ(w, x) = x otherwise. One step of the evolution is then the sliding-block code that advances a symbol exactly when the m symbols before it form a word in A. The default active set is the single all-(k − 1) word, which is the carry rule of the odometer.

Construction

The composition automaton of A and B over a common symbol set,

AutomatonProduct[A, B]

, has state set the pairs, with {p, q} numbered (p − 1) s_B + q, and reads δ({p, q}, x) = {δ_A(p, x), δ_B(q, λ_A(p, x))}, λ({p, q}, x) = λ_B(q, λ_A(p, x)).

Definition

A tree automorphism is finitary of depth d when its section at every vertex of depth d is the identity; equivalently its permutation of the vertices at any level L ≥ d moves whole blocks of k^(L−d) vertices. An automaton is finitary of depth d when every one of its states is.

Definition

The activity of a state q at depth d is the number of vertices of depth d whose section of q permutes its symbols. An automaton is bounded when the activity of every state is bounded in d, and we call it exponentially active when the activity grows like k^d.

Classification

The three properties order the families. Being finitary of depth d puts the group inside the automorphism group of the tree truncated at depth d, which is finite; a finite nontrivial group has torsion; and torsion refutes a group-ring counterexample of Kaplansky type before any search runs.

finitary of depth d⟹G(A) ⊆ Aut(T_d) finite⟹G(A) has torsion⟹no Kaplansky candidate

The cascade sits at the left of that chain and the window program off it entirely.

blockInflationQ[rule_,state_,depth_,level_]:=With[{deep=AutomatonLevelPermutations[rule,level][state],shallow=AutomatonLevelPermutations[rule,depth][state],k=Length@Union[rule[[All,1,2]]]},deep===Flatten@Table[(shallow[[j]]-1)k^(level-depth)+Range[k^(level-depth)],{j,Length[shallow]}]];

Grid[Prepend[Table[{s,InvertibleAutomatonQ[AutomatonAdderCascade[s]],AllTrue[Range[s],blockInflationQ[AutomatonAdderCascade[s],#,s-1,s]&],Table[Last@AutomatonWordOrders[AutomatonAdderCascade[s],{i},{s}],{i,s}],levelGroupOrder[AutomatonAdderCascade[s],s-1],AutomatonTorsionFreeCandidateQ[AutomatonAdderCascade[s],2,Range[5]]},{s,2,6}],{"s","invertible","finitary of depth s−1","orders of the states","|G|","torsion-free candidate"}],Frame->All,FrameStyle->RGBColor[0.8,0.82,0.85],Background->{None,{RGBColor[0.93,0.95,0.97]}},Alignment->Left,ItemSize->Automatic]

s	invertible	finitary of depth s−1	orders of the states	\|G\|	torsion-free candidate
2	True	True	{2,1}	2	False
3	True	True	{4,2,1}	8	False
4	True	True	{8,4,2,1}	128	False
5	True	True	{16,8,4,2,1}	32768	False
6	True	True	{32,16,8,4,2,1}	2147483648	False

The window program is not finitary at any depth, and its level quotients keep growing.

windowOrders=Table[m->Table[levelGroupOrder[AutomatonWindowProgram[m],level],{level,5}],{m,3}];ListLogPlot[Last/@windowOrders,Joined->True,Mesh->All,ImageSize->440,PlotStyle->{RGBColor[0.55,0.75,0.9],RGBColor[0.6,0.8,0.6],RGBColor[0.95,0.7,0.45]},AxesLabel->{"level","order of the level quotient"},PlotLegends->Placed[{"m = 1, s = 2","m = 2, s = 4","m = 3, s = 8"},Right],PlotLabel->"the window program does not stabilize in the level"]

Observation

The window program of length 1 over two symbols is the automaton a = (a, b), b = σ(a, b) of Grigorchuk and Żuk, whose group is the lamplighter group [GrigorchukZuk2001]; it is not the adding machine, which its carry rule resembles.

The activity separates the families in the other direction: the cascade's states are silent below their depth, while every state of a window program is active on a fixed fraction of every level, so no criterion for amenability by activity reaches them.

A window program is a subset of the k^m windows, so at window length m there are 2^(k^m) − 1 nonempty programs on k^m states — a space that grows fast but is searchable where the ambient (s k)^(s k) is not. We census it at m = 1, 2, 3 over two symbols: 1, 15 and 255 programs on 2, 4 and 8 states.

Conjecture

For every s ≥ 2 the adder cascade on s states over two symbols generates the whole automorphism group of the tree truncated at depth s − 1, of order 2^(2^(s−1) − 1). Over k symbols it generates the iterated wreath product of s − 1 copies of the cyclic group of order k, of order k^((k^(s−1) − 1)/(k − 1)), which is the whole automorphism group exactly when k = 2. Status: verified for s ≤ 6 and k ≤ 3 by exact group order.

Conjecture

For every m ≥ 1 the window program of length m over two symbols with the all-ones active set generates an infinite group. Status: verified through level 5 for m ≤ 3, in the sense that the level quotients are strictly increasing there; proved for m = 1, where the group is the lamplighter group [GrigorchukZuk2001].

Remark

The last column is not a counterexample and must not be read as one: every group in the table has torsion, so its group ring has zero divisors for the reason that an element g of order n gives (1 + g + ⋯ + g^(n−1))(1 − g) = 0, and the search finding them is the control that says the search works. A counterexample requires the third column to be True and the fourth to be nonzero at once, and no row does both.

The cost of an invariant in the state count

Every word-based invariant is linear in the size of the ball of radius r on s generators, which is (2 s)(2 s − 1)^(r−1), and every level-based invariant is linear in k^L. So the state count and the level enter the cost through different factors, and an invariant is expensive in whichever of them its parameter is.

Observation

The level-based invariants — the level permutations, the orders of one word — lose nothing as s grows, because s enters their cost linearly while the level enters it as k^L; at a budget of thirty seconds the level permutations reach level 20 at 2 states and at 32 states alike. The radius-based invariants lose a radius roughly every time s doubles, because the ball grows like (2 s)^r. The state count is therefore the harsher parameter exactly for the invariants that quantify over words, which are the ones a counterexample search needs, and the affordable radius for the zero-divisor search is 2 from 4 states onward.

AutomatonAdderCascade

The cascade's Moore diagram is a path with the carry edges on it, and every state's portrait is silent below its depth.

The boundary graph of the first state at level 4 is a single cycle of length 16, which is the order of that state.

One step of the evolution advances a symbol exactly under an active window, so the evolution of a tape is the orbit of a sliding-block code.

The exercised sub-digraphs of a window program are the walks of the de Bruijn graph, so the family over the tapes of a length is the family of window sequences that occur.

AutomatonProduct

The composition automaton of the cascade on three states with the window program of length 2 has twelve states, and its group is the group of the two factors together.

Constructive families of many-state automata

Setup

Functions

Definitions

Classification

The cost of an invariant in the state count

AutomatonAdderCascade

AutomatonProduct

Literature