Nondeterministic recursive-padding separation

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.