Three computational presentations

A strict real-time multitape machine consumes one input symbol and makes one global transition. Cutting each work tape at its head turns the cells on its two sides into a pair of stacks; the scanned symbol stays in finite control. A scaffolding automaton stores the new persistent stack roots in one appended node.

Independent stacks are enough to simulate moving tape heads. A branching computation asks for more: two new slots may need to share one old stack tail and then push different heads. The results below isolate the failed operation, repair the coordinates, and state exactly which stronger source machine the repair compiles.

FPRD-T89 · strict real-time compiler

Moving tapes become persistent zipper stacks

A work tape is represented as $(L,c,R)$ : the finite stacks to the left and right of the head, and the currently scanned symbol. Writing and moving left or right changes each stack by at most one push, keep, or pop action. The scanned symbols of all tapes fit in finite control.

For a finite deterministic strict real-time $m$ -tape machine, the compiler uses $2m$ stack ports and observation distance two. One appended node records all new roots after each arriving symbol. After every prefix, decoding the two roots and the scanned symbol reconstructs each source tape at every integer offset from its head.

L(A_M)=L(M), \qquad \deg(A_M)=2m, \qquad \operatorname{dist}(A_M)=2.

The proof also needs a clean-empty invariant: when a label component ends a stack, following its same-stack port must not resurrect an older symbol. The formalization identified and proved this invariant rather than silently assuming it.

FPRD-T88 · failed clone operation

Changing one port does not change the historical coordinate

In the original decoder, stack j is read by taking label component j and following port j at every older node. It is tempting to clone source stack 0 into destination 1 by putting source component 0 in the new destination component and redirecting destination port 1 along source port 0. The first symbol comes from the source, but the decoder then resumes with component and port 1.

For a compiler-shaped backward history with

S_0=[2,1], \qquad S_1=[9],

the naive redirection produces

S'_0=[2,1], \qquad S'_1=[2,9]\ne[2,1].

The scaffold remains backward and uses no SELF target, so the failure is genuinely coordinate-based. This counterexample rejects one operation in one decoder; it does not reject persistent root sharing in scaffolding automata.

FPRD-T100 · coordinate repair

Let each cell carry the coordinate used next

The repaired cell stores a pair $(a,i)\in A\times[s]$ . At a handle $(v,j)$ , the current coordinate j selects the port leaving v; the coordinate i stored in that cell selects the label component at the next node. The decoder can therefore switch coordinate once and retain that choice throughout the shared tail.

Let every output slot independently choose a source slot and one of three operations: push a symbol, keep the stack, or pop its top. One appended node realizes all choices simultaneously. Generated targets are missing or self-free paths of length at most two, and backwardness and clean missing edges are preserved.

\operatorname{decode}(S',j) =\operatorname{derive}_j \bigl(\operatorname{decode}(S,\operatorname{source}(j))\bigr).

In the same two-stack calibration, two outputs select source 0 and push distinct heads. The result is now the intended shared-tail pair

S'_0=[7,2,1], \qquad S'_1=[8,2,1].

FPRD-T101 · source-selecting compiler

A fixed-slot machine may select and update any old root

A source-selecting stack machine has finitely many fixed slots. In each letter-synchronous round it reads every stack top and the arriving symbol, updates finite control, and assigns each output slot a push, keep, or pop applied to any source slot from the preceding round. Several outputs may select one source.

The coordinate-carrying construction compiles every finite deterministic machine of this kind to a degree-s, distance-two Loff–Moreira–Reis scaffold. One node is appended per input symbol; control, all stacks, acceptance, and the empty-word answer are preserved exactly.

\forall w\in\Sigma^*:\quad \operatorname{decode}(A_M(w),j)=M(w).\operatorname{stack}_j, \qquad A_M(w)\text{ accepts}\iff M(w)\text{ accepts}.

The compiler begins with a source-selecting machine. It does not derive a stationary slot assignment from a bounded pushdown frontier; equality-sensitive deduplication, eviction, and successor placement remain separate obligations.

FPRD-T102 · exact allocator interface

What a pushdown frontier must supply

Forgetting whether a visible machine took a call, return, or local action turns one observed prefix into a finite set of possible controls and stacks. Failed partial commands contribute nothing; duplicate derivations and list order have no semantic meaning. A stationary allocator represents this successful frontier in a fixed number of source-selecting stack slots.

The allocator must satisfy five laws: valid initialization, valid one-letter updates, exact initial representation, exact successor representation, and exact accepting-control readout. These are one set of laws for one fixed transition table—not a new choice of slot assignment for every word.

Any allocator satisfying those laws compiles through $\text{FPRD-T101}$ to a scaffold whose answer equals existential successful hidden-action execution after the same prefix, including the empty word.

This theorem identifies the interface exactly. It does not infer an allocator from a bound on the number of frontier elements.

FPRD-T103 · semantic normalization

Rejecting sinks should not occupy live frontier slots

Total visible machines often send a failed command into an absorbing rejecting sink. That convention preserves the accepted language, but keeping every sink configuration in the frontier can retain irrelevant stacks forever. If the sink is nonaccepting and cannot be left, every command entering it may instead be discarded in that same input round.

\operatorname{ProjectAccepts}(V,w) \iff \operatorname{Accepts}(\operatorname{prune}(V),w).

The equality includes epsilon and even the case in which the initial control is the sink. It removes a presentation artifact; it still does not create an allocator for the pruned frontier.

FPRD-T104 · first canonical allocator tier

When control itself is a persistent address

Call a frontier control-functional when, after every observed prefix, a fixed visible control carries at most one concrete stack. The control can then serve as its stack's slot. The allocator keeps an active-control mask and, for each target control, selects one successful push, pop, or keep candidate.

Why is arbitrary selection safe? Every candidate for target q is in the frontier at the same extended prefix. Control functionality says all of their stacks are equal. The allocator therefore needs no online comparison of unbounded stacks: any candidate has the unique correct value.

(q,z_1),(q,z_2)\in\mathsf{Frontier}(w) \quad\Longrightarrow\quad z_1=z_2.

This is stronger than bounded frontier width. It succeeds because it provides canonical coordinates, not merely a cardinality bound.

FPRD-T105 and FPRD-T106 · finite causal refinements

Split histories before allocating them

A frontier may carry two different stacks at one original control. A finite refinement can give those histories different refined controls while preserving the same input letter, hidden action, complete stack, and accepting answer. If the refined frontier is control-functional, its refined controls become canonical slots and the resulting scaffold still decides the original language.

FPRD-T106 removes a purely syntactic obstacle: named finite controls can be transported through a supplied equivalence to $\operatorname{Fin}(s)$ without changing frontier semantics. Refinements compose, so reindexing does not need a second compiler.

The substantive condition is the existence of a finite causal refinement. Merely knowing that every individual frontier is small does not construct such a history coloring.

FPRD-T107 and FPRD-T108 · bounded causal memory

Sometimes a short action history supplies the colors

The first canonical refinement remembers which hidden action most recently succeeded: call, return, or local. If histories reaching the same target control with the same last action always carry the same stack, this four-way memory—none at epsilon, then one of three actions—is control-functional.

More generally, fix $k\ge 0$ and retain the newest at most k hidden actions. If that window separates the stacks at every observed word and target control, pairing it with the control gives a finite refinement and hence a stationary scaffold. One theorem covers every fixed k, including zero and the empty word.

A depth-two calibration shows that this hierarchy is genuine: two histories can have the same last local action while their preceding call-versus-local action separates their different stacks.

FPRD-T109 · failure of every fixed window

No fixed action suffix is a universal coordinate system

Consider a one-letter, one-control machine in which call pushes 7, local keeps the stack, return fails, and the sole control accepts. Its projected language is the universal unary language. For every fixed k, compare two traces of length k+1:

call once, then take k local actions;
take k+1 local actions.

The retained depth-k windows are identical because the differing first action has fallen out of view. Their stacks are nevertheless $[7]$ and $[]$ . Thus no fixed action window separates this machine's traced frontier.

This is a representation counterexample, not a language lower bound. The language is regular, so another coordinate system is plainly possible. What fails is the proposal that a fixed suffix of hidden actions is always the right persistent address.

FPRD-D34 · semantic contract

The PEG target is finite, total, ordinary, and complete-match

The transfer theorem does not use a permissive parser or an implementation-specific acceptance convention. Its target has a finite alphabet, finitely many nonterminals transported to $\operatorname{Fin}(n)$ , and ordinary parsing expressions with sequence, ordered choice, negative lookahead, terminals, failure, and epsilon.

Evaluation is relational and total. A word is recognized only when the start expression succeeds with exactly the empty suffix:

w\in L(G) \quad\Longleftrightarrow\quad G\vdash \operatorname{start},w\Downarrow \varepsilon.

The rank-scheduled table evaluator is checked against this independent semantics. It supplies executable evidence, but does not redefine PEG membership by a fuel bound or a parser timeout.

FPRD-T110 · full sufficient direction

Every finite distance-bounded scaffold has a PEG for its reverse language

Let $A$ be a finite Loff–Moreira–Reis scaffolding automaton satisfying the published distance constraint. The generated grammar records finite control, scaffold labels, bounded paths, exact neighbourhood observations, and acceptance. The mechanized theorem is

L(A)^R\in\mathsf{PEG}.

SELF is included. A SELF edge may point to the node being created, so the proof uses a non-forward invariant rather than strict backwardness. Its path induction allows the same input position while the bounded path rank decreases. Nested SELF cases are part of the checked invariant, not a self-free corollary added later.

The construction proves totality, complete consumption, the state, label, path, and neighbourhood invariants, empty-input behavior, reversal, and transport to a literal finite nonterminal carrier. It formalizes the sufficient scaffold-to-PEG direction; it does not formalize the converse.

FPRD-T111 · compiler composition

The same theorem consumes both FPRD compiler interfaces unchanged

Composing FPRD-T110 with the strict real-time compiler gives the checked inclusion

\operatorname{rev}(\mathsf{RT\text{-}MTTM}) \subseteq \mathsf{PEG}.

Composing it with the source-selecting stack compiler gives the analogous reverse-language PEG theorem for every finite letter-synchronous fixed-slot source-selecting machine. Neither source model gains an extra endmarker step, epsilon move, delayed work phase, or stronger root-sharing operation.

The mechanization also proves conditional even-palindrome wrappers: an exact source recognizer implies PEG membership. It does not machine-check the separate classical palindrome recognizer. That is why the wholly mechanized compositions and the mixed-assurance proper-containment claim remain distinct records.

FPRD-T90 · recognition-class consequence

The transferred strict real-time class is a proper part of PEG

The machine-to-scaffold compiler and the sufficient direction of the Loff–Moreira–Reis scaffold theorem give

\operatorname{rev}(\mathsf{RT\text{-}MTTM}) \subseteq \mathsf{PEG}.

Strictness uses their final online lower-bound witness W, not an intermediate scaffold language. Every strict real-time machine is an $\operatorname{Online}(O(1))$ machine when the stronger model's length tape is left unused. Their theorem excludes both W and its reversal from every $\operatorname{Online}(t(n))$ with $t(n)=o(n/(\log n)^2)$ , so the witness cannot lie in the reversed strict-real-time class:

\operatorname{rev}(\mathsf{RT\text{-}MTTM}) \subsetneq \mathsf{PEG}.

Combining the inclusion with the classical strict real-time palindrome recognizer and its ordinary single-head multitape implementation gives the concrete corollary

\mathsf{EPAL}_2 =\{ww^R:w\in\{0,1\}^*\} \in\mathsf{PEG}.

This last chain remains a source-verified informal proof because the classical recognizer, its ordinary-machine realization, and the properness premise are not re-mechanized in the Lab's Lean development. The compiler composition itself is mechanized.

Where the allocator question now stands

Persistent root sharing answers a representation question: once a finite controller names the source of every next stack, a stationary distance-two scaffold can realize all updates exactly. The allocator results now add genuine positive tiers: control-functional frontiers, finite control refinements, and every sufficient fixed action window.

The remaining problem is narrower and sharper. Some machines escape every fixed action window, yet that failure alone says nothing about their language complexity. The next question is whether another stationary coordinate doctrine can represent those frontiers, or whether a doctrine-independent obstruction can be proved.

Persistent stacks, shared roots, and language transfer