Effective Numberings, Reductions, Resources, and Randomness

Fix the input syntax first. A model tag distinguishes the published one-tape code from its following multitape extension. For the latter, encode the tape count $k\ge 1$, states $0,\dots ,m-1$ with start/accept/reject $0,1,2$, alphabet $0,\dots ,r-1$ with blank0, and input alphabet $1,\dots ,s$, where $m\ge 3$ and $0\le s<r$. List the transition entries in lexicographic order of $(q,a_1,\dots ,a_k)$ for nonhalting $q$. Each entry records one next state, $k$ written symbols and $k$ directions. Apply the tuple blocks from F2 to these canonical numerals. A tagged old code is the case $k=1$ with its original interpretation. The tag changes its length by a constant. For either tagged form, define the initial multitape configuration to have state0 and every head at cell0, with $x$ in cells $0,1,\dots$ of the first tape and every other cell of every tape blank; each tape uses F5's clamped left boundary. Encode the word $x$ by its tuple of canonical symbol numerals, explicitly allowing arity zero with code $0$ for the empty word. The outer tuple contains the program, word and canonical $\mathrm{bin}(b)$; its self-delimiting syntax is included in the input-length accounting. These explicit extensions do not reinterpret any published one-tape code.

A finite parser reads unary lengths and the indicated blocks, verifies canonical numerals, the model tag, symbol/state ranges and the table's actual entry count, and rejects extra or missing bits. To check the expected count $(m-2)r^k$ against an actual count $a$, use integer arithmetic saturated at $a+1$: when $r\ge 2$ stop exponentiation as soon as it exceeds $a$, and when $r=1$ the power is one. Thus an enormous malformed tape-count numeral cannot force an enormous allocation. All malformed inputs halt rejecting by finite scans and finite arithmetic loops. On valid inputs for a fixed $M$, the whole program, $k$, alphabet widths and table length are constants. Scan the word blocks once, consuming their unary length headers on spare tapes and checking each symbol against the fixed alphabet; copy the decoded word to a sequential archive. Validate/copy the binary clock by one scan. These routines cost $O_M(n+\log (b+2))$ time and space: every input bit is traversed a bounded number of times, except scans of fixed $M$-data. The theorem claims no uniform time bound on malformed descriptions.

For the time interpreter, give each virtual tape a centre record and two ordered stacks of records extending outwards. Each record stores a tape symbol and an immutable origin bit, initially1 exactly at cell0. Writing changes only the symbol. The positive stack initially contains input cells1,2,... and then blanks on the first tape, and blanks on the others; the negative stacks initially contain blanks. Put $h_i=2^i$, $i\ge 0$. On each side zone $i$ has capacity $2h_i$, with occupancy in $\{0,h_i,2h_i\}$; holes use a distinct code, and ordinary blank symbols count as genuine records. Genuine records are packed at the near end in stack order. The two occupancies at each level sum to $2h_i$. Initially both are $h_i$, and the centre is the initial scanned cell. Ignoring holes and concatenating the zones gives the exact two stacks. The base zone has capacity2 and half-occupancy1.

Construct $U_{\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{c}\mathrm{e}}$ separately. Use the same validated finite program and input archive, but store the $k$ virtual tapes as delimited rows of fixed-width symbol records with one head flag per row. Include cells through the larger of the last initially occupied input cell and the furthest cell so far visited. Other tapes start blank. Sweeps locate the $k$ flags and read their symbols; a scan of the fixed program table selects the transition. Further sweeps write the symbols and move each flag to its adjacent record, clamping at zero and appending a blank record when needed. Inserting a record can shift a finite suffix from its right end with one temporary record, or copy the rows to a spare tape of their total length. Update the state only after all rows' actions. These operations produce exactly the next configuration and keep no history. No fast-time bound for the sweeps is asserted.

For a move towards the positive stack, first write the old centre $c$ as prescribed and choose the least $i$ with nonempty right zone. All lower right zones are empty and their left partners full. Remove the first $h_i$ records from right zone $i$. The first becomes the new centre; distribute the remaining $h_i-1={\sum }_{j<i}{h}_j$ in order into the lower right zones, with $h_j$ records in zone $j$. Right occupancy at $i$ decreases by $h_i$, from $h_i$ or $2h_i$ to0 or $h_i$. Prepend $c$ to the concatenated lower left zones. This list has $1+2{\sum }_{j<i}{h}_j=2h_i-1$ records. Keep its first $h_i-1$ in the lower left zones, half in each, and prepend the remaining $h_i$ to left zone $i$. Its old occupancy was0 or $h_i$, hence its new occupancy is $h_i$ or $2h_i$. Order and complementary occupancy are preserved; every lower zone ends half-full. At $i=0$ the lower lists are empty and these formulas simply transfer one record to the centre and prepend the old centre on the other side.

Realize the buffers on a fixed number of physical tapes over a fixed alphabet of binary digits and finitely many marker codes. The interpreter does not acquire $k$ physical tapes or an alphabet ${\mathrm{\Gamma }}^k$. Instead a physical slot is a delimited block of $k$ fixed-width symbol/origin-or-hole fields. For fixed $M$ its width and the saved program-table length are constants. Two tapes store the outward left/right zone sequences; other fixed tapes store centres, table, archive, countdown and scratch lists. A zone has endpoint and midpoint markers and one three-valued occupancy flag per virtual tape. Scanning through zone $i$ traverses $O_M({\sum }_{j\le i}2h_j)=O_M(2^i)$ physical cells. If binary level labels are used their total length $O({\sum }_{j\le i}\log (j+2))$ is also $O(2^i)$.

Interchange left and right for the negative-stack move. When a requested left move has the origin bit in its centre, perform the write but no stack move. Records retain their origin bits, so this is exactly the clamped convention and no auxiliary negative cell is scanned. A suitable source zone always exists, since untouched higher zones are half-full. Select the simulated transition from the original tuple of $k$ centre symbols, store its instructions, then process the $k$ buffer operations successively and update the state. Thus each completed simulated transition has exactly the writes, movements and state of $M$; one tape's redistribution does not alter another tape's fields.

Fix one virtual tape and $i\ge 1$. Let $q_i$ be total right occupancy below level $i$, and $H_i={\sum }_{j<i}{h}_j=2^i-1$. Initially $q_i=H_i$. Every operation at level at least $i$ resets these lower zones to half-full, again leaving $q_i=H_i$, including operations strictly above level $i$. Between these resets, a positive-stack move at a lower level decreases $q_i$ by exactly1, a negative-stack move increases it by exactly1, and a clamped move leaves it unchanged: redistribution conserves all lower right records except the single transfer through the centre. An operation at level at least $i$ requires all lower source zones empty, so immediately before it $q_i=0$ or $q_i=2H_i$. Reaching either endpoint from $H_i$ needs at least $H_i$ preceding lower-level moves, followed by the triggering move.

Find the least nonempty source zone by scanning its occupancy flags. Copy the affected genuine sublists of the chosen virtual field to scratch in stack order, then scan back to distribute the explicit lists from step 4.1. Preserve other virtual fields, write holes in unoccupied slots, and update occupancy flags. Midpoint and endpoint markers determine all half-capacities without per-record unbounded arithmetic. A fixed number of copying/writing/return scans of this prefix and its scratch lists implements the redistribution, costing $O_M(2^i)$. To extend the allocated prefix, copy a unary marker of the previous zone's capacity twice, putting a midpoint between the copies. Each copy and return is linear, and writing the fields and updating the unary marker costs the new zone's length. The first zone is a literal layout. Thus allocation also costs $O_M(2^i)$. These are fixed finite-state scan/copy routines with saved finite program data; no random access or unit-cost large-integer operation is assumed.

Maintain a binary countdown initially $b$. At each simulated configuration, test the state first and report its acceptance/rejection if halting. Otherwise reject if the countdown is zero; otherwise simulate one transition, decrement, and repeat. A whole-clock scan costs $O(\log (b+2))$ per transition, sufficient here without an additional amortization. A halt on the $b$th transition is reported, while a still-nonhalting configuration at expiry rejects. At $b=0$ the nonhalting initial state rejects before simulation; at $b=1$ exactly one transition is allowed. A zero clock occupies one digit.

Consequently each event at level at least $i$, including the first, is separated from the previous reset or the start by at least $H_i+1=2^i$ simulated transitions. Among $b$ transitions there are at most $\lfloor b\mathrm{/}{2}^i\rfloor$ such events, and in particular at most that many events exactly at level $i$. Higher resets are themselves counted events and cannot bypass this argument. There are at most $b$ level-zero events, and no level with $2^i>b$ is reached. This count applies separately to each of the fixed $k$ virtual tapes.

The convenient physical scan routines may use stationary heads. Compile this fixed physical machine to the left/right-only model by storing logical cell $j$ at physical cell $2j$. Implement each logical step by two physical steps: a right request uses $R,R$, a left request $L,L$, and a stationary request $R,L$. On the first step write the desired logical symbol and retain the finite tuple of pending moves in finite control; on the second preserve the currently scanned symbol and complete the movement. Intermediate odd cells have no logical role. A left request at zero clamps at zero on both steps. All heads again lie at the prescribed even cells, including mixed moving/stationary requests. The fixed number of physical heads makes the pending tuple finite-control data. This initial spacing also has a left/right-only linear implementation: process two input symbols per four steps, with source moves $R,R,L,R$ and destination moves $R,R,R,R$. Read the first symbol in the first step and the second in the second step, and write them at the destination even positions in the first and third steps. Ignore intermediate reads and preserve odd cells. One temporary symbol fits in finite control; an odd final symbol is paired with blank. The input delimiter detects the end, and a return sweep to marked cell zero is linear. Other unused heads oscillate in a four-step $R,L,R,L$ cycle. A spare tape receives the spaced input; the original raw-input tape is thereafter ignored. Thus initial spacing does not assume the stationary-head capability that is being compiled away. This compilation changes time and visited space by constant factors, plus input preparation.

Initialize only the centres, retaining the archive head at input position1; do not distribute the whole word into buffers. Unallocated zones mean their untouched initial half-full lists. On first reaching a new global level $i$, initialize its right half-list for the first virtual tape from the next $h_i$ archive symbols, then blanks if the archive is exhausted; all other tape fields and the left halves initially receive blanks. Fill unused halves with holes. Initially that right zone represents positions $2^i,\dots ,2^{i+1}-1$. Operations below it leave this suffix unchanged, and new levels are allocated in increasing order, so the archive is exactly at the next untouched interval. If another virtual tape forces allocation first, initialize all fields of that zone then. Each symbol is read from the archive at most once and no scan back through the long input is needed. Allocation is charged to the first event reaching that level as in step 6.2. For $b\ll \mathrm{\mid }x\mathrm{\mid }$ there is only the initial $O_M(n)$ archive scan plus the lazily reached buffer prefix, not $O_M(n\log n)$ preprocessing.

If $v_j$ is the visited extent on tape $j$, the first row has at most $\mathrm{\mid }x\mathrm{\mid }+v_1+1$ records and every other row at most $v_j+1$. Including fixed-width symbols, delimiters, saved code/input and scratch copies gives $O_M(n+{\sum }_j{v}_j)$ visited cells. Since a head starts at zero and moves by adjacent steps, its visited cells form this initial interval; their sum is the statement's $S$, up to the harmless fixed endpoint convention. Add the $O(\log (b+2))$-cell countdown and use the test-before-expiry loop of step 6.3. The finite valid-input decoder and saved tables use $O_M(n+\log (b+2))$ space by step 2.1. Spacing and the two-step physical compilation of step 7.2 change only constants. Hence this distinct interpreter uses $O_M(n+S+\log (b+2))$ visited space.

For $b\ge 1$, steps 7.1 and 6.2 bound the total buffer work on all virtual tapes by $C_{M}b+C_M{\sum }_{i=1}^{\lfloor {\log }_{2}b\rfloor }{2}^i\lfloor b\mathrm{/}{2}^i\rfloor \le C_{M}b(1+\lfloor {\log }_{2}b\rfloor )\mathrm{.}$ Initialization costs $O_M(n+\log (b+2))$, table/centre processing $O_M(b)$, and clock work $O(b\log (b+2))$. Including the fixed compilation gives $O_M(n+b\log (b+2))$. At $b=0$ no buffer or transition work occurs and the constant clock length is absorbed by the nonempty encoded-input syntax. This constructs $U_{\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}}$. No linear visited-space claim for its buffers has been used or proved.

Both interpreters halt rejecting malformed encodings, and reproduce the same bounded acceptance/rejection behavior on valid inputs by the configuration invariants and expiry test. Neither interpreter's resource proof is imported into the other. If the clock is produced by a constructor rather than supplied, add that constructor's separately declared time/workspace. All choices above are explicit finite scans and prescribed lists; no choice axiom is used.

For total $g,h$, fix $\mathbf{a}$. On $\mathbb{N}\times \mathbb{N}$ set $A_0=(0,g(\mathbf{a}))$ and $H_{\mathbf{a}}(y,z)=(y+1,h(\mathbf{a},y,z))$. Recursion produces a unique sequence $A_y$. Its first coordinate is $y$: it is zero initially and increments at each step. Its second coordinate therefore satisfies exactly the two equations defining $f(\mathbf{a},y)$.

If another function satisfied those equations, its pairs $(y,f(\mathbf{a},y))$ would be the same unique recursion solution. Thus each parameter tuple and each $y$ have exactly one value. Define the parameterized graph by that unique-solution property inside ${\mathbb{N}}^{k+1}\times \mathbb{N}$; this is not a choice of solutions from possibly many witnesses. Composition of total functions is total, and the initial functions are total. Applying these observations successively at the finitely many nodes of a derivation tree proves totality of its denoted function. Empty parameter tuples and nullary constants obey the same construction.

The recursions $a+0=a$, $a+(b+1)=S(a+b)$, $a\cdot 0=0$, $a\cdot (b+1)=a\cdot b+a$, $a^0=1$, $a^{b+1}=a^{b}a$ give addition, multiplication and powers. Predecessor is $P(0)=0$, $P(b+1)=b$, so truncated subtraction is , . The zero test $Z(0)=1$, $Z(b+1)=0$ yields and . All are applications of the schemes, with total values even at zero.

For PR $u(\mathbf{a},j)$, accumulate sums from initial value zero and products from one for $j=0,\dots ,B-1$ by primitive recursion on $B$. Products of Boolean values give bounded universal quantification and $1$ minus a product of complements gives bounded existential quantification. For a PR predicate $R$, its least witness at most $B$ with failure value $B+1$ is ${\sum }_{j=0}^B{\prod }_{i=0}^j(1-[R(\mathbf{a},i)])\mathrm{.}$ If the least witness is $r$, precisely the terms $j<r$ equal one; if none exists, all $B+1$ terms equal one. Bounded maximum can be obtained by searching in reverse or accumulating the latest successful index, initially zero. Conditional branches are arithmetic combinations with a Boolean selector.

For $d>0$, divisibility $d\mid z$ is $\mathrm{\exists }q\le z(dq=z)$. A quotient, if present, is found by bounded least search. On $z>0$, let $a$ be the largest $a\le z$ such that $2^a\mid z$. Such an $a$ exists since $2^0=1$. A maximal one has odd quotient: an even quotient would make $2^{a+1}$ divide $z$. Repeated division by two strictly decreases a positive even number, so this process terminates at an odd positive integer. It also proves uniqueness: if $2^{a}u=2^{b}v$ with odd positive $u,v$ and $a<b$, cancellation would make $u$ even. Thus the bounded definition is exactly the two-adic valuation. The odd quotient has the unique form $2b+1$; find $b\le z$ by bounded search. These are the claimed head and tail functions with explicit zero branches.

For $z>0$, $\mathrm{tail}(z)=(z\mathrm{/}{2}^a-1)\mathrm{/}2<z$. Let $t(z,0)=z$ and $t(z,j+1)=\mathrm{tail}(t(z,j))$. Primitive recursion makes $t$ PR. A strictly decreasing sequence of positive naturals starting at $z$ has at most $z$ terms: after $j$ decreases its value is at most $z-j$. Therefore $\mathrm{\ell }(z)={\sum }_{j<z}(1-Z(t(z,j)))$ is precisely the list length. The list represented by any natural is well-founded; conversely successive cons operations encode each finite list, and the unique head/tail decomposition makes the encoding injective. Its coordinate function is $\mathrm{head}(t(z,i))$, zero when $i\ge \mathrm{\ell }(z)$.

Define $r(z,0)=0$ and $r(z,j+1)=\mathrm{cons}(\mathrm{head}(t(z,j)),r(z,j))$. Then $\mathrm{rev}(z)=r(z,\mathrm{\ell }(z))$ reverses the list: after $j$ steps it contains the first $j$ entries in reverse order, by checking the initial value and the cons step. Appending $a$ is $\mathrm{rev}(\mathrm{cons}(a,\mathrm{rev}(z)))$. To concatenate $z$ with $w$, start the accumulator at $w$ and cons the entries of $\mathrm{rev}(z)$ in order, stopping after $\mathrm{\ell }(z)$ steps. Its result is the entries of $z$ followed by those of $w$. These bounded folds are PR even though their accumulator values need not be bounded by the input code.

Bounded list predicates are sums/products of tests on these coordinates. In particular a word parser can maintain a cursor and finite coded state for at most the word's length plus one iterations. Each iteration reads a coordinate, compares bounded lengths, updates arithmetic counters and appends decoded letters; on failure it records a fixed failure state and remains there. Every such update is one of the PR operations already proved, so primitive recursion implements the entire bounded scan. Binary numeral conversion uses the fold $v\mapsto 2v+\text{bit}$; the reverse conversion finds the largest $j\le v+1$ with $2^j\le v$ when $v>0$, then uses bounded division to obtain its bits, with the separate one-bit representation of zero. Empty lists have length zero and reverse zero; a singleton $\mathrm{cons}(a,0)$ has length one and coordinate zero equal to $a$. Empty sums/products are zero/one. No unbounded minimization or inference from computability to PR has been used.

Decode the word of index $e$ by binary expansion of $e+1$ and deleting its leading bit. The operations are PR by F2. Parse its unary arity header and each unary-length block with a cursor, taking at most word length plus one parser rounds; failed states stay failed. Horner conversion decodes a numeral. Check canonicality, $m\ge 3$, $r\ge 1$, $s<r$, $s\ge 2$, tuple length $3+3(m-2)r$, and the ranges of every triple. Multiplication and comparisons are PR; bounded iteration over the actual list checks every entry and no unprovided entries. Hence program validity and decoded table lookup, with a fixed zero fallback on failure, are PR.

For a candidate configuration, its list must have exactly three entries. Check state range, $h<\mathrm{\ell }(v)$, all symbol ranges and the trimming condition in F1 by bounded comparisons and a scan of $v$. Construct the initial tape word by converting each of the fixed $k$ input numbers into its canonical numeral, appending the arity and length headers, and changing bit $i$ to letter $i+1$. All these are bounded folds in F2; their bounds may be PR functions of the arguments, not constant bounds. Its initial configuration code has state/head zero and the resulting nonempty tape word, so equality of the proposed first entry with it is PR.

For two valid configuration codes $(q,h,v)$ and $(q^{\mathrm{\prime }},h^{\mathrm{\prime }},v^{\mathrm{\prime }})$, reject if $q$ is halting. Otherwise read the table entry for $q$ and the coordinate $v_h$, obtaining $(p,b,d)$. Check $q^{\mathrm{\prime }}=p$, $v_h^{\mathrm{\prime }}=b$, and $v_j^{\mathrm{\prime }}=v_j$ at each $j<\max (\mathrm{\ell }(v),\mathrm{\ell }(v^{\mathrm{\prime }}))$ other than $h$. Beyond this bound both tapes are blank. Check $h^{\mathrm{\prime }}=h+1$ if $d=1$ and $h^{\mathrm{\prime }}=\max (h-1,0)$ if $d=0$. These PR checks express precisely one actual step, including clamping and any new last cell; the validity tests already require canonical trimming on both sides.

A bounded conjunction over the history list tests all configurations and all adjacent pairs. Nonemptiness and first/last entry checks are PR. For terminal output, find the first coordinate of the last tape list not in $\{1,2\}$, using its length as the value if no such coordinate occurs. This stopping rule gives exactly the maximal bit prefix; only in the latter case is its next implicit cell necessarily blank. Reject an empty prefix; accept a leading $1$ bit or the single bit $0$. Horner accumulation computes its value. On any syntactic failure set $U$ to zero. All scans are bounded by a decoded finite length, proving that $U$ is total PR and the conjunction $T_k$ is PR. No search for a halting time occurs in these tests.

If $T_k$ holds, its initial check places the list at the actual starting configuration. At every subsequent position the exact step check produces the unique next configuration, so successor induction identifies the entire list with an initial segment of the actual run. Its final state is halting and all earlier ones are nonhalting, hence this is the first halt and has canonical output. Conversely, a finite actual run ending at its first halt with canonical output has finitely supported tapes; trim and encode its configurations as prescribed and cons them into a history. It passes every check. The start is nonhalting, so a purported length-one halting history does not pass.

Two witnessing histories coincide at every common time by determinism and induction. If one were shorter, the longer would have a nonhalting entry at the time where the shorter has its halting entry, impossible since these entries coincide. Thus their lengths and final configurations coincide, and the deterministic extraction in U gives the same value. Empty histories are false, malformed indices have no witnesses, and invalid output has no witness although U itself remains total. This proves all claims without an assumption of eventual halting or any choice.

Since $T_k$ is a total Boolean predicate, test $z=0,1,2,\dots$ in order. If some witness exists this search reaches the least one after finitely many terminating tests; if none exists it never terminates. F1 then gives exactly the numerical function and domain of ${\phi }_e^{(k)}$. Since PR functions belong to the partial recursive class, composition of U with minimization of $1-[T_k]$ is partial recursive. Thus every machine function belongs to that class.

Here are finite tape routines for the converse. Store finitely many finite words in delimited zones, with marked versions of each symbol. To copy a zone, find its next unmarked symbol by a left-to-right sweep, mark it, carry that symbol in the finite control to the destination delimiter, append it, and return to the source; after its end delimiter is reached, unmark the source. To insert room, scan to the last occupied delimiter and shift the suffix right by one cell, working from right to left while carrying one symbol. Erasing and testing an empty zone are sweeps to its delimiter. Binary increment scans rightward to the last digit, changes trailing ones to zero and the preceding zero to one, inserting a leading one if necessary. Zero testing compares with the one-letter zero word. Each sweep terminates on a finite zone; its cases concern a finite alphabet, so each description expands to finitely many states and transitions. Distinct control-state tags prevent interference. A left-edge flag prevents a sweep going below zero. If a routine uses a stationary move, store logical cells at even physical positions: a stationary action is right-left, a right move is right-right and a left move is left-left, with right-left for a clamped left move at zero. Delay a requested halt to the end of the two-transition action. This gives the stipulated left/right-only one-tape model.

Parse and copy the tuple inputs by these routines. Zero writes the single zero numeral, successor applies binary increment, and a projection copies its designated input numeral. For a composition $h(g_1(\mathbf{a}),\dots ,g_r(\mathbf{a}))$, keep the original tuple, run the $g_i$ sequentially on copies, save each canonical result, form their tuple and run $h$. To invoke a compiled machine without allowing its tape to destroy stored arguments, simulate its finite configuration in a separate zone using F3, retaining the calling zones outside that encoded tape. Copy its final output back only after a valid numeric halt; on invalid output or malformed code enter an endless rightward walk. Interpreter code and finite program constants can be inserted with renamed states and finite literal-writing chains. All required subcalls terminate exactly when their represented functions are defined. Thus the composition is strict in every inner argument, including when the outer function happens to ignore an argument.

For primitive recursion, retain $\mathbf{a}$ and the target $y$. Run $g(\mathbf{a})$, then for $j=0,\dots ,y-1$ run $h(\mathbf{a},j,z)$ where $z$ is the previous result, increment $j$ and replace $z$. At $y=0$ there are no calls to h. If any required call diverges, the entire computation diverges. Otherwise the loop makes exactly $y$ calls and its successive stored values satisfy the recursion equations, so it computes their strict partial interpretation. Nullary g is a constant routine on the empty stored argument list; it needs no arity-zero numeric evaluator.

For minimization, start $j=0$, run the compiled $g(\mathbf{a},j)$, output j on zero, and increment and repeat on nonzero. An undefined call blocks forever; it is not bypassed by dovetailing. Consequently termination at z occurs exactly under the minimization condition in the Statement. Each finite derivation of a partial recursive function now produces a finite program: process its tree from leaves to root using the preceding compilation constructions. The process is effective, since renaming a finite list of states, writing a literal constant, combining finite tables and encoding a table are finite scans with the explicit routines of step 1.2.

The programs thus built erase scratch, write the canonical output at the left edge, and halt only on a defined value; the internal simulation keeps scratch outside each simulated tape. They therefore compute the represented partial functions with precisely the required domains. Conversely step 1.1 covers every valid machine and assigns the empty domain to malformed or invalid-output indices. This proves the normal form and both inclusions of classes, including functions undefined everywhere. No complexity bound on the compiler or search is asserted.

Identity is total computable and preserves membership, so $A{\le }_{m}A$. If f reduces A to B and g reduces B to C, compute f then g; both halt on every natural, and $n\in A$ iff $f(n)\in B$ iff $g(f(n))\in C$. The same sequential program works with oracle X for both routines, routing each query to X. String-valued identity and composition obey the identical membership calculation.

Given a numeric reduction f, parse a source word. On a canonical numeral for n, add the numeric machine's tuple wrapper, run f, decode its numeric result and output $\mathrm{bin}(f(n))$. On malformed input output the one-letter zero. This is total and meets precisely the canonical-input specification. Conversely a total string map having canonical outputs on all canonical inputs gives a total numeric map by forming $\mathrm{bin}(n)$, running the map, and decoding its canonical output. The iff of membership is preserved in each direction. These finite encoders/decoders work unchanged relative to X. Malformed input is outside this bridge's specification; choosing zero there would not in general reduce the full numeral-image language if $0\in B$.

To decide A from B when $A{\le }_{m}B$, run the total map f, put its canonical result on the query tape, make one query to B and output that bit. Both f and the single query terminate, and the iff in F1 gives the correct answer. Identity querying also decides any B from itself.

Suppose $A{\le }_{T}B$ and $B{\le }_{T}C$. A C-program simulates the A-decider, keeping its finite configuration in a protected work zone. When the simulated machine queries a canonical number b, run the total C-decider for B on b in separate work zones, and return its bit as the simulated B answer; malformed queries return zero immediately. Finite table simulation and work-zone copying do not depend on knowing B. Each subcall halts. On a fixed input the original A computation has finitely many transitions and queries; induction over those transitions shows the composite eventually reaches the same halt and bit. Thus $A{\le }_{T}C$, with no uniform bound on the lengths or number of subcalls required. Replacing the B-decider by a recognizer would invalidate this argument at a negative query, since that call might diverge.

For evaluation, decode e into its word and validate it, looping forever if invalid. Construct the initial configuration on the one-entry tuple for x and iterate F2 until its first halt. Extract the canonical numeral if present and otherwise loop forever. The finite decoding and tape-zone routines in F1 implement the preprocessing and iteration; F3 identifies the result and domain exactly with ${\phi }_e(x)$. Every finite program has an index, and F1 compiles every numerical partial computable function, proving exhaustivity.

Given e,d, generate a program which retains its unary input x, runs the evaluator on $(d,x)$, retains its numeric result y, and runs the evaluator on $(e,y)$. Include e and d by finite chains of states writing their canonical bits; rename the evaluator's state copies to disjoint consecutive state intervals and use delimited work zones as in F1. Set the three designated states to 0,1,2, assign numbers to all remaining states and tape symbols, and fill unused state-symbol entries with transitions to an explicit infinite rightward walk. Emit every transition in the fixed lexicographic syntax and encode the table. If w is the resulting word, its index is $2^{\mathrm{\mid }w\mathrm{\mid }}-1+\mathrm{val}(w)$. Scanning finite tables and binary arithmetic are halting tape routines from F1, so this compiler c is total on all e,d, independently of whether the generated program will halt.

On x the generated program halts exactly when the d-evaluation halts with y and the e-evaluation on y halts. In that event it returns the latter value; if either call diverges, so does the composite. This is the strict composition equation. A malformed e or d causes the corresponding evaluation to diverge, exactly as required. Thus universality and the total composition compiler hold without assuming specialization or fixed points.

Generate the following finite program. Parse its input as exactly an n-entry tuple of canonical numerals, entering an endless walk on failure. Retain those entries, write the literal canonical numerals $a_1,\dots ,a_m$ into new zones, and form the tuple with arity header $1^{m+n}0$, the m parameter blocks and the n retained input blocks. Each word block w is written as $1^{\mathrm{\mid }w\mathrm{\mid }}0w$. Run the raw evaluator on program e and that tuple word, with canonical output normalization. F1 implements the evaluator and the literal-writing chains; F2 implements the parser and tuple construction. Encode the resulting finite table and return its length-lex index. This defines $s_m^n$.

Code generation does not execute e. It scans only the finite arities, parameter numerals and fixed evaluator template, expanding each literal into a finite writing-state chain. It therefore halts for every allowed input, even when e is malformed or represents a divergent function. A single generator handles all m,n by loops over their finite numerals and parameter list. On malformed generator inputs it may return a fixed index; the stated compiler uses only the valid ones.

On the tuple for $\mathbf{y}$, the generated parser succeeds and supplies exactly $E(\mathrm{bin}(\mathbf{a}),\mathrm{bin}(\mathbf{y}))$ to the raw e-evaluator. Every preprocessing operation terminates. Thus its subsequent run has exactly the canonical output of that evaluation or diverges exactly when that evaluation is undefined. This proves the displayed equality of domains and values, including zero parameters, zero-valued inputs, malformed e and empty partial domains. For m=n=1 the construction simply prepends one stored numeral and changes the arity header to two.

Compile a binary program q which on $(z,y)$ first computes $s(z,z)$, then evaluates f on that number, obtaining $F(s(z,z))$, then evaluates that index on y. F1 supplies the first terminating subroutine, totality of F the second, and F2 the possibly partial last evaluation. Thus its binary function is $H(z,y)\simeq {\phi }_{F(s(z,z))}(y)$. The finite compiler inserts f literally, so q is obtained effectively from f without running F during code generation.

Compute $e=s(q,q)$. For each y, specialization gives ${\phi }_e(y)\simeq H(q,y)\simeq {\phi }_{F(s(q,q))}(y)={\phi }_{F(e)}(y)$. The first two subcalls in H terminate, so either the last call halts with exactly the asserted value or both sides are undefined. This proves equality of the partial domains as well as values. Computing q and then e is a halting transformation of the given index f; if the promise of totality fails the transformation still produces a number, but the asserted fixed-point conclusion is not inferred.

A head visits at most T new cells in T transitions. Thus an output word occupies at most its initially occupied input extent plus T plus one cells: a polynomial time bound gives a polynomial output-length bound when input and output share a tape, and at most T plus one on an initially blank output tape. For composition of reductions with time/length bounds $C(n+1{)}^a$ and $D(n+1{)}^b$, the first output has length at most $n+C(n+1{)}^a+1$. Retain that result on work tapes and run the second fixed machine on it. The two fixed programs can be joined on finitely many tapes, with linear copying/preparation time. Their combined time is bounded by a constant multiple of $C(n+1{)}^a+D(n+C(n+1{)}^a+2{)}^b+n+1$, a polynomial. The membership iff composes, proving transitivity.

If fixed-length certificates are wanted, let $P=p(\mathrm{\mid }x\mathrm{\mid })$. Encode a witness w of length $\mathrm{\ell }\le P$ by the length field $1^{\mathrm{\ell }}{0}^{P+1-\mathrm{\ell }}$ followed by $w{0}^{P-\mathrm{\ell }}$, a word of length $2P+1$. The verifier rejects certificates whose total length is not $2P+1$, then checks the field consists of at most P initial ones followed by zeros, then checks the last $P-\mathrm{\ell }$ payload bits are zero, and applies R to the first $\mathrm{\ell }$ payload bits. Every guarded witness has this encoding, and every accepted encoding decodes one guarded witness. Scanning and evaluating p in binary and writing at most polynomially many cells are polynomial operations for the fixed polynomial p (successive addition/multiplication of its fixed number of binary factors suffices). The case P=0 has certificate 0 and decoded empty witness. This optional padding therefore preserves the language and polynomial bounds.

A fixed prefix of j bits occurs in $2^{p(n)-j}$ words, hence has mass $2^{-j}$. More generally, prescribing any j distinct bit positions leaves $p(n)-j$ free coordinates and has the same count. Each marginal is one half, and the joint probabilities factor, exactly as in F1. The empty prescription has mass one.

For a fixed supplied word, the simulator and the PTM take the same first table, and agreement through transition j makes them use the same table and configuration at the next transition. Thus they agree up to the halt by induction. A branch halting after j steps corresponds to precisely the words with that consumed prefix, of total mass $2^{-j}$; prefixes for distinct terminal branches are disjoint. Summing their masses proves agreement with fresh fair-bit semantics, even when the stopping time depends on previous bits. Unused suffixes have been counted, not assumed independent of a stopping rule. For p(n)=0 the space is the singleton containing the empty word; in a model with nonhalting start such a bound is impossible on that input, which is consistent with the definition.

At a finite cutoff K, $\min (T,K)={\sum }_{j<K}{\mathbf{1}}_{\{T>j\}}$ on the finite space of K bits, so its expectation is ${\sum }_{j<K}{q}_j$. The equality follows pointwise by counting the j before the truncated halt. Thus F2 makes the displayed survival sum an exact extension of finite expected runtime. On the K-bit space $\mathbb{P}(\min (T,K)\ge K)=q_{K-1}$ for K positive, hence F3 gives $q_K\le q_{K-1}\le \mathbb{E}T\mathrm{/}K$. This also follows by adding the first K decreasing survival terms. If the expectation is finite, choosing arbitrarily large K shows $q_K\to 0$. No nonhalting mass has been silently omitted from a sum over halting prefixes.

Given expected runtime at most p(n), truncate the machine after $2p(n)$ simulated transitions, preserving any halt reached on the last allowed transition, and return unknown otherwise. Step 1.1 bounds unknown probability $q_{2p(n)}\le 1\mathrm{/}2$. A deterministic counter and a direct simulation of this one fixed machine cost polynomial time even if a counter scan is used at every transition. A returned yes/no is an actual terminal answer, so it is never wrong. This proves the bounded-unknown formulation from the expected-time one.

Conversely let a bounded-unknown algorithm cost at most p(n) per attempt. Repeat after unknown, with disjoint fresh blocks, until yes/no. Include input restoration and block generation in a larger polynomial bound P(n). Independence of complete blocks gives probability of reaching attempt r at most $2^{-(r-1)}$, by multiplying the conditional failure probability at each restart. Grouping the first KP(n) survival terms by attempts gives expected runtime at most $P(n){\sum }_{r=0}^{K-1}{2}^{-r}\le 2P(n)$. The finite sum identity follows on multiplying by one half and subtracting: ${\sum }_{r<K}{2}^{-r}=2(1-2^{-K})$. Every shorter prefix sum has the same upper bound by monotonicity, so F2 gives total expectation at most $2P(n)$. Step 1.1 gives probability-one halting; no attempt can return a wrong answer.

If L is in both RP and coRP, run its two bounded machines with independent bit blocks. An RP acceptance certifies membership; a coRP rejection certifies nonmembership; if neither occurs, output unknown. On a member the coRP machine never rejects and the RP machine certifies yes with probability at least one half. On a nonmember the RP machine never accepts and the coRP machine certifies no with probability at least one half. Both certificates cannot occur on any input branch: a zero-probability bad terminal event in a finite uniform space is empty. Thus this procedure is never wrong and has unknown probability at most one half.

From a bounded-unknown zero-error procedure obtain an RP machine by interpreting unknown as no, and a coRP machine by interpreting unknown as yes. The successful correct answer has probability at least one half on the relevant input side; the opposite wrong certificate has probability zero. Together with step 3.1 and the equivalence established above, this proves $\mathrm{Z}\mathrm{P}\mathrm{P}=\mathrm{R}\mathrm{P}\cap \mathrm{c}\mathrm{o}\mathrm{R}\mathrm{P}$. Empty languages, full languages and empty input cause no change: the polynomial guard is positive and the correct deterministic output is permitted. None of these transformations changes PP's strict threshold to a BPP gap.

Fix x and a desired u. For each $a\in F$, the equation $ax+b=u$ has the unique solution $b=u-ax$ by additive cancellation. Hence exactly $\mathrm{\mid }F\mathrm{\mid }$ of $\mathrm{\mid }F{\mathrm{\mid }}^2$ seeds give u, proving marginal probability $1\mathrm{/}\mathrm{\mid }F\mathrm{\mid }$. In particular the seed with a=0 is necessary to this full family and is permitted. F is nonempty, indeed has at least two elements by F1.

For distinct x,y and prescribed u,v, subtraction gives $a(x-y)=u-v$. The nonzero $x-y$ has an inverse, so necessarily $a=(u-v)(x-y{)}^{-1}$ and $b=u-ax$. These values work: $ay+b=u-a(x-y)=v$. They are unique by multiplication by the inverse and additive cancellation; uniqueness of an inverse itself follows from $c=c((x-y)d)=(c(x-y))d=d$ when c,d are both inverses. Exactly one seed therefore realizes each ordered output pair, with probability $1\mathrm{/}\mathrm{\mid }F{\mathrm{\mid }}^2$, equal to the product of the marginals from step 1.1. This proves pairwise independence. Equal x,y are intentionally excluded: their values cannot be independently prescribed.