arXiv CSopen access

Transcript-Managed Transformers: Monotone Multi-Agent Collapse and Universality with Two Pop-Enabled Transcripts

Transcript-Managed Transformers: Monotone Multi-Agent Collapse and Universality with Two Pop-Enabled Transcripts Sergey Salishev

arXiv:2607.29496v1 [cs.LG] 31 Jul 2026

AI Foundry San Francisco, CA, USA [email protected] Abstract—We study transcript management for fixed, finiteprecision causal Transformers. A transcript is partitioned into channels of bounded blocks. Each transition consults a fixed visible suffix and may append one block, leaving the model, weights, and token protocol unchanged. The operation Pc := PopContext(c) deletes the newest block on channel c and exposes its predecessor. We model the layer by the Transcript-Managed Transducer TMTk : one finite controller, k channels, and per-round actions from stay, push, and pop under a caller-driven status map. Fixed visible windows encode as finite symbols. The pop-free Restricted Transcript-Managed Transducer RTMTk is the standard appendonly layer and, for every fixed k, realizes exactly the deterministic finite-state transductions. The same holds for every fixed finite agent population under a monotone protocol that appends, routes, and copies visible blocks. Admitting {Pc }kc=1 restores pop. Newest-first, a pop-enabled channel is a stack; compiling to the Hopcroft–Ullman presentation transfers the classical hierarchy: DCFL for k = 1 and RE for every k ≥ 2. Orchestrated one-channel agents match one controller with k channels, so two pop-enabled transcripts— in one agent or two—suffice for universality. Simulation costs and invariance to fixed block size and visible radius are stated. The bounds fix precision, alphabets, blocks, visibility, controller state, and population; growing exact context, hidden-block access, writable stores, and unbounded Spawn add further state. Index Terms—Artificial intelligence, automata theory, finitestate machines, formal languages, multi-agent systems, transformers, Turing machines.

I. I NTRODUCTION Transformers are the standard architecture of modern AI [1], [2], [3], but deployed systems rarely use them as isolated fixed-window sequence predictors. Because consulting longer contexts increases memory and inference costs, systems deliberately manage transcripts during execution. Transcripts are split, copied, delegated, resumed, compressed, retrieved, and occasionally deleted. Reasoning scaffolds, tool loops, and multi-agent orchestration all rest on such transcript management [4], [5], [6]. This motivates a constructive question: Which local transcript operation completes the abstract bounded-transcript model to a universal machine, and can its semantics be added to a standard Transformer without changing the token protocol or additional memory storage?

Here a transcript is the sequence of bounded token blocks retained by the transcript manager between model calls. Each call receives the current input item and a fixed visible suffix of each transcript channel. The manager applies the returned transcript action. The new transcript operation Pc := PopContext(c) removes the newest block on channel c, so the preceding block enters the next visible suffix. Write P := P1 . Section III defines the Transcript-Managed Transducer TMTk , the normal form for this management layer. One finite controller drives k transcript channels. Each round consults the visible window of every channel together with the current symbol, performs one action per channel from stay, push, and pop, and emits at most one output symbol. A status map marks each control state as an input round, an internal round, or a halt, so the caller-supplied schedule is part of the model. Write TMT := TMT1 . The Restricted Transcript-Managed Transducer RTMTk is the pop-free case: every action is stay or push, which is the append-only layer of a standard deployment. Admitting Pc on every channel lifts that restriction and returns TMTk . The channels are the parts of the one transcript that the deployment already keeps, and k counts how many of them admit pop. A member of RTMTk and a member of TMTk can share a controller, a block alphabet, a visible radius, and a forward map; the second has one more available action. A pop deletes a block and exposes the block beneath it, so the retained transcript shortens. Read newest block first, a popenabled channel behaves as a stack. Lemma 1 compiles the normal form above into the Hopcroft–Ullman top-replacement presentation and back, with a bound on the steps per classical transition; that compilation is what lets the classical one- and two-stack classifications speak about TMTk , and two popenabled channels give universality. Theorems 1–3 are proved directly in the normal form fixed here. The abstract theorems classify the transcript manager. Any fixed choice of attention, depth, residual layers, and normalization supplies one finite local forward map under the stated precision and visibility bounds. We work under deployment constraints that stay fixed throughout: 1) finite precision and finite alphabets,

2) bounded transcript blocks and bounded exact visibility, 3) a fixed finite agent population with finite-state orchestration over agent transcripts, 4) the standard fixed, nontrainable execution schedule. a) Hierarchy summary: Under these assumptions, write Trans(C) for the input/output transductions realized by a machine class C, Acc(C) for its accepted languages, MONm for the class of monotone orchestrations with exactly m agents, and OTMk for the class of Orchestrated Transcript Machines: k one-channel agents under one finite-state orchestration controller that owns their transcripts (Definition 9). For fixed k and m, the transduction and acceptance classification is Trans(RTMTk ) = Trans(FST), Trans(MONm ) = Trans(FST), Trans(OTMk ) = Trans(TMTk ), Acc(TMT1 ) = DCFL, Acc(TMTk ) = RE

(k ≥ 2).

We prove the three transduction identities. The two acceptance identities are the classical one- and two-stack classifications, transferred to this normal form by Lemma 1 and recorded in Corollary 3 and Theorem 4. b) Results and contributions: This paper proves the fixed-population monotone collapse and the tagged-transcript normal form with its correspondence to bounded-transcript controllers, including the equivalence between k orchestrated one-channel agents and one controller with k channels together with the simulation costs. The one- and two-stack acceptance classifications are classical, and Lemma 1 carries them into the normal form used here. 1) Monotone collapse. Every fixed finite collection of agents under a standard monotone protocol that may append, route, and copy currently visible blocks realizes exactly the finite-state transductions. The theorem permits arbitrary finite controller logic and any sequence of the allowed local and transcript operations. Their joint visible configuration forms a finite global summary that determines every future transition. The same summary also covers finite-branching nondeterministic acceptance and finite-precision sampling under positive-probability acceptance. The consequence for deployment is concrete: with a fixed visible window, an append-and-copy agent population cannot parse a general programming language, however large the retained transcript grows. This limitation is visible in practice, through external grammars and symbolic checkers in program synthesis [7], [8], context-free generalization failures without stack memory [9], and unbounded repetition in deployed agents [6]; our theorem states it directly for every fixed population. 2) Transcript and agent correspondence. We show how a bounded channel-tagged physical transcript instantiates RTMTk and how a fixed-precision Transformer supplies its local transition map. A separate theorem equates the transductions of k orchestrated one-channel agents with those of one controller using k pop-enabled channels.

An orchestrator that pops the transcripts of two agents therefore has the power of one agent with two pop-enabled channels, which covers both deployed layouts with one classification. 3) Exact hierarchy and invariance to fixed bounds. Every fixed visible radius can be encoded in one symbol from a finite enlarged alphabet (Proposition 1). One TMTk round costs at most k orchestration steps, one Turing-machine step costs O(1) two-agent steps, and t stack operations use O(t) transcript blocks (Proposition 2). One pop-enabled channel gives the deterministic context-free languages; every fixed k ≥ 2 gives the recursively enumerable languages, and additional channels may remain unused. All effective universal augmentations accept this same language class. The intermediate DPDA level is the first practical step beyond finite-state behavior once exact pop is available: deterministic parsing [10] and structured instruction languages [11], [12]. c) Scope: The upper bounds apply when the exact state consulted by one transition ranges over a finite set. Bounded windows, finite-state compaction, and bounded exact transcript visibility satisfy this condition. If F is the finite floating-point set, then every positional map p : N → Fd has image im(p) := {p(t) : t ∈ N} ⊆ Fd , the set of positional vectors produced by p, so | im(p)| ≤ |F|d < ∞. The bound comes from the precision of F alone, and no hypothesis on the rule generating p is required. Because the domain N is infinite while im(p) is not, p must repeat addresses, so position by itself supplies no unbounded consulted state however far the index runs. Under exact real or unbounded-precision arithmetic the same map may take infinitely many values and this bound fails. Models that later consult an exact unbounded sequence, an unbounded writable store, or an unbounded population of spawned agents have a growing consulted-state space. Standard read-only RAG into a bounded visible window supplies bounded external input [13], [14]. The same finite-state assumption appears in formal analyses of restricted transformers [15], [16], [17] and in classical memory-bounded computation [18]; see Section II. II. R ELATED W ORK The computational power of attention-based architectures has been studied from several directions. At the architectural level, the vanilla Transformer of Vaswani et al. [1] does not prescribe how a deployment must manage context size beyond attention. Extensions with unbounded retained context can therefore look like natural continuations of the same architecture even though they introduce a different computational resource.

The following literature provides architectural upper bounds and broader context for our contribution. a) Transformer upper bounds: Here n denotes input length. Hahn’s fixed-layer restricted self-attention is not universal: it cannot recognize even some regular languages [15]. In the same hard-attention regime, Hao, Angluin, and Frank place unique-hard attention within AC0 , the constant-depth polynomial-size circuits of unbounded-fan-in Boolean gates, while averaging-hard attention already recognizes the non-AC0 languages M AJORITY and DYCK-1 [19]. Since AC0 excludes parity, the unique-hard bound is strictly stronger than the threshold-circuit bounds that follow. The saturated-transformer result is a nonuniform constant-depth threshold-circuit upper bound and classifies a circuit family [16]. For O(log n)-bit arithmetic, logspace-uniform threshold-circuit simulations imply, under the standard conjecture that deterministic logarithmic space is weaker than deterministic polynomial time, that one forward pass misses some polynomial-time problems and therefore is not universal [17]. Strobl et al. survey these and other formal-language results, emphasizing that their apparently conflicting conclusions depend on precision, positional encodings, attention variants, and uniformity assumptions [20]. b) Neural formal-language learning: Bhattamishra et al. give Transformer constructions for a restricted family of counter languages and empirically evaluate formal-language recognition, including an bn cn [21]. Their positive finite-range result uses the entire growing prefix and normalized prefix counts; their stated finite-precision guarantee for this construction is bounded by the available bits. Their construction uses growing consulted context. Our classification fixes the visible context. Their finite-range result also supports the empirical possibility of learning a two-counter procedure. Delétang et al. train RNNs, LSTMs, Transformers, and stack- or tapeaugmented RNNs on transduction tasks spanning the Chomsky hierarchy [9]. Their stack and tape action policies are learned end-to-end, but both memory modules are attached to RNN controllers; their evaluated Transformer is unaugmented. That baseline enters Table I as the row retaining no memory at all: Theorem 1 fixes it at finite-state, and the deterministic contextfree tasks it misses are exactly those one pop-enabled channel supplies. Length generalization reported in this literature is partial, and two separate conditions govern it: the architecture must be able to represent the required memory discipline, and training must actually find that representation. Bhattamishra et al. show that gradient descent biases Transformers toward simple, low-sensitivity functions, so the second condition can fail even where the first holds [22]. Our expressivity results speak only to the first. c) Relation to classical stack models: Classical memory bounds already induce strict computational hierarchies [18]. At the language-acceptance level, one stack gives DCFL and two stacks give RE; equivalently, the two-stack machine model is Turing complete [23], [24]. We reach these results through a transducer normal form built for the deployed Transformer interface. Lemma 1 compiles that form into the Hopcroft–Ullman top-replacement presentation and back with

step bounds, which is where the classical acceptance results enter. Our transduction theorems are proved in the new normal form itself, and we identify PopContext with the pop action omitted by the append-only management layer. Our abstract results establish the tagged-transcript correspondence and the monotone multi-agent collapse under fixed finite consulted state (Definition 3). PopContext is not the only conceivable memory primitive, and related classical intermediate variants delimit the space of alternatives: pushdown transducers, visibly pushdown automata [25], counter machines [23], and ordered multi-pushdown systems [26]. The maximality discussion in Section IV is accordingly stated at the language-acceptance level for effective universal augmentations, not as a claim that PopContext is the unique smallest extension increasing the language acceptance power of the Transformer. d) Post-training automaton extraction: Weiss et al. take a fixed, already-trained RNN acceptor and use it as the membership oracle for Angluin’s L∗ algorithm [27]. A finite abstraction of the RNN is compared with each candidate deterministic finite automaton (DFA); a disagreement yields either a counterexample to the DFA or a refinement of the abstraction after consulting the RNN. The result is a DFA extracted after neural training. Its relevance here is limited to the pattern of extracting an automaton after neural training. At the acceptance level, a DFA is a DPDA that never uses its stack, and the inclusion is strict [24]. An L∗ -style extraction therefore reaches exactly the append-only level of Theorem 1 and supplies no method for extracting a DPDA from a general TMT1 acceptor. The remaining items are organized by which resource is allowed to grow and whether that growth yields universality. To keep heterogeneous results comparable, we read each cited model along the axes stressed by the survey of Strobl et al. [20]: numerical precision; whether memory grows with input or runtime; whether that memory is writable and exactly accessible; whether the control policy is learned or supplied; and whether the stated result concerns recognition, transduction, or finite-range learning. Table I summarizes the comparison. Its Task column gives the generic setting a work evaluates, and Growing Memory names the resource the mechanism allows to grow. Access describes the deployed read and update: soft when they are continuous or latent, exact when push and pop are hard, and lossy when retained content is replaced by a summary; a qualifier such as append-only records an operation the mechanism omits, and a dash marks a mechanism with no such memory to access. Representative power is the language class of that growing memory taken in its idealized exact form, so it states what the mechanism can express rather than what the cited work claims or demonstrates. Turing completeness is recorded as RE. The last two columns therefore say together whether growth buys anything. This reading makes mechanisms comparable across works whose evidence is otherwise incommensurable. Here DCFL ⊊ CFL separates the deterministic from the nondeterministic stack relaxations, and a second exact unbounded store lifts either to RE. Every row keeps a finite controller, so the comparison stays within

deployable architectures rather than the unbounded-precision constructions of [28]. e) Unbounded exact state: Pérez, Barceló, and Marinkovic prove Turing completeness using arbitraryprecision rational representations [28]. This is outside fixed precision. Bhattamishra, Patel, and Goyal likewise analyze Transformer computational power and universality under explicit model-specific assumptions [39]. The relevant classical caveat is that even two unbounded counters (equivalently, two integer registers with suitable counter operations) already suffice for Turing completeness [23]; a fixed register count is finite-state only when register values range over a fixed finite set. Universal Transformers add recurrence and obtain stronger capabilities under their own assumptions [40]. Oren et al. cast decoder-only transformers as multi-state RNNs whose growing key-value cache provides an unbounded exact retained sequence [14]; this holds in the idealized unbounded-length formulation, whereas a real finiteprecision deployment with a compressed or bounded cache remains finite-state in our formalization. An unbounded exact sequence that each step may read and extend is a universal resource, since writing successive machine configurations to it simulates a Turing machine step by step, which is how the chain-of-thought simulations of [41], [42] proceed; Table I records RE for that idealized cache and not as a claim of theirs. Their own experiments point the same way: fixing the cache size yields a bounded multi-state recurrent model that performs nearly on par with the full one. The growing memory recorded for them in Table I is therefore the idealized uncapped cache, not the one their experiments retain. f) Differentiable stacks: Differentiable stacks introduce another form of exact state in their idealized temperature τ > 0 formulation: continuous block strengths range over exact real values. Grefenstette et al. introduced continuous block strengths, newest-first fractional pop, and unit-mass top reads, and report that the resulting models often recover the underlying generating algorithm of a synthetic transduction grammar [29]. That work instantiates the same machinery as a queue and as a double-ended queue; taken exactly, either is Turing-equivalent, a queue by the standard queuemachine simulation of a tape and a double-ended queue by exposing two stack ends at once, which is the second entry recorded in its row. Joulin and Mikolov proposed a distinct superposition stack with soft push, pop, and no-op, and learn algorithmic sequences that require counting and memorization [30]. They also run configurations holding several stacks, and two exact unbounded stacks already suffice for Turing completeness [23], [24], which is the second entry in their row. DuSell and Chiang replaced the deterministic relaxation by a weighting over nondeterministic stack runs, which reaches the context-free class on language recognition [31]. The deterministic variants provide deterministic pushdown power, hence DCFL, and the nondeterministic variants reach the full context-free class CFL, which strictly contains it. The same relaxations were later carried into Transformer attention, where the nondeterministic variant again represents

CFL [33], and Chung and Siegelmann extend their construction to Grefenstette-style neural stacks [32]. These are readings of the idealized exact structure, not claims made by the cited works; each soft relaxation is evaluated on learning, and none of them establishes the class recorded in Table I. g) Tape and stack-augmented RNN and Transformers: With RNN controllers, the stack-augmented networks of Joulin and Mikolov [30] and of DuSell and Chiang [31] learn algorithmic and context-free patterns, and the tape-augmented models evaluated above sit in the same family [9]. Chung and Siegelmann prove Turing completeness for a boundedprecision RNN with two dynamically growing stack modules [32]; their universality uses two unbounded stores with exact push and pop behavior rather than the relaxation. With Transformer controllers, Stack Attention places the store inside the attention operator and is evaluated on language recognition [33], Pushdown Layers maintain a stack-like tape synchronously during autoregressive prediction to modulate attention, improving syntactic generalization in language modeling [34], and StackTrans inserts a differentiable stack of hidden states between Transformer layers rather than along the transcript, motivated explicitly by the pushdown automaton as the minimal model for deterministic context-free grammars and evaluated on Chomsky-hierarchy tasks as well as naturallanguage reasoning benchmarks [35]. Both Transformer-side stores are driven by soft push, pop, and no-op updates on a single stack, so each idealizes to a deterministic pushdown store and is recorded at DCFL. StackTrans is instructive here because its deployed form returns to our finite-state regime in two independent ways. Its stack is allocated at a fixed size S, small in their experiments, with overflow truncated to zero, which the authors describe as a form of forgetting; and training parallelism is recovered by breaking the temporal dependency, so that stack operations run over the layers of a single token rather than along the token sequence. Either restriction alone confines the reachable stack configurations to a fixed finite set, so Definition 3 is satisfied and Theorem 1 applies. The DCFL entry is therefore the idealization the authors themselves state, an unbounded stack driven along the token sequence, and not the model they train. The evaluated task therefore matters for reading these rows: a language-class theorem and a benchmark gain are not comparable evidence, so Table I records the task and the controller alongside the idealized power rather than collapsing them. Our model differs from both lines in that the store is the tagged Transformer transcript itself rather than a dedicated soft or latent memory module: each channel admits exact push, stay, and pop in the TMTk normal form. h) Memory and retrieval: Transformer-XL introduces segment-level recurrence over cached hidden states [36], whose span Rae and Razavi then vary to ask how much of that memory the model actually needs [43]. Separately, compressive and embedding-based memories replace retained history by a finite summary [37], [38]. In both, the retained context keeps growing as further history is folded in, but what a step may consult of it does not: the cached span is fixed, and the summary has a fixed number of slots that

TABLE I S TACK - AND MEMORY- AUGMENTED NEURAL MODELS , GROUPED BY CONTROLLER . C OLUMNS ARE DEFINED IN THE TEXT; POWER IS THAT OF THE GROWING MEMORY IN ITS IDEALIZED EXACT FORM , NOT A CLAIM OF THE CITED WORK . Work Grefenstette et al. [29] Joulin and Mikolov [30] DuSell and Chiang [31] Chung and Siegelmann [32] Stack Attention [33] Pushdown Layers [34] StackTrans [35] Oren et al. [14] Transformer-XL [36] Compressed memory [37], [38] Unaugmented Transformer [9] This work

Task Sequence transduction Algorithmic sequences Language recognition

Controller RNN

Access Soft

RNN

Growing Memory Differentiable stack, queue, DeQue Differentiable stacks

RNN

Nondeterministic stack

Soft

Representative power DCFL (stack), RE (queue, DeQue) DCFL (stack), RE (two stacks) CFL

Machine simulation

RNN

Two unbounded stacks

Exact

RE

Language recognition Language modeling Chomsky hierarchy, reasoning Long-context modeling Long-context modeling Long-context modeling Sequence transduction Sequence transduction

Transformer Transformer Transformer

Stack inside attention Stack-like tape Hidden-state stack

Soft Soft Soft

CFL DCFL DCFL

Transformer

Key-value cache

Exact, append-only

RE

Transformer

Cached segment states

Exact

Finite-state

Transformer

Context

Lossy

Finite-state

Transformer

None

—

Finite-state

Any finite controller

Tagged transcript

Exact

DCFL (k = 1), RE (k ≥ 2)

successive compressions overwrite. Table I therefore lists a growing memory for these rows and still records them as finitestate. How far the raw transcript grows does not affect the classification, because a standard Transformer consults only a bounded visible window: the exact state entering one transition ranges over a finite set whatever is retained behind it, and Theorem 1 applies. Compaction and compression therefore change retention cost, not computational class. Length generalization also depends on positional encoding [44], [45]: under fixed floating-point arithmetic, rotary encodings [46] are constrained by the RoPE base [47] and may lose positional distinctions when phases become indistinguishable [48]. None of these works presents a Turing-universality result. With fixed precision and fixed cache, slot, and window bounds, their models remain finite-state in our formalization. Allowing retained activations or memory slots to grow without bound and remain exactly consultable supplies growing consulted state. A universality result additionally requires suitable state transitions. The same resource distinction applies to retrieval. Standard RAG retrieves a bounded chunk from a read-only document store into the visible window. Because the store is read-only and the retrieved chunk is bounded, it supplies bounded external input [13]. An exact store that the agent can update and later query supplies persistent state and can support universal computation given suitable read/write addressing. i) Iteration and CoT: Merrill and Sabharwal show that generalized pre-norm Transformers with a polynomially bounded chain of thought recognize exactly the decision problems in P [41]. Their model lets each step consult a growing transcript, uses logarithmic precision, and places a polynomial bound on the chain-of-thought length. Feng et al. show added

Soft

effective depth for bounded written derivations [49]. Our theorem fixes the exact consulted state of each step. Under this condition, append-only CoT eventually cycles (Corollary 1). This predicts eventual repetition of tool-and-thought cycles observed in deployed agents [6]. j) Context, agents, and external tools: Li and Wang simulate space-s(n) Turing machines with constant-bit Transformers using an O(s(n)) context and O(s(n)c ) chain-of-thought steps per simulated step, for arbitrarily small fixed c > 0 [42]. Their exact transcript grows with the simulated space. Our monotone-collapse theorem fixes the exact consulted state, so the two results describe different context regimes. Rizvi-Martel et al. study how agent count, bandwidth, and communication depth affect multi-agent reasoning tasks [50]. Our theorem classifies every fixed finite population governed by arbitrary finite controller logic and the stated local-call, append, routing, and visible-copy operations. Tool and function calls may supply computation oracles, but their computational effect depends entirely on the interface: a tool may be a finite-state transducer, a computable subroutine, a read-only database, a writable store, or an undecidable oracle [51]. Our bounds assume the finite-state and read-only cases; writable store interface or undecidable tools add a separate computational resource. III. M ODEL A. Transcript-Managed Transducer We first define the Transcript-Managed Transducer TMTk , the deterministic transducer normal form used throughout the paper. The deployed Transformer interface shapes it: one round per model call, one transcript action per channel and

at most one output symbol per round, one written block per push, a status map that marks input rounds and internal rounds, and a right-end marker with an explicit completed-run convention. A pop on an empty channel is a no-op, matching a transcript that stops at empty. Lemma 1 compiles this form into the Hopcroft–Ullman top-replacement presentation of the pushdown and multi-pushdown models [24], [26] and back, with a step bound in each direction, so a result stated for either form applies to both. The theorems of Section IV work in the form fixed here; that compilation is what carries the classical acceptance classifications across. The symbols ⊥ and ⊣ are distinguished internal-step and right-end markers, respectively, outside every input alphabet. Definition 1 (Transcript-Managed Transducer TMTk ). Define the stack-control alphabet Astk := {stay, push, pop}. Fix k ≥ 1. A k-channel Transcript-Managed Transducer is a tuple A := (QA , Σ, Ω, Λ, #, δA , χA , q0 ), where QA is a finite nonempty set of control states, q0 ∈ QA is the initial control state, Σ and Ω are finite input and output alphabets, Λ is a finite nonempty stack alphabet, and # ∈ /Λ is the bottom marker. The status map

defines no completed transduction. The transducer’s output on a completed run is the concatenation of its nonsilent emissions. For language recognition, partition the halting states into accepting and rejecting sets, rej acc ˙ χ−1 A (halt) = QA ∪ QA .

A completed run accepts or rejects according to the subset containing its final state. This specialization is a TMTk acceptor; it is a decider when every input completes in one of the two subsets. For fixed k, let TMTk also denote the class of these instances, and write TMT := TMT1 . Word c of the configuration is transcript channel c, and its rightmost symbol is the block currently exposed to the controller. Read newest block first, channel c behaves as a stack over Λ, and for k = 1 the acceptor is a deterministic pushdown acceptor. We use stack vocabulary for the three actions throughout, with the understanding that each channel holds the blocks the deployment already retains. Dropping the stack alphabets, stack arguments, and stack actions gives the ordinary deterministic finite-state transducer under the same input, stopping, and completion conventions; write FST for this class. Definition 2 (Hopcroft–Ullman top-replacement presentation). Take the Hopcroft–Ullman top-replacement transition form coordinatewise over k stacks, as in the standard multi-pushdown model [24], [26]. A deterministic, output-bearing instance is

χA : QA → {input, internal, halt} determines whether the next round consumes input or is internal, and marks halting states. It is a fixed component of the abstract transduction semantics. Set Σ⊥ := Σ ∪ {⊣, ⊥},

Q◦A := χ−1 A ({input, internal}),

and let δA : Q◦A × Σ⊥ × (Λ ∪ {#})k → QA × Akstk × Λk × (Ω ∪ {ε}). On input w ∈ Σ∗ , the initial configuration is (q0 , w ⊣, #, . . . , #). A configuration records a control state, the unread suffix of w ⊣, and k stack words in #Λ∗ . If χA (q) = input, the round supplies and consumes the first unread symbol; if χA (q) = internal, it supplies ⊥ without consuming input. The transducer applies δA to that symbol and the k top symbols, performs the returned actions simultaneously, and emits the returned output; ε is silent. The rightmost symbol of each stack word is its top. Stay leaves that word unchanged, push appends its returned write symbol, and pop removes the rightmost symbol when it lies above #. If the action and write tuples are a = (a1 , . . . , ak ) and λ = (λ1 , . . . , λk ), then action push on stack c writes λc ; the value λc is ignored for stay and pop. A pop on # leaves that stack unchanged. A run stops exactly on entering a state q with χA (q) = halt. The stopped run is complete exactly when ⊣ has been consumed, so the unread suffix is empty; a premature halt, an input request with empty unread suffix, or an infinite run

H := (Q, Σ, Ω, Λ, #, q0 , Qacc , Qrej , δHU ), where the finite sets and distinguished symbols have the meanings in Definition 1, Qacc ∩ Qrej = ∅, and, writing Λ# := Λ ∪ {#} and Σ := Σ ∪ {⊣},
δHU : Q \ (Qacc ∪ Qrej ) × (Σ ∪ {ε}) × Λk# ⇀ Q × (Λ∗# )k × (Ω ∪ {ε}). If δHU (q, a, γ1 , . . . , γk ) = (q ′ , u1 , . . . , uk , o), then a ∈ Σ consumes a, whereas a = ε consumes nothing, and each stack βc γc becomes βc uc . To preserve the unique bottom marker, require uc ∈ Λ∗ when γc ̸= # and uc ∈ #Λ∗ when γc = #. Determinism means that the map is single-valued and, whenever its ε-transition is defined for (q, γ1 , . . . , γk ), no input-consuming transition is defined for the same state and top tuple. The run starts from (q0 , w ⊣, #, . . . , #), stops on entering Qacc ∪ Qrej , and is complete exactly when ⊣ has been consumed. A missing transition or an infinite run is incomplete; outputs and acceptance follow Definition 1. Lemma 1 (Hopcroft–Ullman multi-stack normal form). For every fixed k ≥ 1, Definitions 1 and 2 realize exactly the same completed transductions and accept exactly the same languages. Let L be the length of the longest replacement word in a given δHU table. One transition of that table compiles into at most 2 + k(L + 1) rounds of Definition 1, and one round of Definition 1 compiles into one transition of a δHU table with L ≤ 2.

Proof. Let L := max({0} ∪ {|uc | : uc occurs in the transition table}). To compile δHU into Definition 1, an internal dispatcher uses (q, γ1 , . . . , γk ) to select an ε-transition when one exists and otherwise enters an input state. After selecting the transition, finite control stores (q ′ , u1 , . . . , uk , o) and, in a fixed stack order, replaces each old top by one pop followed by the symbols of uc . When γc = #, write uc = #vc , retain #, and push only the symbols of vc . At most L pushes are needed per stack; emitting o only on the final simulated step gives at most 2 + k(L + 1) steps per classical transition. Undefined transitions enter a fixed nonhalting internal sink. Conversely, one step of Definition 1 is one δHU transition. For current top γc , set  ac = stay,  γ c ,  ε, ac = pop and γc ̸= #, uc := #, ac = pop and γc = #,    γc λc , ac = push.

C. Restricted Transcript-Managed Transducer

Label it by the supplied input symbol when χA (q) = input and by ε when χA (q) = internal, and retain the same next state and output. Halting states have no outgoing transition. Both compilations preserve the input suffix, stacks, state, and accumulated output at transition boundaries, which proves the claim.

whose action tuple returned by δA always lies in Akapp . Thus pop is the only stack action excluded, and every member of RTMTk is one agent with one finite controller. Stack c is called transcript channel c, and Λ is its finite abstract transcript alphabet. By convention,

The forward direction serializes an unbounded-width top replacement into rounds of bounded width, which is what the one-action-per-model-call interface requires. Through this lemma the classical one- and two-stack acceptance results speak about the normal form of Definition 1 (Corollary 3 and Theorem 4). The transduction theorems of Section IV are proved in that normal form and use the lemma nowhere.

Thus RTMTk is the append-only management layer of a standard deployment: blocks accumulate, and each call consults the visible window of every channel.

B. Finite blocks and channels Fix a finite nonempty token alphabet Γ. Fix a block bound B ≥ 1. Let ∆ := Γ[1,B] := {w ∈ Γ∗ : 1 ≤ |w| ≤ B}. Because Γ is finite and B is fixed, the block alphabet ∆ is finite. For r ≥ 0, write ∆≤r := {s ∈ ∆∗ : |s| ≤ r} = {ε} ∪ ∆[1,r] , where ∆[1,r] := {s ∈ ∆∗ : 1 ≤ |s| ≤ r} and ∆[1,0] := ∅. For each fixed integer k ≥ 1, let

Definition 3 (Finite consulted state). A system has finite consulted state if its joint exact configuration consulted in one transition ranges over a finite set. Equivalently, its one-step transition factors through a finite consulted-state space. An unbounded sequence still has finite consulted state when every transition consults a finite summary. Exact random access, exact rescan, and unbounded persistent controller state can create infinitely many distinguishable retained configurations. Definition 4 (Restricted Transcript-Managed Transducer RTMTk ). Define the append-only stack-control alphabet by Aapp := {stay, push}. For fixed k ≥ 1, define the Restricted Transcript-Managed Transducer class RTMTk as the class of instances A := (QA , Σ, Ω, Λ, #, δA , χA , q0 ) ∈ TMTk

RTMT := RTMT1 .

Definition 5 (PopContext). The primitive Pc := PopContext(c) is the action pop of Definition 1 on channel c, the one action omitted by RTMTk . On a tagged transcript H = u(c, x)v whose suffix v contains no block tagged c, Pc (H) = uv, and Pc is a no-op when channel c is empty. For one channel, write P := P1 = PopContext, so RTMT1 + P abbreviates RTMT1 + {P1 }. Admitting {Pc }kc=1 restores the action range Akstk , hence RTMTk + {Pc }kc=1 = TMTk .

A k-channel transcript is a word H ∈ ∆∗k . Thus every bounded transcript block is explicitly tagged by its channel. For c ∈ Ck , write πc (H) ∈ ∆∗

Remark 1 (What k and Pc supply). The k channels partition the blocks of one transcript, so k is a property of the caller’s bookkeeping. The power comes from re-exposing a block that append-only visibility had already passed: once a buried block can return, the finite summary of Theorem 1 no longer determines the future, and the channel contents below the visible window become consultable memory.

for the channel-c projection obtained by retaining the payloads of precisely the blocks tagged c, in their original order. When k = 1, we identify (1, x) with x, so a one-channel transcript is simply a word in ∆∗ .

The abstract TMT1 normal form reads one current top symbol. The published GPT-2 and GPT-3 context sizes of 1024 and 2048 tokens state large fixed physical radii [2], [3]. The recoding below packs any fixed physical window into

Ck := {1, . . . , k}

and

∆k := Ck × ∆.

that symbol. For a block alphabet ∆ and Pr visible radius r, the resulting window alphabet contains j=1 |∆|j symbols. Increasing a fixed r enlarges the finite local state space. Every fixed value of r has the same transduction power. A growing radius r = r(n) gives a growing-consulted-state model.

b r . Its Store ζ1 · · · ζt on the corresponding RTMTk stack over ∆ top is exactly the window consulted by the transcript system. Appending bt+1 pushes

Definition 6 (Abstract bounded-transcript controller). Fix k, r ≥ 1, finite input and output alphabets Σ and Ω, a finite nonempty block alphabet ∆, a finite nonempty control set Q, an initial state q0 ∈ Q, and a status map χ : Q → {input, internal, halt}. For a physical transcript H ∈ ∆∗k , define
vis(k) r (H) := visr (π1 (H)), . . . , visr (πk (H)) ,

with the empty channel handled by #. Hence every transcript step is one pop-free stack-transducer step: an append tagged c pushes ζt+1 on stack c, and all other stack actions stay. The control, status, and output are unchanged. A physical Pc removes ζt and exposes ζt−1 , so the encoding commutes with abstract pop. Conversely, for an RTMTk with stack alphabet Λ, take the physical block alphabet to be ∆′ := Λ, set r = 1, and use one transcript channel for each stack. The finite controller stores the returned action, write, and output tuples. If all actions stay, one simulation step emits the output and enters the next abstract control state. Otherwise, the first simulation step receives the symbol selected by the abstract status, and the controller serializes the non-stay channel actions in increasing channel order. Every remaining step is internal and silent; only the final step emits the pending output and enters the next abstract control state. There are at most k simulation steps and at most k − 1 auxiliary steps. In the pop-enabled form, push and pop are serialized identically. Induction at simulation boundaries preserves the control state, channel contents, unread suffix, status, emitted output, stopping, and completion. This serialization establishes transduction equivalence. The sample model applies one hard or relaxed stack action inside each caller-supplied token position.

where visr (πc (H)) is the longest suffix of channel c containing at most r blocks. For s ∈ ∆≤r and x ∈ ∆ ∪ {ε}, let trimr (sx) be the longest suffix of sx containing at most r blocks. Set Q◦ := χ−1 ({input, internal}). A boundedtranscript controller, used below as the wrapper transducer, is the tuple W := (Q, Σ, Ω, ∆, k, r, χ, q0 , g), where g : Q◦ × Σ⊥ × (∆≤r )k −→ Q × (∆k ∪ {ε}) × (Ω ∪ {ε}), is its step map. Its configuration contains a physical transcript H ∈ ∆∗k , and g consults vis(k) r (H). The last argument is an ordered tuple: its coordinate is the channel identity. Thus g may apply any fixed-width map, including attention after adding a channel-ID vector to each coordinate. Initially H = ε. A returned (c, b) ∈ ∆k appends that tagged block; the returned ε performs no append. Input consumption, output, stopping, and completion follow Definition 1. The status and completed-run convention belong to this abstract wrapper, not to the deployed decoder. In the pop-enabled form, replace the transcript-action codomain by ∆k ∪ {P1 , . . . , Pk , ε}, so one abstract simulation step performs at most one append or pop. Proposition 1 (Bounded-transcript correspondence). Every bounded-transcript controller induces a member of RTMTk . Conversely, every member of RTMTk has a boundedtranscript realization for some finite physical block alphabet and r = 1, using at most k abstract simulation steps per source transition, at most k − 1 of them silent. In the popenabled form, the correspondence identifies each physical Pc with pop on abstract stack c.

ζt+1 := trimr (ζt bt+1 ),

Thus every fixed physical radius has an equivalent r = 1 realization and carries no additional theoretical power. Remark 2 (Transformer instantiation). Consider the standard causally masked decoder stack of Transformer blocks [1], with token vocabulary V , finite-precision number system F, embedding dimension d, and fixed weights in F. A transcriptmanager wrapper selects the finite visible suffix supplied to the standard forward map. Write the decoder instance as D := V, F, d, N, L, (Hℓ )L−1 ℓ=0 , e, p,
ℓ,a (WQℓ,a , WK , WVℓ,a )0≤ℓ<L , (Blockℓ )L−1 ℓ=0 , Wout , bout , a∈Hℓ

where N is the maximum context length, L is the number of layers, Hℓ is the finite head set of layer ℓ, and Blockℓ contains that layer’s remaining fixed Transformer operations. For each a ∈ Hℓ , let dℓ,a ≥ 1 be the head width. The coordinates in this tuple have types e : V → Fd ,

p : {1, . . . , N } → Fd ,

ℓ,a WQℓ,a , WK , WVℓ,a ∈ Fdℓ,a ×d ,

Proof. Define the finite window alphabet b r := ∆[1,r] = {s ∈ ∆∗ : 1 ≤ |s| ≤ r}. ∆

Blockℓ : Fd × F

For a channel word b1 · · · bt ∈ ∆∗ , set ζ0 := ε and define the window symbols

Wout ∈ F|V |×d ,

b r. ζj := visr (b1 · · · bj ) ∈ ∆

P

a∈Hℓ dℓ,a

→ Fd ,

bout ∈ F|V | .

Let FD : V [1,N ] −→ F|V |

[1,N ]

be its standard forward map at maximum context length N , with FD (V n ) ⊆ (F|V | )n for every 1 ≤ n ≤ N . Instantiate the wrapper transducer of Definition 6 with k := 1, so it exposes one transcript suffix of at most r blocks. Fix a transcript tokenizer Tok : Σ⊥ × ∆≤r −→ V [1,N ] and a finite state/action/output decoder
[1,N ] Dec : Q◦ × Σ⊥ × F|V |

and the controller fixes an initial state qctl,0 ∈ Qctl . It also fixes a global status map χctl : Qctl → {input, internal, halt}. It governs the shared input convention: the agents have no separate unread-input cursors, and a selected local transition receives the symbol chosen from the single global unread suffix. The population is fixed and finite, as required by the collapse results below; unbounded Spawn is treated separately.

−→ Q × (∆ ∪ {ε}) × (Ω ∪ {ε}).

Definition 7 (Monotone protocol). A monotone protocol step Under the standing k = 1 identification (1, x) ↔ x, the is any deterministic controller action that depends only on transcript-action codomain ∆ ∪ {ε} matches the general wrap- 1) the current controller state, per’s ∆1 ∪ {ε}. Thus r is the maximum number of exposed 2) the current symbol in Σ⊥ , physical transcript blocks. The parameter N is the maximum 3) the current local agent states, number of tokens accepted by D; Tok serializes the exposed 4) the exposed blocks top# (H1 ), . . . , top# (Hm ), blocks and current input symbol within that token bound. For and which, apart from finite controller-state updates, performs s ∈ ∆≤r , define at most one of the following transcript actions:
(M1) execute one step of one agent’s bounded-transcript realgD,Tok,Dec (q, x, s) := Dec q, x, FD (Tok(x, s)) . ization whose input/internal status agrees with χctl (qctl ), (M2) append one block from ∆ to some transcript, The resulting wrapped Transformer transducer is (M3) copy an exposed block to the end of another transcript.
W[D, Tok, Dec] := Q, Σ, Ω, ∆, 1, r, χ, q0 , gD,Tok,Dec . Each step may also emit at most one symbol from a fixed The objects D, Tok, and Dec parameterize the local step map finite output alphabet. No monotone protocol step may delete a g. The decoder tuple and its Transformer block equations stay block or otherwise reveal transcript content below the exposed fixed. Since V , F, and N are finite, the domain and range blocks. On input w, the global unread suffix starts as w ⊣. An of FD are finite. Hence the exact local transition gD,Tok,Dec input controller state consumes its first symbol, an internal controller state supplies ⊥, and a halting controller state admits factors through a finite set of visible contexts. no step. The run is complete exactly when it halts after Take Σ = Ω = Γ = V and choose a block bound B for consuming ⊣, as in Definition 1. For language recognition, transcript chunks. In the one-channel token-level realization, partition the halting controller states as ∆ = V , B = 1, and r = N when the current input and rej acc ˙ boundary information are already present in the exposed token χ−1 ctl (halt) = Qctl ∪ Qctl . sequence. If the input or boundary information is serialized The visibility restriction is exact: a copy source is one separately, its tokens also count toward N ; in every case of the currently exposed blocks. Addressing a fixed finite the exact requirement is | Tok(x, s)| ≤ N . For chunked set of transcript positions remains finite-state because their transcripts, Tok may use any fixed segmentation satisfying values fit in the finite consulted-state summary. Addressing the same bound. Proposition 1 packs the entire fixed portion arbitrary positions in an unbounded retained transcript creates consulted by one forward step into one finite abstract top infinitely many consultable configurations. Exact reload of symbol. This construction specifies the local transcript interdiscarded text and an unbounded writable store create the same face. The standard autoregressive protocol supplies prompt additional resource. processing, successive invocations, and end-of-sequence or For each fixed m ≥ 1, let MONm denote the class of length stopping. The wrapper uses this fixed schedule. monotone orchestration systems with exactly m agents. D. Monotone orchestration Definition 8 (Spawn). The operation Spawn creates a fresh Throughout this subsection, each RTMT agent uses the r = 1 bounded-transcript realization from Proposition 1. Because the population is finite, a disjoint-union recoding gives all agents a common finite block alphabet ∆. For H ∈ ∆∗ , let top# (H) be its final block, or # when H = ε. A monotone orchestration system consists of finitely many such agents M1 , . . . , Mm , physical transcripts H1 , . . . , Hm ∈ ∆∗ , local control states q1 , . . . , qm , and an orchestrationcontroller state qctl ∈ Qctl , where Qctl is finite. Each agent starts in its designated initial state with an empty transcript,

agent with its own local state and transcript, initialized in a fixed start configuration. If the controller may invoke Spawn unboundedly often, then the population of live agents is no longer a priori finite. Operationally, it models starting a fresh agent session with its own retained transcript. Remark 3 (Deployed transcript primitives). Table II states when common deployment patterns remain monotone. PopContext, unbounded writable memory, and unbounded Spawn are outside the monotone protocol defined here.

TABLE II D EPLOYMENT PATTERNS AND MONOTONE CONDITIONS .

Pattern CoT / ReAct scratchpad [41], [49], [4]

Ops / primitives Append

Standard RAG [13] Finite-summary compaction [37], [38] Multi-agent handoff [50], [5] KV cache / durable store [14]

Copy / insert into window Replace by finite summary Copy shared / visible messages Retain / drop cache entries

Monotone condition Each step reads a fixedsize exact context and cannot recover discarded tokens. Document store is readonly. Discarded exact text is never reloaded. Agent population stays fixed. Consulted state remains a fixed finite context; dropped exact entries are never re-exposed.

E. Orchestrated Transcript Machine Definition 9 (Orchestrated Transcript Machine with k agents). Fix k ≥ 1. Let Ai ∈ RTMT range over one-channel agents, let Σ, Ω range over finite input and output alphabets, and let Qctl range over finite orchestration-control sets. Use the r = 1 realizations of Proposition 1; after finite recoding, let ∆ be their common physical block alphabet and Qi the local control of agent i. Set QO := Qctl ×

k Y

Qi ,

∆# := ∆ ∪ {#}.

i=1

Let

call together with an orchestration-level append of the actionspecified block b ∈ ∆ to Hi ; the appended block is taken from the action, not from an agent-emitted return value. Action route(i, j) appends the exposed final block of Hi to Hj and leaves Hi and all local states unchanged; it is a no-op when Hi is empty. Action pop(i) is issued by the orchestration layer and deletes the final block of Hi when present; idle changes no agent or transcript. The initial configuration is (qO,0 , w ⊣, ε, . . . , ε). Input consumption, output, halting, and completion follow Definition 1. Thus OTMk has k one-channel agents. The class TMTk has one agent with k tagged channels. Remark 4 (Compaction, routing, and serialization). Compaction is not an extra primitive: an agent produces a summary by an ordinary step, and orchestration-level pop removes superseded blocks. Cross-agent handoff is route(i, j); a destructive move is route followed by pop(i). The model records a sequential event trace. Every deterministic parallel deployment has a deterministic serialization of its completed agent events. If several events read one pre-round state, its finite control and exposed-top tuple can be retained in Qctl while their effects are serialized. IV. T HEORETICAL R ESULTS All results in this section concern the abstract machine classes of Section III. A. Exact characterization of one agent Theorem 1 (Exact single-agent characterization). For every fixed k ≥ 1,

AO,k := {idle} ∪ {step(i) : i ∈ Ck } ∪ {push(i, b) : i ∈ Ck , b ∈ ∆}

Trans(RTMTk ) = Trans(FST).

∪ {route(i, j) : i, j ∈ Ck , i ̸= j}

Proof. Let A ∈ RTMTk have control set QA and stack alphabet Λ. The finite summary space

∪ {pop(i) : i ∈ Ck }.

S := QA × (Λ ∪ {#})k

Define OTMk as the class of instances O := (Ai )ki=1 , Qctl , Σ, Ω, ∆, χO , qO,0 , δO ,

where qO,0 ∈ QO contains the designated controller and agent initial states, χO : QO → {input, internal, halt}, Q◦O := χ−1 O ({input, internal}), and δO : Q◦O × Σ⊥ × ∆k# −→ QO × AO,k × (Ω ∪ {ε}) is a deterministic sequential orchestration map. It consults the finite global control and the exposed top of each physical transcript Hi ∈ ∆∗ . An ordinary call to agent Ai advances only that agent’s local control state under the shared input symbol selected by χO ; it does not consult or modify any other agent’s state, and the orchestration retains exclusive control of every transcript. Action step(i) is one ordinary call with no transcript change. Action push(i, b) is one ordinary

records the control state and current top of every channel. Stay preserves a top and push replaces the recorded top with the written symbol. Because pop is unavailable, no buried symbol can become visible again. Hence the next summary, status, and output depend only on S, giving an equivalent deterministic finite-state transducer. Conversely, a deterministic finite-state transducer under the same status convention is an RTMTk over any singleton stack alphabet whose action tuple is always stayk . Thus both classes realize the same completed transductions. In particular, every RTMTk recognizes exactly the regular languages and is strictly weaker than a pushdown automaton, which recognizes the nonregular language {an bn : n ≥ 1}. B. Monotone protocols stay finite-state Theorem 2 (Monotone multi-agent collapse). For every fixed m ≥ 1, Trans(MONm ) = Trans(FST).

Proof. For each agent, Proposition 1 and Theorem 1 give a finite local summary Si containing its control and encoded visible suffix. The global summary space S := Qctl ×

m Y

Si

i=1

is finite. A local transition updates one Si . A direct append or exposed-block copy updates the target’s encoded visible suffix from the source and target suffixes; no permitted operation reveals a buried symbol. Thus every protocol step induces a deterministic map on S, which is sufficient to determine an equivalent finite-state transition. Conversely, every deterministic finite-state transducer is realized by a member of MONm whose agents always stay and whose orchestration controller implements the finite-state transition. The fixed-population hypothesis is essential: after n unbounded Spawn operations the summary has n local components, so no fixed finite product S covers all configurations. Remark 5 (Nondeterministic and probabilistic protocols). Finite branching does not enlarge the summary space S. Nondeterministic existential acceptance reduces by the subset construction, while assigning positive probability to each enabled branch gives the randomized-machine construction of [24, Sec. 11.4.3]: its random tape resolves a path through the same finite summary. Thus ordinary finite-precision token sampling is a probabilistic finite-state machine on S and accepts with positive probability exactly when some corresponding nondeterministic branch accepts. Corollary 1 (Append-only CoT cycles). Under the hypotheses of Theorem 2, allowing unboundedly many append-only internal steps after a finite input is consumed yields an ultimately periodic run whenever it does not halt. Proof. By Theorem 2, the global process factors through a finite state set S. After the input is consumed, its internal transition on S is deterministic and autonomous. Hence an infinite run eventually revisits a state, after which both the states and emitted blocks repeat periodically. C. Multi-agent correspondence and stack hierarchy Theorem 3 (Agent/channel equivalence). For every fixed k ≥ 1, Trans(OTMk ) = Trans(TMTk ). Proof. Let O ∈ OTMk . Use QO as finite controller state, ∆ as channel alphabet, and transcript Hi as channel i above its bottom marker. Actions step(i) and idle become the allstay tuple, push(i, b) becomes push of b on coordinate i, and route(i, j) becomes stay when stack i is empty and otherwise push of its top symbol on coordinate j. Action pop(i) becomes pop on coordinate i; every other coordinate stays. The transition domain, consulted top tuple, status, input convention, and output are otherwise identical, yielding a stepfor-step deterministic simulation by a member of TMTk .

Conversely, let a member of TMTk have channel alphabet Λ. Take k one-state RTMT agents with common physical block alphabet ∆ := Λ whose finite input interface selects stay or push of a specified b ∈ Λ. Store the simulated control state and pending transition in Qctl . At the start of each simulated transition, δO consults the same top tuple and serializes the at most k non-stay coordinate actions in increasing channel order: push(i, b) implements push, pop(i) implements pop, and an all-stay transition needs one idle round. The first round consumes the source symbol; remaining rounds are internal ⊥-steps. Only the final round emits the pending output and completes the simulated transition. Induction over completed simulated transitions preserves the simulated state, stacks, unread input, status, and emitted output. Corollary 2 (Pop-enabled single-/multi-agent correspondence). For every fixed k ≥ 1, Trans(RTMTk + {Pc }kc=1 ) = Trans(OTMk ). Proof. By Definition 5, RTMTk + {Pc }kc=1 = TMTk . Apply Theorem 3. Corollary 3 (Classical acceptor hierarchy). Under the acceptor specialization, both RTMT1 + P and OTM1 recognize exactly the deterministic context-free languages. For every fixed k ≥ 2, both RTMTk + {Pc }kc=1 and OTMk are Turingcomplete [23], [24]. Proof. Definition 5 identifies RTMTk +{Pc }kc=1 with TMTk , and Theorem 3 identifies OTMk with the same transduction class. The simulations in its proof preserve halting status, so the identification also holds for the acceptor specializations. Lemma 1 transfers the classical Hopcroft–Ullman results to this normal form: one stack gives the deterministic contextfree languages, and two stacks simulate a Turing machine. In the standard two-stack tape encoding, one stack stores the cells left of the head with the nearest cell on top, and the other stores the current cell and the cells to its right. A head move writes the current symbol and transfers the boundary symbol between the stacks; finite control stores the Turing-machine state and handles blanks. In transcript terms, one tape cell is one block: a head move appends one block to one channel and applies Pc to the other, so the two retained transcripts hold the tape split at the head. For k > 2, the additional channels may remain unused. Thus the acceptance hierarchy has two cases: k = 1 gives DCFL, and every fixed k ≥ 2 gives RE. Two pop-enabled transcripts already reach RE; additional agents or channels preserve this language class. For fixed k, an augmentation X of RTMTk is an extension of its configuration and transition interface by specified deterministic primitives; RTMTk + X denotes the resulting machine class. Call X effective if every extended configuration has a finite description and every added one-step primitive is Turing-computable. Call it Turing-complete if RTMTk + X simulates a Turing machine. For a fixed channel count k, write X ⪯acc Y when every language accepted by RTMTk + X

is accepted by RTMTk + Y . Let RE denote the class of recursively enumerable languages. Theorem 4 (Acceptor maximality of PopContext for k ≥ 2). For every k ≥ 2, RTMTk + {Pc }kc=1 accepts exactly RE and is acceptor-equivalent to every effective Turing-complete augmentation. Consequently, all effective universal augmentations form one equivalence class under ⪯acc . Proof. By Definition 5, RTMTk + {Pc }kc=1 = TMTk . By Lemma 1, the classical two-stack construction applies to this normal form and gives Turing completeness for k ≥ 2. For the upper bound, a Turing machine encodes each finite configuration description and computes successive transitions. Thus the channelwise PopContext augmentation and every effective Turing-complete augmentation X accept exactly RE [24], [23]. Remark 6 (Intermediate classes). Theorem 4 begins its comparison at universality. Channelwise PopContext is one effective route to RE. Nonuniversal nonmonotone primitives may realize intermediate or incomparable language classes. Standard examples include one-counter languages, deterministic context-free languages, context-free languages, and recursive languages [24]. Proposition 2 (Multi-agent simulation overhead). The multiagent simulations have the following costs. 1) For fixed k, one TMTk round costs at most k steps of OTMk ; in particular, one TMT1 round costs one OTM1 step. A classical Hopcroft–Ullman pushdown transition with longest replacement word L first expands into at most L + 3 such rounds by Lemma 1. 2) One deterministic Turing-machine step costs O(1) steps of OTM2 , and OTM2 simulates OTMk with polynomial overhead. The simulations use O(t) transcript blocks for t stack operations. Proof. In the reverse simulation of Theorem 3, an all-stay TMTk round is one idle round. Otherwise, each non-stay coordinate becomes one push(i, b) or pop(i) round, so at most k rounds are needed and at most k − 1 are internal and silent. Encoding one stack symbol per block gives the first bound and the storage cost. The standard split-tape simulation then gives constant overhead per Turing step. The forward simulation in Theorem 3 maps each orchestration round to one round of a fixed member of TMTk . Simulating that transducer on a Turing machine and returning through the two-stack construction gives the polynomial bound. V. D ISCUSSION a) Finite versus unbounded consulted memory: With finite precision, bounded transcript visibility yields finite consulted state. A growing exact KV cache, writable store, suitable tool oracle, or transcript operation that re-exposes hidden blocks supplies unbounded discrete memory [14], [51],

[28]. Bounded read-only RAG supplies bounded external input [13]. In the abstract controller, PopContext re-exposes the most recently hidden block by stack pop, giving deterministic pushdown power with one pop-enabled transcript and Turing universality with two. b) Chain-of-thought and repetitive loops: Chain-ofthought expressivity [41], [49] scales with decoding steps when each step consults a growing exact transcript and logprecision arithmetic. If each step consults only a fixed finite summary, Corollary 1 applies: an infinite scratchpad run must eventually cycle. Repetitive tool-and-thought loops under a token budget exhibit the same limitation. Growing exact writable memory, unbounded agent population, and operations such as PopContext provide practical routes beyond this fixedsummary regime. c) Formal-language interpretation: Relative to Hahn [15] and Merrill et al. [17], [16], who upper-bound fixed architectures, we classify the transcript-management layer around a fixed architecture. We identify a deployed transcript operation with the pop action of our normal form, connect that form to the classical presentation through Lemma 1, and prove that the specified fixed-population monotone alternatives remain finite-state. Pushdown models connect the transcript interface to deterministic parsing [10], grammar-constrained or checkable synthesis [7], [8], and instruction languages [11], [12]. d) Context compaction: For long-session compaction [37], [38], the relevant distinction is whether hidden or discarded exact text can later be re-exposed. A finite summary remains finite-state. PopContext-style re-exposure supplies stack memory. e) Unbounded Spawn avoids finite-population collapse: Unbounded Spawn creates an unbounded collection of local states even if each agent uses fixed precision. PopContext recovers hidden memory at a fixed population. These operations add distinct state resources. VI. C ONCLUSION The fixed-population monotone collapse is the paper’s novel theoretical result. Any finite collection of agents governed by the standard local-call, append, routing, and visible-copy operations realizes exactly the finite-state transductions so cannot accurately parse any general programming language. This result applies directly to most deployments of Transformers in production systems, and it gives a formal reason why synthesis and verification pipelines supply their grammars and checkers from outside the learned component [7], [8]. The bounded-transcript correspondence represents the same management layer as our RTMTk , the pop-free case of the Transcript-Managed Transducer. Channelwise PopContextadmits the one remaining action and returns the full TMTk . One pop-enabled transcript gives the deterministic context-free languages, and two give the recursively enumerable languages. The channels may reside in one agent or in separate orchestrated agents. For k ≥ 2, every effective universal augmentation accepts the same language class, RE.

One operation extends the transcript-management vocabulary, while the Transformer, its weights, its token protocol, and the amount of retained text stay as they are. Deployed singleand multi-agent systems therefore admit a transcript-managed reading, which opens a route to strengthening existing deployments by adding pop locally in the transcript manager rather than changing the model. R EFERENCES [1] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in Advances in Neural Information Processing Systems 30, 2017. [2] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever, “Language models are unsupervised multitask learners,” OpenAI technical report, 2019. [Online]. Available: https://cdn.openai.com/better-language-models/language models are unsupervised multitask learners.pdf [3] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. HerbertVoss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei, “Language models are few-shot learners,” in Advances in Neural Information Processing Systems, vol. 33, 2020, pp. 1877– 1901. [4] S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao, “ReAct: Synergizing reasoning and acting in language models,” in International Conference on Learning Representations, 2023. [5] Q. Wu, G. Bansal, J. Zhang, Y. Wu, B. Li, E. Zhu, L. Jiang, X. Zhang, S. Zhang, J. Liu, A. H. Awadallah, R. W. White, D. Burger, and C. Wang, “AutoGen: Enabling next-gen LLM applications via multiagent conversation,” in First Conference on Language Modeling, 2024. [6] X. Hou, S. Wang, Y. Zhao, and H. Wang, “When agents do not stop: Uncovering infinite agentic loops in LLM agents,” 2026. [7] R. Alur, R. Bodik, G. Juniwal, M. M. K. Martin, M. Raghothaman, S. A. Seshia, R. Singh, A. Solar-Lezama, E. Torlak, and A. Udupa, “Syntax-guided synthesis,” in Proceedings of the 2013 Formal Methods in Computer-Aided Design, 2013, pp. 1–17. [8] N. Kobayashi, T. Sekiyama, I. Sato, and H. Unno, “Towards neuralnetwork-guided program synthesis and verification,” Formal Methods in System Design, 2025. [9] G. Delétang, A. Ruoss, J. Grau-Moya, T. Genewein, L. K. Wenliang, E. Catt, C. Cundy, M. Hutter, S. Legg, J. Veness, and P. A. Ortega, “Neural networks and the Chomsky hierarchy,” in International Conference on Learning Representations, 2023. [10] D. E. Knuth, “On the translation of languages from left to right,” Information and Control, vol. 8, no. 6, pp. 607–639, 1965. [11] T. Kuhn, “A survey and classification of controlled natural languages,” Computational Linguistics, vol. 40, no. 1, pp. 121–170, 2014. [12] A. Veizaga, M. Alférez, D. Torre, M. Sabetzadeh, and L. Briand, “On systematically building a controlled natural language for functional requirements,” Empirical Software Engineering, vol. 26, no. 5, p. 90, 2021. [13] P. Lewis, E. Perez, A. Piktus, F. Petroni, V. Karpukhin, N. Goyal, H. Küttler, M. Lewis, W. tau Yih, T. Rocktäschel, S. Riedel, and D. Kiela, “Retrieval-augmented generation for knowledge-intensive NLP tasks,” in Advances in Neural Information Processing Systems 33, 2020. [14] M. Oren, M. Hassid, N. Yarden, Y. Adi, and R. Schwartz, “Transformers are multi-state RNNs,” in Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, 2024, pp. 18 724– 18 741. [15] M. Hahn, “Theoretical limitations of self-attention in neural sequence models,” Transactions of the Association for Computational Linguistics, vol. 8, pp. 156–171, 2020. [16] W. Merrill, A. Sabharwal, and N. A. Smith, “Saturated transformers are constant-depth threshold circuits,” Transactions of the Association for Computational Linguistics, vol. 10, pp. 843–856, 2022. [17] W. Merrill and A. Sabharwal, “The parallelism tradeoff: Limitations of log-precision transformers,” Transactions of the Association for Computational Linguistics, vol. 11, pp. 531–545, 2023.

[18] R. E. Stearns, J. Hartmanis, and P. M. Lewis, II, “Hierarchies of memory limited computations,” in 6th Annual Symposium on Switching Circuit Theory and Logical Design, 1965, pp. 179–190. [19] Y. Hao, D. Angluin, and R. Frank, “Formal language recognition by hard attention transformers: Perspectives from circuit complexity,” Transactions of the Association for Computational Linguistics, vol. 10, pp. 800–810, 2022. [20] L. Strobl, W. Merrill, G. Weiss, D. Chiang, and D. Angluin, “What formal languages can transformers express? A survey,” Transactions of the Association for Computational Linguistics, vol. 12, pp. 543–561, 2024. [21] S. Bhattamishra, K. Ahuja, and N. Goyal, “On the ability and limitations of transformers to recognize formal languages,” in Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, 2020, pp. 7096–7116. [22] S. Bhattamishra, A. Patel, V. Kanade, and P. Blunsom, “Simplicity bias in transformers and their ability to learn sparse Boolean functions,” in Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2023, pp. 5767– 5791. [23] M. L. Minsky, Computation: Finite and Infinite Machines. PrenticeHall, 1967. [24] J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed. Pearson, 2007. [25] R. Alur and P. Madhusudan, “Visibly pushdown languages,” in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 202–211. [26] M. F. Atig, “Model-checking of ordered multi-pushdown automata,” Logical Methods in Computer Science, vol. 8, no. 3, pp. 1–31, 2012. [27] G. Weiss, Y. Goldberg, and E. Yahav, “Extracting automata from recurrent neural networks using queries and counterexamples,” in Proceedings of the 35th International Conference on Machine Learning, 2018. [28] J. Pérez, P. Barceló, and J. Marinkovic, “Attention is Turing-complete,” Journal of Machine Learning Research, vol. 22, no. 75, pp. 1–35, 2021. [29] E. Grefenstette, K. M. Hermann, M. Suleyman, and P. Blunsom, “Learning to transduce with unbounded memory,” in Advances in Neural Information Processing Systems 28, 2015. [30] A. Joulin and T. Mikolov, “Inferring algorithmic patterns with stackaugmented recurrent nets,” in Advances in Neural Information Processing Systems 28, 2015. [31] B. DuSell and D. Chiang, “Learning context-free languages with nondeterministic stack RNNs,” in Proceedings of the 24th Conference on Computational Natural Language Learning, 2020, pp. 507–519. [32] S. Chung and H. T. Siegelmann, “Turing completeness of boundedprecision recurrent neural networks,” in Advances in Neural Information Processing Systems 34, 2021, pp. 28 431–28 441. [33] B. DuSell and D. Chiang, “Stack attention: Improving the ability of transformers to model hierarchical patterns,” in International Conference on Learning Representations, 2024. [34] S. Murty, P. Sharma, J. Andreas, and C. D. Manning, “Pushdown layers: Encoding recursive structure in transformer language models,” in Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 2023, pp. 3233–3247. [35] K. Zhang, G. Li, J. Li, H. Zhang, Y. Dong, J. Li, J. Xu, and Z. Jin, “Recursive transformer: Boosting reasoning ability with state stack,” in Advances in Neural Information Processing Systems 38, 2025. [36] Z. Dai, Z. Yang, Y. Yang, J. Carbonell, Q. V. Le, and R. Salakhutdinov, “Transformer-XL: Attentive language models beyond a fixed-length context,” in Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, 2019, pp. 2978–2988. [37] J. W. Rae, A. Potapenko, S. M. Jayakumar, C. Hillier, and T. P. Lillicrap, “Compressive transformers for long-range sequence modelling,” in International Conference on Learning Representations, 2020. [38] Y. Dai, J. Lian, Y. Huang, W. Zhang, M. Zhou, M. Wu, X. Xie, and H. Liao, “Pretraining context compressor for large language models with embedding-based memory,” in Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2025, pp. 28 715–28 732. [39] S. Bhattamishra, A. Patel, and N. Goyal, “On the computational power of transformers and its implications in sequence modeling,” in Proceedings of the 24th Conference on Computational Natural Language Learning (CoNLL), 2020, pp. 455–475.

[40] M. Dehghani, S. Gouws, O. Vinyals, J. Uszkoreit, and Ł. Kaiser, “Universal transformers,” 2018, arXiv:1807.03819. [Online]. Available: https://arxiv.org/abs/1807.03819 [41] W. Merrill and A. Sabharwal, “The expressive power of transformers with chain of thought,” in International Conference on Learning Representations, 2024. [42] Q. Li and Y. Wang, “Efficient Turing machine simulation with Transformers,” in International Conference on Learning Representations, 2026. [43] J. W. Rae and A. Razavi, “Do transformers need deep long-range memory?” in Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 2020, pp. 7524–7529. [44] O. Press, N. A. Smith, and M. Lewis, “Train short, test long: Attention with linear biases enables input length extrapolation,” in International Conference on Learning Representations, 2022. [45] A. Kazemnejad, I. Padhi, K. N. Ramamurthy, P. Das, and S. Reddy, “The impact of positional encoding on length generalization in transformers,” in Advances in Neural Information Processing Systems, vol. 36, 2023. [46] J. Su, M. Ahmed, Y. Lu, S. Pan, W. Bo, and Y. Liu, “RoFormer: Enhanced transformer with rotary position embedding,” Neurocomputing, vol. 568, p. 127063, 2024. [47] M. Xu, X. Men, B. Wang, Q. Zhang, H. Lin, Y. Lu, X. Han, and W. Chen, “Base of RoPE bounds context length,” in Advances in Neural Information Processing Systems, vol. 37, 2024. [48] F. Liu, “Rotary positional embeddings as phase modulation: Theoretical bounds on the RoPE base for long-context transformers,” 2026. [Online]. Available: https://arxiv.org/abs/2602.10959 [49] G. Feng, B. Zhang, Y. Gu, H. Ye, D. He, and L. Wang, “Towards revealing the mystery behind chain of thought: A theoretical perspective,” in Advances in Neural Information Processing Systems, vol. 36, 2023. [50] M. Rizvi-Martel, S. Bhattamishra, N. Rathi, G. Rabusseau, and M. Hahn, “Benefits and limitations of communication in multi-agent reasoning,” 2025. [Online]. Available: https://arxiv.org/abs/2510.13903 [51] U. Tiwari, S. S. Nalli, and A. Deshpande, “Modeling tool use in transformers via computation oracles,” in Latent and Implicit Thinking Workshop at ICLR, 2026.