Recoverable Memory Under Finite-State Endomorphic Replacement:
Universal Permutation Quotients and Trusted Replacement Records

Brian Theory
B-Theory Research Programme
Brian@B-Theory.com

8 November 2026

Abstract

We study exact recovery of finite-state information after a deterministic system undergoes an endomorphic state replacement that preserves its named task dynamics and observable output. Three notions are separated at the outset: audited continuation of a token, recoverability of an earlier register, and equivalence of all future task behavior. For a finite Moore machine, let $S$ be its endomorphism monoid. A register is robust when, for every $F \in S$ , its old value can be recovered from its value after $F$ by a decoder that may depend on $F$ . We prove that robust registers are exactly the $S$ -invariant quotients on which every element of $S$ acts as a permutation. A canonical finest quotient is realized explicitly from any minimum-rank idempotent $e \in S$ : it is the component quotient of the graph with edges $F (x) - - F (e (x))$ . This quotient is independent of $e$ , is contained in predictive equivalence, and is a congruence for the task dynamics.

We then remove direct knowledge of the replacement. Given the induced permutation group $G$ on the robust quotient, a publicly known nonempty origin promise $H$ , a trusted record depending only on the replacement, and the final quotient state, the minimum record alphabet is the chromatic number of an explicit functional characteristic graph on $G$ . For the regular cyclic action on $ℤ_{n}$ and $H = {0, \dots, h - 1}$ , this number is

⌈ \frac{n}{⌊ n ∕ h ⌋} ⌉ .

The universal group-action quotient, characteristic-graph reduction, and cycle-power formula are established mathematics. The contribution is a self-contained operational synthesis for replacement and origin recovery, including an explicit minimum-idempotent component realization, boundary and end-to-end examples, and reproducible finite checks. No criterion for personal identity or consciousness is asserted.

Keywords. finite transformation monoid; Moore machine; endomorphism; memory recovery; permutation quotient; zero-error coding; characteristic graph.

MSC 2020. 20M20, 68Q45, 94A15, 05C15.

1 Introduction

Replacing part or all of a finite system can preserve some descriptions and destroy others. A device may continue to produce the same task behavior while losing an earlier internal bit; conversely, an old register value may remain recoverable although the device’s future outputs change. A third question—whether the resulting token is counted as the same audited continuant—is not determined by either information recovery or behavior unless an additional lineage rule is supplied.

This paper isolates the finite deterministic mathematics behind those distinctions. The intended word memory has a deliberately narrow meaning: a declared finite register evaluated before and after a state map. Recovery is counterfactual over a common family of possible old states. It is not the vacuous assertion that a constant decoder can be fitted to one already known realized history. Similarly, a replacement record is a trusted side channel in a stated coding problem; it is not an unverified narrative generated by the system.

Here replacement means a state transformation within one fixed behavioral architecture: the state set, named transitions, and output interface remain those of $A$ . Replacing a machine by a different machine $A^{'}$ would require homomorphisms, simulations, or a declared common comparison object and is outside the present model.

The first part concerns a finite Moore machine

A = (X, U, {T_{u}}_{u \in U}, b) .

Its allowed replacements are the endomorphisms that commute with every named task transition and preserve the current output:

S = End (A) = {F : X \to X : F T_{u} = T_{u} F for all u, bF = b} .

The monoid $S$ is generally different from the transition monoid generated by the $T_{u}$ . A register $r : X \to K$ is robust if, for every $F \in S$ , a decoder $d_{F}$ satisfies $r = d_{F} rF$ on all of $X$ . We show that this apparently asymmetric decoding condition forces $F$ to permute the memory classes. We then give a canonical finest robust quotient.

The construction is the action-level universal group reflection familiar from finite transformation-monoid theory. Congruences of finite $M$ -sets, idempotent images, minimal ideals, maximal subgroups, and maximal group images are standard; see Steinberg [10] and Egri-Nagy and Nehaniv [4]. We give a self-contained proof and an explicit component graph from one minimum-rank idempotent because the recovery contract and its interaction with task prediction are the point. We claim an operational specialization and realization, not a new universal construction. A targeted search did not locate this exact single-idempotent graph formula; its publication priority remains to be checked by a human specialist.

The second part asks how much replacement information a decoder needs. After passing to the finest robust quotient $Q$ , the monoid image is a permutation group $G \leq Sym (Q)$ . The old value $q$ is promised to lie in a public set $H \subseteq Q$ . The encoder knows the replacement $g \in G$ but not $q$ and sends one trusted symbol $z (g)$ . From $z (g)$ and the final state $y = gq$ , the decoder must recover $q$ exactly. The optimum is a characteristic-graph chromatic number. This is an instance of classical zero-error coding with decoder side information [11, 6, 3], not a new coloring principle. The cyclic interval family reduces to a power of a cycle; its closed formula is the Prowse–Woodall formula [9, 5].

Contributions and status

The paper makes four claims at deliberately different levels.

(C1): Operational separation. Audited lineage, decoder recoverability, and predictive behavior are independent predicates in a four-state machine. This is a modeling clarification, not a claimed new automata theorem.
(C2): Robust-memory quotient. Robust registers are characterized as permutation quotients. The standard universal group-action quotient is realized as the component quotient generated by any minimum-rank idempotent, and is shown compatible with predictive equivalence and named task dynamics. The operational formulation and explicit graph are the contribution claimed here; priority for the graph formula is not certified.
(C3): Replacement-record optimum. The exact one-shot record alphabet is the chromatic number of a functional characteristic graph. This is a specialization of established characteristic-graph coding, included to make the replacement contract exact.
(C4): Cyclic family and limits. The cyclic interval formula, examples, self-report counterexample, and finite enumerations make the boundaries explicit. The cycle formula itself is established.

Section 2 separates the three continuity predicates. Section 3 gives the robust quotient and its task compatibility. Section 4 solves the trusted-record problem, and Section 5 treats the cyclic family and an end-to-end Moore machine realization. Interpretation, verification, literature boundaries, and open questions follow.

2 Three continuity contracts

2.1 Machine, prediction, and registers

Let $X$ be a finite nonempty state set, $U$ a finite input alphabet, $T_{u} : X \to X$ the transition for input $u$ , and $b : X \to Y$ an output map. For a word $w = u_{1} \dots u_{ℓ}$ , write $T_{w} = T_{u_{ℓ}} \dots T_{u_{1}}$ and let $T_{𝜀} = {id}_{X}$ .

Definition 2.1 (Predictive equivalence). States $x, x^{'} \in X$ are predictively equivalent, written $x E x^{'}$ , when

b (T_{w} x) = b (T_{w} x^{'}) for every w \in U^{*} .

Thus $E$ is the usual Moore behavioral equivalence for all future input words, including the empty word. A finite register is a surjection $r : X \to K$ onto its attained alphabet. Its kernel relation is denoted $R = ker r$ .

Given a state map $F : X \to X$ , consider:

$L (F)$: An external audit stipulates that the output token continues the old lineage.
$M_{r} (F)$: There exists $d_{F} : K \to K$ such that $r = d_{F} rF$ on all $X$ .
$P (F)$: $F (x) E x$ for all $x \in X$ .

The label $L$ is intentionally not inferred from the state map. It represents whatever extra physical or institutional rule audits a continuant. The other two predicates are mathematical.

Example 2.2 (All eight truth patterns). Let

X = {(v, m) : v, m \in {0, 1}}, b (v, m) = v, T (v, m) = (1 - v, m),

and take $r (v, m) = m$ . Identity has $M_{r}$ and $P$ ; the erasure $F (v, m) = (v, 0)$ has $P$ but not $M_{r}$ ; the visible flip $F (v, m) = (1 - v, m)$ has $M_{r}$ but not $P$ ; and the reset $F (v, m) = (0, 0)$ has neither. Pair each map with either a stipulated surviving token or a fresh token having the same resulting state. All eight triples $(L, M_{r}, P)$ occur.

The example is a logical independence construction. It does not assert that biological lineage is freely adjustable. Its role is to prevent behavioral, informational, and lineage claims from being substituted for one another without an additional premise.

2.2 The unrestricted-map boundary

When every state map is admitted, the relationships among memory and prediction become extreme. The following proposition is useful as a negative control for the restricted endomorphism problem.

Proposition 2.3 (Unrestricted coupling). Let $X$ be finite and let $R = ker r$ .

(i): Every $P$ -map satisfies $M_{r}$ if and only if $E \subseteq R$ .
(ii): Every map satisfying $rF = r$ satisfies $P$ if and only if $R \subseteq E$ .
(iii): Every map satisfying $M_{r}$ satisfies $P$ if and only if $E = X^{2}$ .

Proof. For (i), if $E \subseteq R$ and $F (x) E x$ , then $rF = r$ , so identity decodes. Conversely, if $x E y$ but $r (x) \neq r (y)$ , the map that sends $x$ to $y$ and fixes all other states is a $P$ -map but collapses two different old register values at the post-map register.

For (ii), if $R \subseteq E$ , literal register retention implies $F (x) R x$ , hence $F (x) E x$ . Conversely, if $x R y$ but $xE̸y$ , send $x$ to $y$ and fix all other states. The register is retained but prediction is not.

For (iii), universality of $E$ is sufficient. If $E$ is not universal, choose $xE̸y$ . Choose a permutation $σ$ of the set of $R$ -classes that sends ${[x]}_{R}$ to ${[y]}_{R}$ (if these classes coincide, take $σ$ to fix that class). Define $F (x) = y$ and, for every other state $v$ , choose $F (v)$ in the class $σ ({[v]}_{R})$ . Then $rF$ is obtained from $r$ by a permutation of its attained labels, so a decoder exists, whereas $P$ fails at $x$ . □

These necessity arguments use arbitrary maps. They cannot be imported into a mechanism-respecting replacement monoid without checking that the witnesses are endomorphisms.

2.3 Observational non-identifiability

Suppose two histories give exactly the same entire interface permitted to an observer but different lineage labels. Any decision rule on that interface gives the same answer on both histories and must fail on one. This elementary observation is the finite analogue of a recurring distinction in experimental identification: pairwise behavioral distinguishability and identification under a declared experiment family are different notions; compare Moore [7].

Branching adds a separate logical obstruction. An equivalence relation for numerical identity, identity of two distinct contemporaneous copies with one parent, and uniqueness of a contemporaneous bearer cannot all hold. Transitivity identifies the copies. This is a consistency boundary, not a resolution of philosophical debates about persons; compare the branching discussion in Parfit [8].

3 Robust memory as a permutation quotient

3.1 Allowed replacements

We now restrict replacements to

S = End (A) = {F : X \to X : F T_{u} = T_{u} F for every u \in U, bF = b} .

Composition is written on the left: $FG = F \circ G$ . Identity belongs to $S$ , and $S$ is closed under composition. We do not require a designated initial state to be fixed. If every state is reachable from such a state, commuting with all transitions and fixing that state would force every endomorphism to be identity.

An equivalence relation $R$ on $X$ is $S$ -invariant when $x R y$ implies $F (x) R F (y)$ for every $F \in S$ . Relations are ordered by inclusion: a smaller kernel gives a finer, larger quotient.

Definition 3.1 (Robust register). A register $r : X \to K$ is robust for $S$ if

\forall F \in S \exists d_{F} : K \to K r = d_{F} rF . (1)

The decoder may depend on the replacement, but not on the old state.

The same finite register is evaluated on both sides of the replacement. Allowing an expanding post-replacement memory, or requiring one decoder for unknown $F$ , gives different problems.

3.2 Kernel characterization

Lemma 3.2 (One replacement). For a fixed $F : X \to X$ , a decoder in (1) exists if and only if

ker (rF) \subseteq ker r .

If $X$ is finite and $K = r (X)$ , this inclusion holds if and only if $ker (rF) = ker r$ .

Proof. A decoder exists exactly when $r (x)$ is constant on every fiber of $rF$ , which is the stated inclusion. The partition $ker (rF)$ has at most $| K |$ blocks. If it refines $ker r$ , which has exactly $| K |$ blocks, it has at least $| K |$ blocks. Equality of the block counts forces equality of the relations. □

Theorem 3.3 (Robust-register characterization). For $R = ker r$ , the following are equivalent.

(a): $r$ is robust.
(b): $R$ is $S$ -invariant and every $F \in S$ induces a permutation $\bar{F}$ of $X ∕ R$ .
(c): $R$ is $S$ -invariant and $x R e (x)$ for every $x \in X$ and every idempotent $e \in S$ .

Proof. By Lemma 3.2, robustness is equivalent to $ker (rF) = R$ for all $F$ . Equality means that $F$ sends each $R$ -class into one class, sends different classes into different classes, and uses all classes. This is exactly (b).

If (b) holds, an idempotent $e$ induces an idempotent permutation and hence identity, proving (c). Conversely, assume (c). Every transformation of a finite set has an idempotent positive power: take an exponent beyond the transient part and divisible by all cycle lengths. Thus for each $F \in S$ , some $F^{n}$ is idempotent and ${\bar{F}}^{n} = id$ . Hence $\bar{F}$ is invertible, proving (b). □

Remark 3.4 (Unknown replacement). If one decoder $d$ must work for every $F \in S$ , then applying it to $F = id$ makes $d$ identity on $K$ . The condition becomes $rF = r$ for all $F$ . Individual invertibility on the quotient does not reveal which inverse to apply.

3.3 The finest quotient

Choose a minimum-rank element of $S$ and replace it by an idempotent positive power. This gives an idempotent $e \in S$ of minimum rank, lying in the minimal ideal of the concrete transformation monoid, with $k = | e (X) |$ [10]. Define an undirected graph $G_{e}$ on $X$ by adding the edges

F (x) - - - F (e (x)) (F \in S, x \in X) . (2)

Loops and repeated edges are ignored. Let $ρ_{e}$ be the connected-component relation of this graph. Equivalently, $ρ_{e}$ is the least $S$ -invariant equivalence containing $x \sim e (x)$ for every $x$ .

Theorem 3.5 (Explicit canonical group-action quotient). Let $S$ be a finite transformation monoid on a finite nonempty set $X$ , and let $e \in S$ be any minimum-rank idempotent. Then:

(i): every element of $S$ induces a permutation of $Q = X ∕ ρ_{e}$ ;
(ii): an equivalence relation $R$ is the kernel of a robust register if and only if it is $S$ -invariant and $ρ_{e} \subseteq R$ ;
(iii): $ρ_{e}$ is independent of the selected minimum-rank idempotent and is the least $S$ -invariant equivalence containing $x \sim f (x)$ for every idempotent $f \in S$ .

Proof. Every $ρ_{e}$ -class has a representative in $e (X)$ because $x ρ_{e} e (x)$ . Fix $F \in S$ . The map $eFe$ has image in $e (X)$ . Since $eFe \in S$ , its rank is at least the minimum rank $k$ , while its image has size at most $k$ . Moreover $eFe (X) = eFe (e (X))$ , because the rightmost $e$ is applied first. Thus $eFe$ maps $e (X)$ onto all $k$ image points, so its restriction to $e (X)$ is a bijection.

On $Q$ , the map induced by $e$ is identity. Explicitly, $[F (x)] = [F (e (x))] = [eF (e (x))]$ , so $F$ and $eFe$ induce the same map. Given a class $[y]$ , choose $y_{0} \in e (X)$ in that class and choose $x_{0} \in e (X)$ with $eFe (x_{0}) = y_{0}$ . Then the class of $x_{0}$ maps to $[y]$ . The induced $F$ is therefore surjective on finite $Q$ , hence a permutation. This proves (i).

If $R$ is robust, Theorem 3.3 says it is $S$ -invariant and $e$ acts identically on $X ∕ R$ . Therefore $R$ contains all pairs $F (x) \sim F (e (x))$ and hence $ρ_{e}$ . Conversely, any $S$ -invariant coarsening $R$ of $ρ_{e}$ is a quotient of the permutation action on $Q$ . For every target $R$ -class, choose one of its $ρ_{e}$ -classes and a preimage under the permutation of $Q$ ; hence the induced map on $X ∕ R$ is surjective, and on a finite quotient it is bijective. Theorem 3.3 proves robustness. This establishes (ii).

Part (ii) characterizes $ρ_{e}$ as the unique finest robust kernel, so it cannot depend on the chosen minimum-rank idempotent. The equivalence generated using all idempotents has the same universal property by Theorem 3.3, proving (iii). □

Proposition 3.6 (Universal group-action property). Let $η : S \to G_{max} (S)$ denote the maximal group image of the finite monoid $S$ . The action homomorphism $S \to Sym (Q)$ factors uniquely through $η$ . Moreover, $X \to Q$ is universal among $S$ -equivariant quotient maps from $X$ to finite sets on which $S$ acts by permutations.

Proof. Every idempotent of $S$ acts trivially on $Q$ , so the action homomorphism factors through the quotient of $S$ obtained by identifying all idempotents with the identity, which is $G_{max} (S)$ for finite $S$ [10, Section 7.1]. If $X \to Y$ is another such quotient, its kernel is robust by Theorem 3.3; therefore it contains $ρ_{e}$ by Theorem 3.5, and the map factors uniquely through $X \to Q$ . □

Thereafter write $ρ$ for this canonical relation, set $Q = X ∕ ρ$ , and let

G = im (S \to Sym (Q)) .

All robust registers, up to relabeling, are precisely pullbacks of $G$ -invariant equivalence relations on $Q$ . For a transitive action these are the familiar block systems. The group $G$ is an image attached to this particular action and, by Proposition 3.6, a quotient of $G_{max} (S)$ . It need not equal $G_{max} (S)$ , nor the full automorphism group of $Q$ .

Corollary 3.7 (Rank bound).

| Q | \leq min_{F \in S} rank (F) .

Proof. Every $ρ$ -class has a representative in $e (X)$ . □

The bound can be strict; see Example 3.10. If $S$ is explicitly listed, (2) uses $| S | | X |$ edges and connected components compute $ρ$ . This does not make endomorphism enumeration polynomial for a succinctly specified machine: in the worst case there are $| X |^{| X |}$ candidate maps.

3.4 Compatibility with task behavior

Theorem 3.8 (Task compatibility). For $S = End (A)$ , the canonical relation $ρ$ satisfies:

(i): $ρ \subseteq E$ ;
(ii): $ρ$ is a congruence for every named task transition $T_{u}$ ;
(iii): $b$ is constant on $ρ$ -classes.

Consequently $Q$ inherits a Moore-machine structure.

Proof. For every $F \in S$ and every word $w$ ,

b (T_{w} F (x)) = b (F T_{w} (x)) = b (T_{w} (x)),

so $F (x) E x$ . The relation $E$ is $S$ -invariant and every $F$ induces identity on $X ∕ E$ ; hence $E$ is a robust kernel. Theorem 3.5 gives $ρ \subseteq E$ .

Alternatively, task congruence can be seen directly on the generators of $ρ$ . Applying $T_{u}$ to the edge $F (x) - - F (e (x))$ gives

F (T_{u} x) - - F (e (T_{u} x)),

using commutation of $F$ and $e$ with $T_{u}$ . This is another edge of $G_{e}$ . Task maps preserve paths and components. Finally, $ρ \subseteq E \subseteq ker b$ . □

An arbitrary robust coarsening of $ρ$ need not be a task congruence. A coarser memory register can therefore remain recoverable without being a sufficient state for autonomous task updates.

3.5 Boundary examples

Example 3.9 (Irreversible state map, reversible memory). Let $X = {0, 1, 2}$ , let output be constant, and let $T = (1, 0, 0)$ . Direct calculation gives

S = {id, e = (0, 1, 1), T = (1, 0, 0)} .

The canonical classes are ${0}$ and ${1, 2}$ . The nonbijective physical map $T$ swaps these two memory values. Every physical automorphism is trivial, yet the robust quotient has a nontrivial permutation action.

Example 3.10 (Strict rank gap). Let $X = {0, 1, 2}$ , take constant output, and include the two task maps that are constantly $0$ and constantly $1$ . Every endomorphism fixes $0$ and $1$ and may send $2$ anywhere. The minimum rank is $2$ . The collapses of $2$ to $0$ and to $1$ together force $0 \sim 1 \sim 2$ , so $Q$ is a singleton. Thus the rank bound in Corollary 3.7 can be strict.

Example 3.11 (A robust coarsening need not update). Let $T = (1, 2, 2)$ and $b = (0, 0, 1)$ on three states. Its endomorphism monoid is trivial, so every partition is robust. The partition ${0, 1} ∣ {2}$ is not $T$ -invariant because $T (0) = 1$ and $T (1) = 2$ .

Flow diagram: a physical state passes through an admitted endomorphism to the canonical recoverable quotient; if the induced permutation is hidden, a trusted replacement record and the final quotient value jointly recover the old quotient value. — Figure 1: The two stages of the theory. The physical system first passes to the canonical quotient on which every allowed replacement is a permutation. When the decoder is not told which permutation occurred, a trusted record and the final quotient value jointly recover the old value.

4 Trusted replacement records

4.1 One-shot exact-recovery contract

Fix a finite set $Q$ , a permutation group $G \leq Sym (Q)$ , and a nonempty public promise $H \subseteq Q$ . Every pair $(g, q) \in G \times H$ is possible. The encoder knows $g$ but not $q$ and sends $z (g)$ from a finite alphabet $Z$ . The decoder observes

(z (g), y), y = gq,

and must output $q$ for every possible pair. No distribution is assumed, and the objective is $| Z |$ , not expected code length. Encoder and decoder are deterministic and have no shared randomness. Fixed-length binary storage is $⌈ {log}_{2} | Z | ⌉$ bits.

The use of the image permutation group is important. If actual replacements $F$ are the encoder inputs, replacements inducing the same $g$ cannot help lower the optimum. Restricting any valid code to one chosen representative in each fiber over $g$ gives the same lower-bound graph on $G$ . Conversely, a valid code on $G$ lifts by assigning every replacement in the fiber over $g$ the symbol assigned to $g$ .

Definition 4.1 (Functional characteristic graph). Let $Γ_{H}$ be the simple graph with vertex set $G$ . Distinct $g, k$ are adjacent exactly when

\exists q, r \in H, q \neq r, gq = kr . (3)

This is the functional characteristic graph for the demanded function below in the sense of Charpenay et al. [3, Definition 4]; we also call adjacent encoder inputs functionally confusable.

The requirement $q \neq r$ distinguishes recovery of the old state from recovery of the replacement. Two transformations may produce the same final value from the same old state without creating a decoding conflict.

Theorem 4.2 (Minimum trusted-record alphabet). The minimum number of trusted record symbols for exact old-state recovery is

χ (Γ_{H}) .

Proof. Suppose adjacent $g, k$ receive the same record. Choose $q \neq r$ in $H$ with $gq = kr = y$ . The decoder receives the same pair $(z, y)$ in both histories but is required to return two different origins. Thus every valid record map is a proper coloring and $| Z | \geq χ (Γ_{H})$ .

Conversely, let $z$ be a proper coloring. For a color $c$ and output $y$ , consider

D (c, y) = {q \in H : \exists g \in G, z (g) = c, gq = y} .

If this set contained distinct $q, r$ , corresponding $g, k$ of color $c$ would be adjacent. Hence $| D (c, y) | \leq 1$ . On every feasible decoder input the set is nonempty, so return its unique element. Define the decoder arbitrarily on infeasible inputs. □

Corollary 4.3 (Extremes and monotonicity).

(i): If $H$ is a singleton, one record symbol suffices.
(ii): If $H = Q$ , then $Γ_{H}$ is complete and $| G |$ symbols are necessary and sufficient.
(iii): If $H \subseteq H^{'}$ , then $χ (Γ_{H}) \leq χ (Γ_{H^{'}})$ .

Proof. Only (ii) needs comment. If $g \neq k$ , their inverse permutations differ at some $y \in Q$ . Let $q = g^{- 1} y$ and $r = k^{- 1} y$ . Then $q \neq r$ and $gq = kr = y$ , so every pair of vertices is adjacent. Part (iii) follows because enlarging $H$ only adds possible witnesses to (3). □

Example 4.4 (Overlap is not enough). Let $G = S_{3}$ act naturally on $Q = {0, 1, 2}$ and let $H = {0, 1}$ . Identity and the transposition $(1 2)$ have overlapping images of $H$ at $0$ , but that output has origin $0$ under both transformations. They need not be separated. For a regular action, distinct group elements cannot agree on the image of the same origin, so image overlap and functional conflict coincide.

4.2 Relation to zero-error coding

In standard coding notation, the encoder variable is $g$ , the decoder side information is $y$ , the feasible support consists of pairs with $y \in gH$ , and the demanded function is

f (g, y) = g^{- 1} y .

Two encoder inputs are adjacent when a common feasible side-information value requires different function outputs. This is exactly the characteristic-graph principle used in zero-error function computation [3]. Witsenhausen’s chromatic formulation and later work on decoder side information provide the broader antecedent [11, 6].

The present objective is deliberately one-shot and worst-case. Chromatic entropy, graph entropy, prefix-code length, and asymptotic graph products answer different questions. No probabilistic or asymptotic theorem is being inferred from Theorem 4.2.

5 An exact cyclic family

Let $Q = G = ℤ_{n}$ , acting regularly by addition, and let

H_{h} = {0, 1, \dots, h - 1}, 1 \leq h \leq n .

Two shifts $a, b$ conflict exactly when their nonzero difference modulo $n$ lies in

{\pm 1, \dots, \pm (h - 1)} .

Thus

Γ_{H_{h}} = Cay (ℤ_{n}, {\pm 1, …, \pm (h - 1)}),

For $n \geq 3$ this is the usual power $C_{n}^{h - 1}$ . It is complete exactly when $h - 1 \geq ⌊ n ∕ 2 ⌋$ ; the Cayley description also covers all boundary cases, including $n = 1, 2$ , without ambiguity.

Theorem 5.1 (Cyclic interval optimum). For the cyclic action and interval promise $H_{h}$ , the minimum record alphabet is

m (n, h) = ⌈ \frac{n}{⌊ n ∕ h ⌋} ⌉ . (4)

Proof. Put $k = ⌊ n ∕ h ⌋$ . In an independent set of shifts, successive clockwise gaps are at least $h$ ; otherwise two shifts differ by one of the forbidden residues in one direction. This applies for $s \geq 2$ ; the case $s = 1$ is immediate (equivalently, its sole circular gap is $n$ ). Thus an independent set of size $s$ satisfies $sh \leq n$ , so its size is at most $k$ . The set

{0, h, 2 h, \dots, (k - 1) h}

attains this bound, including the wraparound gap $n - (k - 1) h \geq h$ . Therefore every coloring needs at least

c = ⌈ \frac{n}{k} ⌉

colors.

For a matching coloring, let $d = kc - n$ , so $0 \leq d < k$ . Arrange the positions $0, \dots, n - 1$ in $k$ consecutive rows: $d$ rows of length $c - 1$ followed by $k - d$ rows of length $c$ . Color each position by its zero-based column. Every row has length at least $h$ . Indeed $c \geq h$ ; if $c = h$ , then $n = kh$ and $d = 0$ , while otherwise $c - 1 \geq h$ .

For any fixed column, consecutive occurrences around the circle are separated by the sum of one or more intervening row lengths, hence by at least $h$ . A column absent from a short row merely skips that row and increases the gap. Thus every color class is independent, including across the cyclic boundary. At least one row has length $c$ , so exactly $c$ colors are used. □

Writing $n = kh + r$ with $0 \leq r < h$ , formula (4) is $h + ⌈ r ∕ k ⌉$ . In the cycle-power range this is the Prowse–Woodall chromatic-number formula [9, 5]. The proof is included to make the record construction explicit; no originality is claimed for the graph formula or coloring.

Example 5.2 (Strict compression). For $n = 12$ and $h = 3$ , three symbols suffice:

(0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2) .

The record is the shift modulo $3$ , and $q = (y - z) mod 3$ , interpreted in ${0, 1, 2}$ . Twelve replacements therefore need only three record symbols under this promise, versus twelve under full support.

Example 5.3 (The nondivisible case). For $n = 10$ and $h = 3$ , the optimum is four:

(0, 1, 2, 0, 1, 2, 0, 1, 2, 3) .

The tempting coloring $a mod 4$ fails because shifts $0$ and $8$ would share a color across a cyclic gap of only $2$ .

Example 5.4 (Promise geometry matters). For $ℤ_{6}$ , the promise ${0, 1, 2}$ needs three symbols, whereas ${0, 1, 3}$ needs six. The latter set has every nonzero residue in its difference set, so the graph is complete. Promise cardinality alone does not determine record cost. Also, $n = 5, h = 2$ gives a five-cycle: three symbols are needed although the largest clique has size two.

5.1 End-to-end Moore-machine realization

The cyclic coding family arises from the earlier endomorphism construction, rather than being an unrelated group action. Fix $n \geq 2$ and let

X = ℤ_{n} \times {0, 1}, b (a, i) = i .

Give the Moore machine two named transitions

T (a, i) = (a + 1, i), R (a, i) = (a, 1 - i) .

If $F \in End (A)$ , output preservation gives $F (a, i) = (f_{i} (a), i)$ . Commutation with $T$ forces $f_{i} (a) = a + c_{i}$ , and commutation with $R$ forces $c_{0} = c_{1}$ . Hence

End (A) = {F_{c} : F_{c} (a, i) = (a + c, i), c \in ℤ_{n}} ≅ ℤ_{n} .

Every endomorphism is already a permutation, so the canonical relation $ρ$ is equality and $Q = X$ . The subset $O = ℤ_{n} \times {0}$ is an invariant orbit, equivariantly isomorphic to the regular action of $ℤ_{n}$ on itself. Restrict the public old-state promise to

H = {(q, 0) : 0 \leq q < h} .

The unknown replacement $F_{c}$ produces the final state $(c + q, 0)$ , and the functional characteristic graph on the replacements is the Cayley graph displayed above (and, for $n \geq 3$ , $C_{n}^{h - 1}$ ). Theorem 5.1 therefore gives the minimum trusted record alphabet for this concrete Moore machine. This example runs the full pipeline

A ⟼ S ⟼ (Q, G, H) ⟼ Γ_{H} ⟼ χ (Γ_{H})

and shows the additional conclusion supplied by combining the two halves: the optimal trusted replacement side channel can be computed from the admitted mechanism-preserving state replacements.

6 Reports, narratives, and the scope of identity

The formal results concern exact relations among declared finite states, maps, and interfaces. They support several negative interpretive claims but no positive criterion for personal identity or consciousness.

6.1 A self-report is another output

Return to Example 2.2 and add a report

n (v, m) = active v; I retain my origin .

The report depends on $v$ but not on $m$ . The replacement $F (v, m) = (v, 0)$ commutes with the task, preserves visible output and every future report, yet destroys the old memory bit. Both possible old values lead to the same final state. The sentence persists while its retention claim can be false.

Including the report in the output map $b$ restricts $End (A)$ to maps that preserve the report by definition. It does not establish the semantic truth of the report. Likewise, copying a complete report stream cannot authenticate distinct external lineages if the permitted interface is identical. A trusted record in Section 4 is a separately assumed channel; treating an unverified narrative as trusted would assume the desired conclusion.

6.2 Relation to B-Theory and The MIND

B-Theory’s acquisition work distinguishes an attainable observation partition from predictive equivalence and, when actions change state, distinguishes certainty about the current state from recovery of its origin [1]. The present paper starts after that distinction: it asks which old information remains recoverable under a declared family of mechanism-respecting replacements.

This gives a bounded mathematical connection to the programme’s Being-and-Becoming question. The quotient $Q$ is not a criterion of identity. It is the finest declared register whose old value can be recovered after every allowed replacement when the replacement is known. The group $G$ records how that information changes reversibly even when the physical state map is irreversible. The record theorem then quantifies what an observer must learn about the replacement when it is not directly known.

The same distinction complements finite-state reflective self-models that track changing internal machinery [2]. Estimation and control ask how evidence should update an internal model. The present quotient asks a logically prior structural question: which distinctions are recoverable under the admitted transformations at all? Neither answer establishes subjective awareness, introspection, moral status, or numerical personal identity.

7 Computational verification

The proofs above are analytic. Bounded enumeration was used to catch quantifier, orientation, and boundary errors.

1.: The continuity checks covered $57, 600$ coupling-event cases.
2.: The robust-memory implementation examined $10, 228$ labeled machines, $91, 844$ machine–partition cases, and $546$ distinct endomorphism monoids. A separate implementation checked $206$ small transformation monoids ( $1, 030$ cases) and $234$ unary machines ( $1, 114$ partition cases).
3.: The record implementation checked all $120$ nonempty cyclic promises through $n = 6$ , compared $4, 042$ explicit encoders with the graph criterion through $n = 4$ , verified $820$ interval constructions through $n = 40$ , and computed the exact chromatic number for all $78$ interval cases through $n = 12$ .
4.: A separately written checker verified all $247$ nonempty promises through $n = 7$ , $8, 967$ encoder comparisons through $n = 5$ , and the same $78$ exact interval cases.

The overlapping counts are cross-checks, not additive coverage. Enumeration does not prove the infinite family, certify a literature claim, or replace external peer review. Source code, recorded outputs, and SHA-256 manifests are provided with the research package.

8 Related work and contribution boundaries

Transformation monoids. The language of finite $M$ -sets, congruences, idempotent images, minimal ideals, maximal subgroups, and universal group images is standard. Steinberg’s treatment includes the congruence restriction/right-adjoint construction for an idempotent image and the universal maximal group image of a finite monoid [10, Propositions 2.15–2.16 and Section 7.1]. Egri-Nagy and Nehaniv study automaton endomorphisms under a fixed input alphabet and their units [4]. Proposition 3.6 identifies the robust quotient with the standard group-action reflection. The inspected passages do not state the recovery condition (1) or the single-minimum-idempotent component graph (2); that graph may nevertheless be an elementary corollary or known construction under other terminology. We claim an explicit operational specialization and proof, not priority for a new universal construction.

Automata and identification. Moore’s classic paper separates distinguishability from identification by experiments [7]. Homing and distinguishing sequences address related questions about initial or final states under input/output experiments. Here the replacement itself is an endomorphism, the register is declared independently of output behavior, and the first problem gives the decoder the replacement. Those choices should not be conflated with standard homing-sequence objectives.

Zero-error side information. Witsenhausen connected zero-error side information with chromatic numbers [11]; Koulgi et al. study zero-error source coding with decoder side information [6]. Charpenay et al. formulate functional characteristic graphs in which common side information creates an edge only when demanded function values differ [3, Definition 4 and Theorem 1]. That is precisely the distinction illustrated in Example 4.4. Our one-shot alphabet objective is simpler than their asymptotic rate problem.

Cycle powers. Prowse and Woodall proved the chromatic-choosability result for powers of circuits, including the chromatic formula used here [9]. Jimenez and Valencia-Pabon state the formula and give a linear coloring algorithm [5]. Equation (4) is an application of that result to replacement records.

Philosophical scope. Branching cases have a long philosophical history; Parfit is a direct antecedent [8]. This paper supplies no metaphysical criterion for persons. It distinguishes properties that an applied theory would have to connect by substantive premises. Terms such as same memory or same behavior should not silently carry a conclusion about lineage.

9 Open questions

Several extensions require new contracts rather than more interpretation of the present theorem.

(O1): When does the one-minimum-idempotent component graph in Theorem 3.5 give an algorithmic or structural advantage over the standard all-idempotents description of the group reflection?
(O2): What is the complexity of computing the finest quotient when the machine is given succinctly and the endomorphism monoid is not enumerated?
(O3): For which permutation actions and promise families can $χ (Γ_{H})$ be expressed without constructing the full graph?
(O4): How do noisy, forged, probabilistic, or sequential replacement records alter the objective? These require authentication or stochastic coding assumptions absent here.
(O5): How should a resource-bounded controller acquire the final quotient state $y$ ? The present record theorem assumes that observation.
(O6): Which physical replacement families are justified for a particular engineered or biological system? Commutation and output preservation are mathematical admissibility conditions, not empirical laws.

10 Conclusion

Finite-state transformations support several inequivalent continuity claims. An audited token may continue while old information is lost; old information may remain recoverable while future task behavior changes; and identical behavior or narrative cannot authenticate an external lineage label.

Under mechanism-respecting endomorphisms, exact recovery has a rigid structure. Every robust register is a permutation quotient, and there is a unique finest one obtained from any minimum-rank idempotent. For Moore machine endomorphisms this quotient remains compatible with task dynamics and lies inside predictive equivalence. This quotient is the standard universal group-action reflection, here given an explicit component realization. When the replacement is hidden, the minimum trusted record is a functional characteristic-graph chromatic number. The cyclic interval case admits the exact formula $⌈ n ∕ ⌊ n ∕ h ⌋ ⌉$ .

These statements turn broad continuity language into finite, checkable contracts. They do not turn a quotient into a person, a record into an authenticated history, or a report into evidence of consciousness.

Data and reproducibility

The manuscript source, finite-check programs, recorded outputs, review notes, and checksum manifests are distributed in the accompanying research bundle. Running python run_all.py in the supplement executes five implementations in isolated temporary directories and verifies every stable count reported above. The programs use Python 3.10+ and the standard library. Earlier iteration scripts and outputs are retained byte-for-byte.

AI-assistance disclosure

AI systems assisted with literature discovery, drafting, proof criticism, independent finite-check implementations, a specialist-style algebraic and zero-error review, and a hostile-referee simulation. The reports and their resolution are included in the research bundle. All such reviews are internal computational assistance, not external peer review. Claims of priority remain qualified. The named author is responsible for verifying the manuscript, citations, code, and any journal-specific disclosure before submission.

References

[1] Brian Theory. From observable states to acquirable predictive models. B-Theory technical report, revised 7 October 2026. https://www.b-theory.com/manuscripts-html/acquirable-predictive-models/.

[2] Brian Theory. When does an explicit self-model help? Calibration and control under internal change in a finite-state pilot. B-Theory research manuscript, 14 October 2026. https://www.b-theory.com/reflective-self-models/.

[3] Nicolas Charpenay, Maël Le Treust, and Aline Roumy. Side information design in zero-error coding for computing. Entropy, 26(4):338, 2024. https://doi.org/10.3390/e26040338.

[4] Attila Egri-Nagy and Chrystopher L. Nehaniv. Symmetries of automata. Algebra and Discrete Mathematics, 19(1):48–57, 2015. https://admjournal.luguniv.edu.ua/index.php/adm/article/download/1175/664.

[5] Martín F. Jimenez and Mario Valencia-Pabon. A note on coloring powers of cycles. Author-hosted manuscript. https://www-lipn.univ-paris13.fr/~valenciapabon/papers/colpow2.pdf.

[6] Pavan Koulgi, Ertem Tuncel, Shankar L. Regunathan, and Kenneth Rose. On zero-error source coding with decoder side information. IEEE Transactions on Information Theory, 49(1):99–111, 2003. https://doi.org/10.1109/TIT.2002.806157.

[7] Edward F. Moore. Gedanken-experiments on sequential machines. In C. E. Shannon and J. McCarthy, editors, Automata Studies, pages 129–153. Princeton University Press, 1956.

[8] Derek Parfit. Personal identity. The Philosophical Review, 80(1):3–27, 1971. https://doi.org/10.2307/2184309.

[9] Anton Prowse and Douglas R. Woodall. Choosability of powers of circuits. Graphs and Combinatorics, 19(1):137–144, 2003. https://doi.org/10.1007/s00373-002-0480-8.

[10] Benjamin Steinberg. A theory of transformation monoids: combinatorics and representation theory. The Electronic Journal of Combinatorics, 17:R164, 2010. https://doi.org/10.37236/436.

[11] Hans S. Witsenhausen. The zero-error side information problem and chromatic numbers. IEEE Transactions on Information Theory, 22(5):592–593, 1976. https://doi.org/10.1109/TIT.1976.1055607.