Source-linked AI summary
Defining the Crick-Franklin-Watson genes of any robot (equals a finite state machine) and defining the Shannon genetic code attached to each gene. We also define the Krohn-Rhodes complexity of any regular maximal prefix code
John Rhodes
TL;DR
The paper examines connections among codes and automata, random walks on finite semigroups, and Krohn–Rhodes complexity. It relates automata and their genes to Markov-chain quantities and stationary-time results, while noting that the synchronizing assumption excludes about half of mathematical Markov-chain cases.
Problem
The paper addresses relationships among codes and automata, random walks on finite semigroups, and techniques for deciding Krohn–Rhodes complexity c.
Source: §1.1 · p. 1, §2.1 · p. 2, §3 · p. 3Method
It models automata through finite semigroups and defines genes and their Shannon codes, relating these constructions to Markov-chain stationary distributions and strong stationary time.
Source: §2.1 · p. 2, §3 · p. 3, §5 · p. 6Results
The paper states that the automaton’s complexity c is the maximum of the flower-automaton complexities cfg over its genes, and that the reversed Shannon code has expected length 1/Pr(g).
Source: §3 · p. 3Takeaways & Limitations
The paper connects the left action on genes with Diaconis’ strong stationary time and associates each gene with a regular suffix-maximal Shannon code.
Source: §3 · p. 3, §5 · p. 6The synchronizing assumption excludes about half of mathematical Markov-chain cases, although the paper says it later extends the theory to the non-synchronizing case.
Source: §1.2 · p. 1
Abstract
from arXiv · showhide
This paper will discuss the relationships among three pillars of mathematics: important research in codes and automata by Marcel-Paul Schutzenberger and others; random walks on finite semigroups by Persi Diaconis and others; and advanced techniques from finite semigroup theory used in proving Krohn-Rhodes complexity c is decidable by Stuart Margolis, Anne Schilling, and myself. Very surprising connections exist between the Fundamental Lemma of Complexity c (epimorphisms between finite semigroups that are one-to-one on subgroups preserve c) and coupling from the past in Markov chains, Diaconis' strong stationary time, and the Crick-Franklin-Watson genes of a finite automaton (which will be defined in the paper).
1. Basic Assumptions
The paper takes finite-state-machine modeling as a basic assumption and considers synchronizing automata that can be returned to a fixed start state. It notes that this assumption excludes about half of mathematical Markov-chain cases, while stating that a later extension addresses the non-synchronizing case.
1. Basic Assumptions
- Anything can be modeled arbitrarily closely by a finite state machine, and the paper takes this as a basic mathematical assumption.It connects this assumption to Leibniz’s observation that anything can be written as a sequence of 0’s and 1’s.Source: §1.1 · p. 1
1.2. Synchronizing Assumption.
- A synchronizing sequence t returns every state of the automaton to a fixed start state q0.The paper describes this as pushing a reset button.Source: §1.2 · p. 1
- The synchronizing assumption is described as mild in the real world but excludes about half of mathematical Markov-chain cases; the paper says it later extends the theory to non-synchronizing cases.The stated extension is attributed to work with ChatGPT’s help.Source: §1.2 · p. 1
2. Coupling the Automaton with the Past
The section models time with a semigroup and introduces the right Karnofsky–Rhodes expansion as the robot’s genes: past-oriented structures that remember big events.
2.1. Time Convention.
- A semigroup with generators is treated as a model of time, with the section choosing a right-to-left time direction.The automaton is first mapped to its syntactic semigroup.Source: §2.1 · p. 2
2.2. The Right Karnofsky–Rhodes Expansion.
- A transition edge runs from q1 to q2 with no directed path back, marking a “big event” in the past.The passage contrasts this with a non-transition edge, where little has changed from q1 to q2.Source: §2.2 · p. 2
- The right Karnofsky–Rhodes expansion is called the robot’s genes, which go into the past and remember big events.Here, “right” means moving backward in time.Source: §2.3 · p. 2, §2.2 · p. 2
2.3. Genes.
- A gene is a word whose action is a constant map, equivalently a word in the minimal ideal; the expansion acts on genes to the left.The genes remember past events, while their left action proceeds forward in time.Source: §2.3 · pp. 2–3
3. Environment and Shannon Code of a Gene
The section defines each gene’s Shannon code from its first-return strings and relates code length to stationary probability. It also defines regular maximal prefix-code complexity and gives one- and two-state examples.
3. Environment and Shannon Code of a Gene
- Rg consists of first-return strings for gene g and is a regular suffix-maximal code called that gene’s Shannon code.The paper characterizes regularity as having a Kleene expression and being accepted by a finite state machine.Source: §3 · p. 3
- The expected length of the reversed first-return code for gene g is 1/Pr(g), where Pr(g) is its stationary probability.The stationary distribution is induced by the alphabet acting on the genes from the left.Source: §3 · p. 3
- The starting automaton’s Krohn–Rhodes complexity is the maximum complexity of its gene-based flower automata.The section defines code complexity using the reduced complete deterministic flower automaton of the reversed code.Source: §3 · p. 3
3.1. A One-State Automaton.
- In the one-state automaton, the average length of a string in Rg is the reciprocal of the gene’s stationary probability.The stationary distribution is forced by the input probabilities.Source: §3.1 · pp. 3–4
3.2. A Two-State Example.
- With equally likely inputs in the two-state example, the stationary gene probabilities are 1/2 for a, 2/6 for ba, and 1/6 for bba.The stated gene actions include a fixing the genes and b cycling among ba, bba, and ba.Source: §3.2 · p. 4
4. Details of Coupling from the Past
The construction traces paths backward in the right Cayley graph and retains transient edges. The resulting right Karnofsky–Rhodes structure is a subsemigroup of a semidirect product, and its left action completes the coupling-from-the-past pattern.
4. Details of Coupling from the Past
- Moving backward along the right Cayley graph, the construction omits edges whose endpoints are R-related, retaining the transient arrows.The resulting element records the arrows and the product αS.Source: §4 · pp. 5–6
- The construction multiplies arrow sets using the left action of the first semigroup component on the second component’s arrows.The section compares this right-then-left pattern with Munn’s construction and the Margolis–Meakin construction for Rabin tree automata.Source: §4 · p. 6
- The right Karnofsky–Rhodes construction is a subsemigroup of a right semidirect product of a semilattice with S.The section then calls for acting on the left to complete coupling from the past.Source: §4 · p. 6
5. Diaconis Strong Stationary Time and Rhodes–Schilling Synchronization Theory
The section relates the right Karnofsky–Rhodes action on a semigroup’s minimal ideal to Diaconis’ strong stationary time (SST). It then sketches an extension to general finite Markov chains through a group walk and synchronization, while labeling Subsection 5.1 conjectural.
5. Diaconis Strong Stationary Time and Rhodes–Schilling Synchronization Theory
- When the minimal ideal is zero, the left action of the right Karnofsky–Rhodes expansion on its genes satisfies Diaconis’ strong stationary time.The proposition identifies the minimal-ideal elements as the genes.Source: §5 · p. 6
- The stated 1/2 ℓ1 mixing bound is mix(t) ≤ E t + 1, with ϕ recording the first hit of the minimal ideal.The minimal-ideal elements are the genes.Source: §5 · pp. 6–7
- Acting on the left, the stationary gene probability sums the probabilities of strings that first hit 0 when read backwards; the distribution is unchanged by reversing time direction.The passage identifies this with the Rhodes–Schilling synchronization case.Source: §5 · p. 7
5.1. Chat Extension to the General Finite Markov Chain Case.
- Subsection 5.1 is explicitly presented as a conjecture that requires further expansion in a future paper.Source: §5.1 · p. 7
- The extension associates LLM(T) and RLM(T), with kernels LZ(T) and RZ(T), with the synchronized Rhodes–Schilling case.It defines a walk H on (G, X) with mixing time d(t), the group correction term after reverse lumping.Source: §5.1 · pp. 7–8
- In the example, the induced group walk is lazy nearest-neighbor on C5, with increments −1, 0, and 1 equally likely; the semigroup walk mixes once both components have mixed.Source: §5.1 · pp. 8–9
6. Memory and Semigroup Stabilizers
This section discusses semigroup stabilizers and proposes a conjectural interpretation of null elements as “junk” DNA. It states structural results for right stabilizers, including aperiodicity, chain structure, and idempotence under a further replacement.
6.1. Right Stabilizers.
- The right stabilizers of the left Karnofsky–Rhodes expansion are aperiodic and form an L-chain, hence are R-trivial.Source: §6.1 · p. 11
- After the indicated replacement, all right stabilizers become idempotent, forming a band.Source: §6.1 · p. 11
- Replacing sg(A) first by its left Karnofsky–Rhodes expansion yields a right stabilizer that is a band of idempotents forming an L-chain.Source: §6.1 · p. 11
- The section conjectures that null elements in the left stabilizer are “junk” DNA, where information written by genes can exceed available space.Source: §6.1 · p. 11
Appendix A. Every Finite Markov Chain Is a Random Walk on a Finite Semigroup
The appendix represents a stochastic matrix using right-monomial matrices of maps, connecting finite Markov chains with random walks on finite semigroups. It also distinguishes the shared stationary distribution from mixing-time bounds, which can differ between the two walks.
Appendix A. Every Finite Markov Chain Is a Random Walk on a Finite Semigroup
- M is written as a probability-weighted sum of right-monomial matrices, establishing the Birkhoff/von Neumann theorem for right stochastic square matrices.The semigroup is generated by the maps associated with those matrices.Source: Appendix A · p. 12
- The right Markov chain depends only on (g, b), while the stationary distribution is the same in both walk formulations and their mixing-time bounds can differ.Source: Appendix A · p. 12