Recoverable Memory Under Finite-State Endomorphic Replacement: Universal Permutation Quotients and Trusted Replacement Records
Extracted text · reading copy 1 · 16 PDF pages
Reading scope: Full manuscript. Results concern declared finite-state maps, registers, and interfaces; no criterion for consciousness, personal identity, or moral status is asserted.
Format limitation:This text is extracted from the linked PDF. Symbols, tables, line breaks, and reading order may be incomplete or incorrect. It is a prose-reading aid, not a verified mathematical transcription. Consult the PDF for exact statements, or request a specific result in an accessible format.
Read the source-based HTML + MathML instead · Read the original PDF · Download the extracted text
PDF page 1
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 ∈ 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 ∈ 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 Zn and H = {0, . . . , h − 1}, this number is
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 re-
placement 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.
1
Back to the startPDF page 2
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, {Tu }u∈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 → X : F Tu = Tu F for all u, bF = b}.
The monoid S is generally different from the transition monoid generated by the Tu . A register
r : X → K is robust if, for every F ∈ S, a decoder dF satisfies r = dF 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 ≤ Sym(Q). The old value q is
promised to lie in a public set H ⊆ Q. The encoder knows the replacement g ∈ 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
2
Back to the startPDF page 3
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, Tu : X → X the transition for
input u, and b : X → Y an output map. For a word w = u1 · · · uℓ , write Tw = Tuℓ · · · Tu1 and let
Tε = idX .
Definition 2.1 (Predictive equivalence). States x, x′ ∈ X are predictively equivalent, written x E x′ ,
when
b(Tw x) = b(Tw x′ ) for every w ∈ 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 → K onto its attained alphabet. Its kernel relation is
denoted R = ker r.
Given a state map F : X → X, consider:
L(F )
An external audit stipulates that the output token continues the old lineage.
Mr (F )
There exists dF : K → K such that r = dF rF on all X.
P (F )
F (x) E x for all x ∈ 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 ∈ {0, 1}}, b(v, m) = v, T (v, m) = (1 − v, m),
and take r(v, m) = m. Identity has Mr and P ; the erasure F (v, m) = (v, 0) has P but not Mr ; the
visible flip F (v, m) = (1 − v, m) has Mr 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, Mr , P ) occur.
3
Back to the startPDF page 4
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 Mr if and only if E ⊆ R.
(ii) Every map satisfying rF = r satisfies P if and only if R ⊆ E.
(iii) Every map satisfying Mr satisfies P if and only if E = X 2 .
Proof. For (i), if E ⊆ R and F (x) E x, then rF = r, so identity decodes. Conversely, if x E y but
r(x) ̸= 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 ⊆ E, literal register retention implies F (x) R x, hence F (x) E x. Conversely, if
x R y but x ̸ Ey, 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 x ̸ Ey. 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 contempora-
neous 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 → X : F Tu = Tu F for every u ∈ U, bF = b}.
Composition is written on the left: F G = F ◦ 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
4
Back to the startPDF page 5
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 ∈ S.
Relations are ordered by inclusion: a smaller kernel gives a finer, larger quotient.
Definition 3.1 (Robust register). A register r : X → K is robust for S if
∀F ∈ S ∃dF : K → K r = dF 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 → X, a decoder in (1) exists if and only if
ker(rF ) ⊆ 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 ∈ S induces a permutation F̄ of X/R.
(c) R is S-invariant and x R e(x) for every x ∈ X and every idempotent e ∈ 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 ∈ S,
some F n is idempotent and F̄ n = id. Hence F̄ is invertible, proving (b).
Remark 3.4 (Unknown replacement). If one decoder d must work for every F ∈ 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 ∈ S of minimum rank, lying in the minimal ideal of the concrete transformation
monoid, with k = |e(X)| [10]. Define an undirected graph Ge on X by adding the edges
F (x) − − − F (e(x)) (F ∈ S, x ∈ 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 ∼ e(x) for every x.
5
Back to the startPDF page 6
Theorem 3.5 (Explicit canonical group-action quotient). Let S be a finite transformation monoid
on a finite nonempty set X, and let e ∈ 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 ⊆ R;
(iii) ρe is independent of the selected minimum-rank idempotent and is the least S-invariant
equivalence containing x ∼ f (x) for every idempotent f ∈ S.
Proof. Every ρe -class has a representative in e(X) because x ρe e(x). Fix F ∈ S. The map eF e has
image in e(X). Since eF e ∈ S, its rank is at least the minimum rank k, while its image has size at
most k. Moreover eF e(X) = eF e(e(X)), because the rightmost e is applied first. Thus eF e 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
eF e induce the same map. Given a class [y], choose y0 ∈ e(X) in that class and choose x0 ∈ e(X)
with eF e(x0 ) = y0 . Then the class of x0 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) ∼ 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 → Gmax (S) denote the maximal
group image of the finite monoid S. The action homomorphism S → Sym(Q) factors uniquely
through η. Moreover, X → 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 Gmax (S) for
finite S [10, Section 7.1]. If X → 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 → Q.
Thereafter write ρ for this canonical relation, set Q = X/ρ, and let
G = im S −→ 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 Gmax (S). It need not equal Gmax (S),
nor the full automorphism group of Q.
Corollary 3.7 (Rank bound).
|Q| ≤ min rank(F ).
F ∈S
Proof. Every ρ-class has a representative in e(X).
6
Back to the startPDF page 7
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) ρ ⊆ E;
(ii) ρ is a congruence for every named task transition Tu ;
(iii) b is constant on ρ-classes.
Consequently Q inherits a Moore-machine structure.
Proof. For every F ∈ S and every word w,
b(Tw F (x)) = b(F Tw (x)) = b(Tw (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 ρ ⊆ E.
Alternatively, task congruence can be seen directly on the generators of ρ. Applying Tu to the
edge F (x) − −F (e(x)) gives
F (Tu x) − −F (e(Tu x)),
using commutation of F and e with Tu . This is another edge of Ge . Task maps preserve paths and
components. Finally, ρ ⊆ E ⊆ 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 ∼ 1 ∼ 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.
7
Back to the startPDF page 8
origin promise
q∈H⊆Q
physical state πρ robust value g = F̄ final value decoder
x∈X q = [x]ρ ∈ Q y = gq returns old q
induces
replacement trusted record
F ∈ End(A) F 7→ g 7→ z(g) z(g)
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 ≤ Sym(Q), and a nonempty public promise H ⊆ Q.
Every pair (g, q) ∈ G × 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 ⌈log2 |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
∃q, r ∈ H, q ̸= 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 ̸= 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 = ̸ 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| ≥ χ(ΓH ).
8
Back to the startPDF page 9
Conversely, let z be a proper coloring. For a color c and output y, consider
D(c, y) = {q ∈ H : ∃g ∈ 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)| ≤ 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 ⊆ H ′ , then χ(ΓH ) ≤ χ(ΓH ′ ).
Proof. Only (ii) needs comment. If g ≠ k, their inverse permutations differ at some y ∈ Q. Let
−1 −1
q = g y and r = k y. Then q ̸= 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 = S3 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 ∈ 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 = Zn , acting regularly by addition, and let
Hh = {0, 1, . . . , h − 1}, 1 ≤ h ≤ n.
Two shifts a, b conflict exactly when their nonzero difference modulo n lies in
{±1, . . . , ±(h − 1)}.
Thus
ΓHh = Cay Zn , {±1, . . . , ±(h − 1)} ,
For n ≥ 3 this is the usual power Cnh−1 . It is complete exactly when h − 1 ≥ ⌊n/2⌋; the Cayley
description also covers all boundary cases, including n = 1, 2, without ambiguity.
9
Back to the startPDF page 10
Theorem 5.1 (Cyclic interval optimum). For the cyclic action and interval promise Hh , the
minimum record alphabet is
n
m(n, h) = . (4)
⌊n/h⌋
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 ≥ 2;
the case s = 1 is immediate (equivalently, its sole circular gap is n). Thus an independent set of size
s satisfies sh ≤ n, so its size is at most k. The set
{0, h, 2h, . . . , (k − 1)h}
attains this bound, including the wraparound gap n − (k − 1)h ≥ h. Therefore every coloring needs
at least lnm
c=
k
colors.
For a matching coloring, let d = kc − n, so 0 ≤ d < k. Arrange the positions 0, . . . , 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 ≥ h; if c = h, then n = kh and
d = 0, while otherwise c − 1 ≥ 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 ≤ 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 Z6 , 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.
10
Back to the startPDF page 11
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 ≥ 2 and let
X = Zn × {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 ∈ End(A), output preservation gives F (a, i) = (fi (a), i). Commutation with T forces fi (a) =
a + ci , and commutation with R forces c0 = c1 . Hence
End(A) = {Fc : Fc (a, i) = (a + c, i), c ∈ Zn } ∼
= Zn .
Every endomorphism is already a permutation, so the canonical relation ρ is equality and Q = X.
The subset O = Zn × {0} is an invariant orbit, equivariantly isomorphic to the regular action of Zn
on itself. Restrict the public old-state promise to
H = {(q, 0) : 0 ≤ q < h}.
The unknown replacement Fc produces the final state (c + q, 0), and the functional characteristic
graph on the replacements is the Cayley graph displayed above (and, for n ≥ 3, Cnh−1 ). Theorem 5.1
therefore gives the minimum trusted record alphabet for this concrete Moore machine. This example
runs the full pipeline
A 7−→ S 7−→ (Q, G, H) 7−→ ΓH 7−→ χ(Γ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 replace-
ments.
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.
11
Back to the startPDF page 12
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.
12
Back to the startPDF page 13
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 identifica-
tion 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 chro-
matic 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 con-
structing 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.
13
Back to the startPDF page 14
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 tech-
nical 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.
14
Back to the startPDF page 15
[4] Attila Egri-Nagy and Chrystopher L. Nehaniv. Symmetries of automata. Algebra and Dis-
crete 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.
15
Back to the start