Nondeterministic Recursive Padding and Time Separation

A display consists only of the state and the $k$ scanned symbols, not whole tape configurations. Guess on tape two a sequence $D_0,A_0,D_1,A_1,\dots ,A_{t-1},D_t$ of displays and chosen instructions, ending with a delimiter. Each display and instruction is one letter from a finite alphabet depending on M. While guessing, check that $D_0$ has the initial state, each $A_j$ is allowed for the state and scanned symbols in $D_j$, its target state is that of $D_{j+1}$, and only the last display has an accepting state. Reject premature halting states. A branch may guess forever, which is permitted for an acceptor; finite guesses cost $O_M(t+1)$.

Rewind tape two. Use tape one, still containing the original input, as the first simulated tape. For each $j$, compare its actual scanned symbol with the first-tape component of $D_j$, rejecting a mismatch, then perform on tape one the write and move specified by $A_j$. Advance tape two to the next display. At $D_t$ also check the final scanned symbol. During this pass both heads move only constantly many times per record; tape one's head physically follows the simulated head, so a left move at zero is automatically clamped. Input symbols never visited retain their input values.

Before the next virtual-tape pass, erase tape one and return its head to zero. This can be done in $O_M(\mathrm{\mid }x\mathrm{\mid }+t+1)$ time: initially scan the input and mark an extra right delimiter beyond its extent; maintain a track marking the furthest initialized or visited cell, moving the frontier mark one cell when a replay first reaches it. The replayed tape symbols occupy a separate track, so the delimiter/zero marks do not alter comparisons. A sweep from zero through this frontier erases the tape, and a reverse sweep returns to zero. It lies within $\max (\mathrm{\mid }x\mathrm{\mid },t)+1$. Rewind the display tape, whose length is $O_M(t+1)$, and replay the second virtual tape starting blank. Repeat for each remaining tape, always comparing its own component of every display and executing that component of each action. There are exactly k passes.

On an accepting verification, each tape's replay proves by induction on j that its displayed scanned symbols agree with the tape contents obtained from the input and the preceding actions. The state checks and instruction checks were already made while guessing. Hence all components together satisfy M's full transition table at every step and the last state accepts. Conversely the displays/actions of any accepting t-step computation pass all these tests. This proves language equality and the stated soundness for every accepting branch, even if other guesses diverge or reject.

The initial input scan, guessing, k replay passes, k erasures and rewinds together take at most $c_M(\mathrm{\mid }x\mathrm{\mid }+t+1)$ transitions for one fixed $c_M$. Use a shortest accepting computation and absorb the additive constant into d. Empty input only requires its marked blank zero cell, and t=0 could be checked by the same display procedure, though the fixed distinct initial/accepting states forbid an actual zero-step accepting run. All choices are finite instruction guesses; no AC is used.

Adapt the finite table in F1 as follows. A payload d lists the state/alphabet sizes, and for each nonhalting state and pair of scanned symbols a finite list of target states, two written symbols and two L/R bits, in fixed lexicographic order without duplicates. Use the same unary-length-prefixed canonical numeral blocks and tuple-arity header. A deterministic fixed multitape decoder D parses d and checks all bounds, lengths and ordering, accepting exactly canonical valid tables. It halts on every d: all loops inspect finite parsed lists or finite integers from them. The same unique-decoding argument as F2 applies to these longer rows. Let $r(d)\ge 1$ be D's exact number of transitions on d. It is a total recursive function, obtained by running D and counting.

Define $e(d)=1^{\mathrm{\mid }d\mathrm{\mid }}0d{1}^{r(d)}0$ for valid payloads. The first field uniquely ends at d's last bit, and the first zero thereafter uniquely ends the padding. Thus no valid code is a proper prefix of another, and distinct payloads give distinct codes. To validate a word, first recover d and prepare a copy on D's input tapes, costing $O(\mathrm{\mid }d\mathrm{\mid }+1)$. Then run one step of D while advancing a separate head by one padding symbol. Reject an early zero or blank before D halts, and after its r(d) steps require the next symbol to be the padding's terminal zero and no trailing input. Reject also if D rejects d. A too-short malformed word is rejected as soon as the available padding expires; the validator never completes an arbitrarily long D run after input exhaustion. This gives $O(\mathrm{\mid }e\mathrm{\mid }+1)$ time on all words, not only on valid codes.

For universal recognition use the same parsing but regard everything after the terminal zero as data x. If parsing fails, reject. A fixed multitape interpreter stores the decoded table on one tape, the two simulated tapes in binary symbol blocks on two tapes, and the state and temporary fields on a fixed number of scratch tapes. For each fixed e, symbol blocks have a fixed width depending on e; translating the input into such blocks costs $O_e(\mathrm{\mid }x\mathrm{\mid }+1)$. At each step the interpreter reads the two current blocks, scans the stored finite table to find precisely the listed instruction options, guesses one, updates the two blocks and state, and moves the simulated heads to adjacent blocks. Boundary flags on block zero implement the clamped move. Scratch heads return to their bounded working zones after each step. Program and field scans cost a constant depending on e, never on x or the number of simulated steps.

Every interpreter branch therefore corresponds to an actual instruction sequence, and accepts exactly at a simulated accepting state. Every accepting t-step run of $M_e$ yields a branch taking at most $a_e(\mathrm{\mid }x\mathrm{\mid }+t+1)$ interpreter steps, including code parsing; the fixed parsing cost is absorbed into $a_e$. Infinite computations need not halt. Apply F3 once to this one fixed interpreter, not separately to each code, obtaining one two-tape U. Its constant simulation factor and the input length $\mathrm{\mid }e\mathrm{\mid }+\mathrm{\mid }x\mathrm{\mid }$ yield constants $c_e,d_e$ with the asserted bound. Empty data x is allowed; an invalid or incomplete prefix gives no accepting branch. No decoding-time bound for the unpadded legacy syntax was assumed.

Define an explicit compiler f on valid two-tape codes d. Its output describes a machine which, on x on tape one and blank tape two, writes literal d on tape two, returns that head to zero, then executes the table described by d from its start state, with that nonblank second tape. The extra states are finite literal-writing and return chains. Tape one is preserved; a stay can be replaced by a right/left excursion, including at zero. Finally encode the whole finite table with F1's code scheme. This is effective specialization in the sense of F2, here implemented directly in the target syntax rather than through a semantic recognizer. Code-padding computation is allowed to be slow: f is only required to halt.

Construct a two-tape program Q which expects x on tape one and a valid d on tape two. It first computes $e=f(d)$ and $h(e)$, both terminating. It then arranges $h(e)x$ on tape one with all other tracks blank and runs the fixed interpreter of F1. These operations are effective two-tape algorithms: finite computation on d can use scratch tracks on the two tapes while preserving an input track for x; after computing the finite prefix, shift x right by its length with a reverse scan, write the prefix, and erase scratch tracks. Any temporary stay is replaced by the same two-move macro. Let q be the code of this finite Q table and put $e_0=f(q)$. Both q and $e_0$ are obtained by finite code generation.

On ordinary input x, $M_{e_0}$ first writes q on tape two and then runs Q. Q consequently computes $f(q)=e_0$ and then $h(e_0)$, and interprets precisely $H_{e_0}$ on x. The compiler calculations terminate independently of whether that acceptor has a branch which halts. F1 gives language equality in both directions, including when the language is empty. This proves the desired fixed point directly; F3's extensional theorem alone would not provide the quantitative assertion below.

All computation on q, $f(q)$ and $h(f(q))$ now concerns fixed finite strings, so takes a fixed number of steps and uses a fixed finite amount of scratch space, independent of x. Preserving and shifting x for the final fixed prefix costs at most $A(\mathrm{\mid }x\mathrm{\mid }+1)$ for a fixed A. F1 bounds the interpreter run by $B(\mathrm{\mid }x\mathrm{\mid }+{\tau }_{H_{e_0}}(x))+E$, where B and E depend only on the fixed target code $h(e_0)$. Add these costs to obtain C,D as stated. No deterministic dovetailing of branches occurs, so no exponential search has been concealed in C.

For the final specialization let $H_e$ be the finite program which prepends literal e to its input and directly runs A. This compiler is total and its per-e preprocessing is $O_e(\mathrm{\mid }x\mathrm{\mid }+1)$ on semi-infinite tapes; hence ${\tau }_{H_e}(x)\le A_e(\mathrm{\mid }x\mathrm{\mid }+1)+{\tau }_A(ex)$. Insert this estimate in step 4.1. Empty x still permits the literal-prefix writing; zero accepting time is neither needed nor manufactured. All parameters and constants are fixed by explicit compilation, with no AC.

For union, make an initial nondeterministic choice between two tagged branches. Copy the input to the selected machine's disjoint tapes and run it, accepting only on its acceptance. Thus a resulting accepting branch supplies acceptance by A or B, and each such acceptance supplies a branch of the union machine. Copy and setup cost at most $c(n+1)$; use the faster accepting alternative to obtain the displayed minimum bound, interpreting the other alternative as infinity when necessary. A divergent unselected computation has no effect.

For intersection, prepare two input copies on disjoint tape sets. Simulate A, and only after an accepting branch of A continue with B on its untouched copy; accept only when B also accepts. A successful branch therefore witnesses both memberships. Conversely concatenate any two finite accepting instruction sequences, using the two independent copies. Their combined length plus copying cost is bounded by $c(n+{\tau }_A(x)+{\tau }_B(x)+1)$ for a fixed c. If either machine has no accepting branch, no combined branch accepts.

For a cutoff, simulate A and its exact clock in rounds on disjoint tapes, testing A's acceptance no later than the inclusive last round. Every branch rejects at expiry unless already accepted. This recognizes precisely $L_T(A)$ and halts on every branch within $O_A(n+T(n)+1)$. For a fixed integer factor in the desired cutoff, use that many sequential clock runs as in F1. Finite unions/intersections of such clocked machines also halt on every branch, since there are finitely many sequential calls each with a bound; the corresponding min/sum estimates for acceptance remain valid.

Apply F2 to any of the fixed acceptors above if two tapes are required, multiplying the bounds by a fixed constant and adding $O(n+1)$. This does not by itself claim that the normalized machine halts on every branch; its guessing phase may diverge. When an all-branch result is required, use the direct clocked multitape construction from step 1.3, or separately supply and run an adequate clock after normalization. Empty inputs cost a constant; if both union languages are empty or one intersection language is empty, the construction correctly has no accepting branch. No choice beyond two finite alternatives is used.

Enumerate all finite-tape nondeterministic machines, without a time claim for the enumeration. To be explicit, prepend a positive tape count $k$ to a finite numeric table: state/alphabet sizes and a list of allowed instructions for each state and $k$-symbol tuple, each instruction giving a state, $k$ written symbols and $k$ direction bits. This elementary enumeration needs no universal-simulation theorem. Encode each natural $a$ by the self-delimiting word $1^{\mathrm{\mid }\mathrm{bin}(a)\mathrm{\mid }}0\mathrm{bin}(a)$, where $\mathrm{bin}(a)$ is its ordinary binary notation (use $0$ for zero). Prepend the number of table entries, then encode each entry's number of fields and its fields by these words. Decoding is total on finite input strings: read the unary length up to the first zero and then exactly that many bits; if either segment ends early, or trailing bits remain after the advertised entries, declare the code invalid. Once $k$ and the finite state and alphabet sizes are recovered, check the source-tuple list, each instruction's fixed arity, and all finite state/symbol/direction bounds. Invalid strings denote a fixed rejecting machine. Enumerate all binary strings by length and lexicographic order. Every actual finite table has a valid encoding and hence occurs at some index $e$. Enumerate triples $(e,c,j)$ with $c\ge 1,j\ge 0$ by increasing $e+c+j$, lexicographically within each finite diagonal. Assign the $n$th triple to length $n$. Each pair $(e,c)$ consequently appears at infinitely many, hence unbounded, lengths.

On input $1^n$, find its assigned $(e,c,j)$, compute b(n), and exhaust the finite computation tree of $M_e$ on $1^n$ through depth $cb(n)$. This is a terminating deterministic calculation: at each node the table has finitely many options, and the depth is a computed natural number. Decide membership in R by the opposite of whether any accepting node occurs by that depth. Reject nonunary words if a binary decider is desired. This makes R recursive with no claimed efficient bound. At b(n)=0 inspect just the initial node, so the construction still terminates.

Suppose some $M_e$ recognizes R with shortest-time bound $Cb(n)$ at all accepted lengths $n\ge N$. Choose an integer $c\ge \max (1,C)$ and an assigned length $n\ge N$ for the pair $(e,c)$, possible by step 1.1. If the bounded tree contains acceptance, the construction declares $1^n\mathrm{\notin }R$ although $M_e$ accepts it. If it contains no acceptance, it declares $1^n\in R$, so the supposed recognition and time bound give an accepting branch of length at most $Cb(n)\le cb(n)$, again contrary to the tree result. Both alternatives contradict the assumption.

Therefore R has the claimed property. Repeating each pair at unbounded lengths, rather than merely enlarging c, handles finite exceptions even when b vanishes there. The enumeration, bounded tree search and selecting the first assigned length above N are effective finite or natural-number constructions and require no AC. No two-tape time normalization was used, so the result remains valid for sublinear or zero b.

Define $L=L_T(U)$. The direct clocked construction in F1 halts on every branch and accepts exactly this cutoff. Since T is positive and $T(n)\ge n$, its time is $O(T(n))$, so $L\in \mathrm{N}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(T)$. L depends only on U and T. Fix any candidate a as in the statement and suppose an all-branch machine B recognizes L in $O(a)$. Let V be the union acceptor for B and U from F5. Because $L\subseteq L(U)$, it recognizes exactly $L(U)$. For a sufficiently large fixed integer K, whenever $z\in L$ its shortest V-time is at most $A(\mathrm{\mid }z\mathrm{\mid })$, where $A(n)=K(a(n)+n+1)$. Enlarge K to cover all finitely many accepted short strings: A is positive there. Thus $A(n)\ge n+1$ and $A(n+1)=o(T(n))$, since $a(n+1)\ge n+1$.

Fix for now an arbitrary recursive unary language R and a deterministic decider D for it. Let r(m) be D's finite running time on $1^m$. Construct a multitape acceptor H as follows. Parse its input uniquely as $e{1}^m{0}^k$ with valid prefix e; after e, take the maximal initial run of ones and then require only zeros. Reject malformed strings. Simulate D on $1^m$ for at most k steps, counting this budget by a unary copy of the zero suffix. If D halts by that instant, accept or reject according to D. Otherwise, nondeterministically extend the zero suffix to some $k^{\mathrm{\prime }}>k$ and run V on $e{1}^m{0}^{k^{\mathrm{\prime }}}$, accepting just when V does. A branch may extend forever. Parsing, bounded simulation and copying cost $O_H(m+k+\mathrm{\mid }e\mathrm{\mid }+1)$; in the recursive case preparation costs $O_H(m+k^{\mathrm{\prime }}+\mathrm{\mid }e\mathrm{\mid }+1)$ before the direct V run. No computation of the possibly enormous r(m) is needed before the bounded test.

Apply F2 to H and F4 to its resulting two-tape acceptor. Obtain a fixed code $e_0$ and acceptor P=$M_{e_0}$ with $L(P)=\{w:e_{0}w\in L(H)\}$. Put $\mathrm{\ell }=\mathrm{\mid }{e}_0\mathrm{\mid }$, $w_k=1^m{0}^k$, $z_k=e_0{w}_k$, and $N_k=\mathrm{\ell }+m+k$. Combining the two fixed linear overheads with step 1.2 gives an integer $d\ge 1$, independent of m,k,k', such that on accepted instances: $k\ge r(m)⟹{\tau }_P(w_k)\le d(N_k+1),$ $k<r(m),k^{\mathrm{\prime }}>k,z_{k^{\mathrm{\prime }}}\in L(V)⟹{\tau }_P(w_k)\le d(N_{k^{\mathrm{\prime }}}+1+{\tau }_V(z_{k^{\mathrm{\prime }}}))\mathrm{.}$ The second inequality uses the branch which chooses that particular k'. Additive compiler constants and the input-copy terms are absorbed using $N_{k^{\mathrm{\prime }}}+1\ge 1$. By F3 choose $\kappa \ge 1$ with ${\tau }_U(z_k)\le \kappa (N_k+{\tau }_P(w_k)+1)$ whenever P accepts. These constants are fixed after R,D,V and $e_0$ are fixed, before any length induction.

First prove the language identity $w_k\in L(P)$ iff $1^m\in R$ for every m,k. For every $k\ge r(m)$, H's bounded D-test finishes and gives exactly R's answer. Now descend through $k=r(m)-1,\dots ,0$, assuming the identity for all larger k'. The compiler identity and H's recursive branch give $w_k\in L(P)$ iff some $z_{k^{\mathrm{\prime }}}\in L(V)$ with $k^{\mathrm{\prime }}>k$. Since $L(V)=L(U)$ and e0 is valid, this is equivalent to some $w_{k^{\mathrm{\prime }}}\in L(P)$. The induction hypothesis makes it equivalent to $1^m\in R$: if R answers yes, take $k^{\mathrm{\prime }}=r(m)$; if no, no larger k' works. This is a finite downward induction below a base range, not an inference from an ungrounded recursive call.

For $k<r(m)$ take $k^{\mathrm{\prime }}=k+1$ in the second estimate of step 2.1, which applies whenever $z_{k+1}\in L(V)$: ${\tau }_P(w_k)\le d(N_k+2+{\tau }_V(z_{k+1}))$. If also ${\tau }_V(z_{k+1})\le A(N_k+1)$, then ${\tau }_P(w_k)\le d(N_k+2+A(N_k+1))$, the step-down estimate used in the second induction below; since $A(N_k+1)\ge N_k+2$ by step 1.1 it is in particular at most $2dA(N_k+1)$.

Set $B_0=\kappa (d+2)$ and choose $N_0\ge 1$ such that $2B_{0}A(N+1)\le T(N)$ for all $N\ge N_0$, possible by F7. Fix a yes input $1^m\in R$ with $\mathrm{\ell }+m\ge N_0$. We prove by a second downward induction on k, starting from the entire range $k\ge r(m)$, that $\kappa (N_k+{\tau }_P(w_k)+1)\le T(N_k)$ and ${\tau }_V(z_k)\le A(N_k)$. In the base range the first expression is at most $B_0(N_k+1)\le 2B_{0}A(N_k+1)\le T(N_k)$. Therefore U accepts $z_k$ within its exact T-cutoff, so $z_k\in L$ and the bound for V follows from step 1.1.

Filter P's inputs to unary words by a complete scan costing $O(m+1)$, rejecting nonunary words. For a fixed threshold $m_0$ covering the preceding finite exceptions, a literal finite trie can decide all unary strings $1^m$ with $m<m_0$ by D's computed answers; on longer inputs run the filtered P. Step 3.1 proves exact recognition of R for all lengths. Now define the single positive recursive function $b(m)=m+1+{\sum }_{j=0}^{2m}T(j)$. It is recursive because running the fixed exact clock on each finite length computes T. For $m\ge \mathrm{\ell }$, $T(m+\mathrm{\ell })\le b(m)$, without any monotonicity hypothesis. Therefore this acceptor of R has shortest acceptance $O_R(b(m))$; the finite trie costs and finitely many exceptional values are absorbed since b is everywhere positive. Crucially b depends only on T, not on the arbitrary recursive unary language R. This contradicts F6.

Hence no such B exists for the fixed candidate a. Because step 1.1 chose the same cutoff L before a, this excludes the union over all the stated recursive lower bounds, not merely one separately chosen lower bound. If there are no such a, the exclusion is vacuous and the same clocked L still supplies membership. All searches, branch guesses and code constructions are finite or computable; thresholds are fixed natural witnesses to little-o and do not invoke AC. The all-branch claim is exactly the clocked membership proved in step 1.1.