Let \(c, C, q \in \mathbb {N}\), \(x\) a bit string, \(s, s'\) control states of the unary box enumerator \(\mathcal{P}_{c,C}\), \(h \colon \{ 0,\dots ,c\} \to \mathbb {Z}\), \(o\) an output word, \(i \in \{ 0,\dots ,c\} \) and \(d \in \{ -1,0,1\} \). Applying the action that moves only work head \(i\) by \(d\) (writing nothing, emitting nothing, input head fixed) and enters \(s'\) to \(\Gamma _q(s,h,o)\) gives \(\Gamma _q(s', h[i \mapsto h(i)+d], o)\); here \(\Gamma _q(s,h,o)\) denotes its configuration on input \(x\) in control state \(s\), with the input head on the blank cell right of the input, every work tape holding \(1^q\) in cells \(0,\dots ,q-1\) and blanks elsewhere, work head \(k\) at position \(h(k)\), and output \(o\), and \(h[i \mapsto v]\) is \(h\) with its \(i\)-th entry replaced by \(v\).

Let \(c, C, q \in \mathbb {N}\), \(x\) a bit string and \(h \colon \{ 0,\dots ,c\} \to \mathbb {Z}\). For every \(j \le C\) and every output word \(o\), running \(\mathcal{P}_{c,C}\) for exactly \(j+1\) steps from \(\Gamma _q(\mathrm{emit}_j, h, o)\) yields \(\Gamma _q(\mathrm{advance}_0, h, o\, 1^j)\); here \(\mathcal{P}_{c,C}\) is the unary box-enumeration machine with \(c+1\) work tapes, which writes \(1^{|x|+1}\) on every work tape and then runs \(c+1\) nested unary loops, emitting \(C\) ones per innermost iteration, and \(\mathrm{loop}_i\), \(\mathrm{rewind}_i\), \(\mathrm{advance}_i\), \(\mathrm{emit}_j\) are its control states, and \(\Gamma _q(s,h,o)\) denotes its configuration on input \(x\) in control state \(s\), with the input head on the blank cell right of the input, every work tape holding \(1^q\) in cells \(0,\dots ,q-1\) and blanks elsewhere, work head \(k\) at position \(h(k)\), and output \(o\).

Let \(c, C, q \in \mathbb {N}\), \(x\) a bit string, \(h \colon \{ 0,\dots ,c\} \to \mathbb {Z}\), \(o\) an output word and \(i \in \{ 0,\dots ,c\} \). For every \(j \le q\), running \(\mathcal{P}_{c,C}\) for exactly \(j+1\) steps from \(\Gamma _q(\mathrm{rewind}_i, h[i \mapsto j-1], o)\) yields \(\Gamma _q(\mathrm{advance}_{i+1}, h[i \mapsto 0], o)\); here \(\mathcal{P}_{c,C}\) is the unary box-enumeration machine with \(c+1\) work tapes, which writes \(1^{|x|+1}\) on every work tape and then runs \(c+1\) nested unary loops, emitting \(C\) ones per innermost iteration, and \(\mathrm{loop}_i\), \(\mathrm{rewind}_i\), \(\mathrm{advance}_i\), \(\mathrm{emit}_j\) are its control states, \(\Gamma _q(s,h,o)\) denotes its configuration on input \(x\) in control state \(s\), with the input head on the blank cell right of the input, every work tape holding \(1^q\) in cells \(0,\dots ,q-1\) and blanks elsewhere, work head \(k\) at position \(h(k)\), and output \(o\), and \(h[i \mapsto v]\) is \(h\) with its \(i\)-th entry replaced by \(v\).

Let \(c, C, q \in \mathbb {N}\), \(x\) a bit string, \(h \colon \{ 0,\dots ,c\} \to \mathbb {Z}\), \(o\) an output word and \(i \in \{ 0,\dots ,c\} \). One step of \(\mathcal{P}_{c,C}\) from \(\Gamma _q(\mathrm{advance}_i, h, o)\) yields \(\Gamma _q(\mathrm{loop}_i, h[i \mapsto h(i)+1], o)\); here \(\mathcal{P}_{c,C}\) is the unary box-enumeration machine with \(c+1\) work tapes, which writes \(1^{|x|+1}\) on every work tape and then runs \(c+1\) nested unary loops, emitting \(C\) ones per innermost iteration, and \(\mathrm{loop}_i\), \(\mathrm{rewind}_i\), \(\mathrm{advance}_i\), \(\mathrm{emit}_j\) are its control states, \(\Gamma _q(s,h,o)\) denotes its configuration on input \(x\) in control state \(s\), with the input head on the blank cell right of the input, every work tape holding \(1^q\) in cells \(0,\dots ,q-1\) and blanks elsewhere, work head \(k\) at position \(h(k)\), and output \(o\), and \(h[i \mapsto v]\) is \(h\) with its \(i\)-th entry replaced by \(v\).

Let \(c, C, q \in \mathbb {N}\) with \(q \gt 0\), \(x\) a bit string, \(i \le c\), \(h \colon \{ 0,\dots ,c\} \to \mathbb {Z}\) with \(h(k) = 0\) for every \(k \le i\), \(o\) an output word, and \(r, j \in \mathbb {N}\) with \(j + r = q\). Then running \(\mathcal{P}_{c,C}\) for exactly \(r\, (\kappa _{q,C}(i) + 2) + q + 2\) steps from \(\Gamma _q(\mathrm{loop}_i, h[i \mapsto j], o)\) yields \(\Gamma _q(\mathrm{advance}_{i+1}, h, o\, 1^{rCq^i})\), where \(\kappa _{q,C}(0) = C+1\) and \(\kappa _{q,C}(r'+1) = q(\kappa _{q,C}(r')+2)+q+2\); here \(\mathcal{P}_{c,C}\) is the unary box-enumeration machine with \(c+1\) work tapes, which writes \(1^{|x|+1}\) on every work tape and then runs \(c+1\) nested unary loops, emitting \(C\) ones per innermost iteration, and \(\mathrm{loop}_i\), \(\mathrm{rewind}_i\), \(\mathrm{advance}_i\), \(\mathrm{emit}_j\) are its control states, \(\Gamma _q(s,h,o)\) denotes its configuration on input \(x\) in control state \(s\), with the input head on the blank cell right of the input, every work tape holding \(1^q\) in cells \(0,\dots ,q-1\) and blanks elsewhere, work head \(k\) at position \(h(k)\), and output \(o\), and \(h[i \mapsto v]\) is \(h\) with its \(i\)-th entry replaced by \(v\).

For every \(q \in \mathbb {N}\), writing the symbol \(1\) into cell \(q\) of the tape contents \(\tau _q\) yields \(\tau _{q+1}\), where \(\tau _q \colon \mathbb {Z} \to \{ 0,1,\sqcup \} \) holds \(1\) on cells \(0,\dots ,q-1\) and the blank \(\sqcup \) elsewhere.

Let \(q, C \in \mathbb {N}\) with \(q \gt 0\), and let \(\kappa _{q,C} \colon \mathbb {N} \to \mathbb {N}\) be given by \(\kappa _{q,C}(0) = C + 1\) and \(\kappa _{q,C}(r+1) = q(\kappa _{q,C}(r) + 2) + q + 2\). Then \(\kappa _{q,C}(r) \le (C + 1 + 5r)\, q^r\) for every \(r \in \mathbb {N}\).

Let \(c, C \in \mathbb {N}\) and let \(x\) be a bit string. For every \(i \le |x|\), running \(\mathcal{P}_{c,C}\) for \(i\) steps from its initial configuration on \(x\) yields the configuration in the copy state with the input head on input position \(i\) (counting from \(0\)), every work tape holding \(1^i\) in cells \(0,\dots ,i-1\) and blanks elsewhere, every work head at cell \(i\), and empty output; here \(\mathcal{P}_{c,C}\) is the unary box-enumeration machine with \(c+1\) work tapes, which writes \(1^{|x|+1}\) on every work tape and then runs \(c+1\) nested unary loops, emitting \(C\) ones per innermost iteration, and \(\mathrm{loop}_i\), \(\mathrm{rewind}_i\), \(\mathrm{advance}_i\), \(\mathrm{emit}_j\) are its control states.

Let \(c, C, q \in \mathbb {N}\) and let \(x\) be a bit string. For every \(j \le q\), running \(\mathcal{P}_{c,C}\) for exactly \(j+1\) steps from \(\Gamma _q(\mathrm{setup}, h, \varepsilon )\), where every work head is at position \(h(k) = j-1\), yields \(\Gamma _q(\mathrm{loop}_c, h_0, \varepsilon )\), where every work head is at \(h_0(k) = 0\); here \(\mathcal{P}_{c,C}\) is the unary box-enumeration machine with \(c+1\) work tapes, which writes \(1^{|x|+1}\) on every work tape and then runs \(c+1\) nested unary loops, emitting \(C\) ones per innermost iteration, and \(\mathrm{loop}_i\), \(\mathrm{rewind}_i\), \(\mathrm{advance}_i\), \(\mathrm{emit}_j\) are its control states, setup is its rewinding state, and \(\Gamma _q(s,h,o)\) denotes its configuration on input \(x\) in control state \(s\), with the input head on the blank cell right of the input, every work tape holding \(1^q\) in cells \(0,\dots ,q-1\) and blanks elsewhere, work head \(k\) at position \(h(k)\), and output \(o\).

Let \(c, C \in \mathbb {N}\) and let \(x\) be a bit string. After exactly \(2(|x|+1)\) steps from its initial configuration on \(x\), \(\mathcal{P}_{c,C}\) is in control state \(\mathrm{loop}_c\), with its input head on the blank cell right of the input, every work tape holding \(1^{|x|+1}\) in cells \(0,\dots ,|x|\) and blanks elsewhere, every work head at cell \(0\), and empty output; here \(\mathcal{P}_{c,C}\) is the unary box-enumeration machine with \(c+1\) work tapes, which writes \(1^{|x|+1}\) on every work tape and then runs \(c+1\) nested unary loops, emitting \(C\) ones per innermost iteration, and \(\mathrm{loop}_i\), \(\mathrm{rewind}_i\), \(\mathrm{advance}_i\), \(\mathrm{emit}_j\) are its control states.

For all \(c, C \in \mathbb {N}\), the unary box-enumeration machine \(\mathcal{P}_{c,C}\) (a finite binary-alphabet machine with \(c+1\) work tapes that runs \(c+1\) nested unary loops of side \(|x|+1\), emitting \(C\) ones per innermost iteration) computes the function \(x \mapsto 1^{C(|x|+1)^{c+1}}\) in time \(n \mapsto (C + 5(c+1) + 4)(n+1)^{c+1}\): on every input \(x\) it halts within \((C + 5(c+1) + 4)(|x|+1)^{c+1}\) steps with output exactly \(C(|x|+1)^{c+1}\) ones.

Let \(c\) be an effective machine-representation scheme: it assigns to every bit string \(\alpha \) a one-work-tape binary Turing machine \(M_\alpha \), and comes with a canonizer machine that, on every input \(\alpha \), outputs the canonical serialization of \(M_\alpha \) within \(T_c(|\alpha |)\) steps. Then for every bit string \(\alpha \), the canonical serialization of \(M_\alpha \) has length at most \(T_c(|\alpha |)\).

Let \(A\) and \(B\) be types and let \(f\) map every \(a \in A\) to a list \(f(a)\) over \(B\) of length at least \(1\). Then for every list \((a_1,\dots ,a_k)\) over \(A\), the concatenation \(f(a_1)\, f(a_2) \cdots f(a_k)\) has length at least \(k\).

For every \(n \in \mathbb {N}\) and every transition action of a one-work-tape binary Turing machine with state set \(\{ 0,\dots ,n\} \), the canonical serialization of the action (the two-bit input-head move, followed by the encodings of the work-tape write, the work-head move, the output emission and the successor state) has length at least \(1\).

Let \(M\) be a one-work-tape binary Turing machine in code normal form with state set \(\{ 0,\dots ,m\} \) and initial state \(q_0\), and let \(L\) be the length of its canonical serialization. Then the binary representation of \(m\) has length at most \(L\), \(q_0 \le L\), and \(m + 1 \le L\).

Let \(c\) be an effective machine-representation scheme: it assigns to every bit string \(\alpha \) a one-work-tape binary Turing machine \(M_\alpha \), and comes with a canonizer machine that, on every input \(\alpha \), outputs the canonical serialization of \(M_\alpha \) within \(T_c(|\alpha |)\) steps. For a bit string \(\alpha \), let \(L\) be the length of the canonical serialization of \(M_\alpha \), let \(\{ 0,\dots ,m\} \) be its state set and \(q_0\) its initial state, let \(\mathrm{bin}(m)\) be the binary representation of \(m\), and let \(B = 3L + 5(m+1) + 20\). Then

Let \(c\) be an effective machine-representation scheme: it assigns to every bit string \(\alpha \) a one-work-tape binary Turing machine \(M_\alpha \), and comes with a canonizer machine that, on every input \(\alpha \), outputs the canonical serialization of \(M_\alpha \) within \(T_c(|\alpha |)\) steps. For bit strings \(\alpha , x\) and \(t \in \mathbb {N}\) write \(S = (3|\alpha |+14\, T_c(|\alpha |)+50)(t+1)^2\) and \(z = \langle \langle \mathrm{bin}(t),\alpha \rangle ,x\rangle \) (self-delimiting pair encoding, little-endian binary \(\mathrm{bin}(t)\)). Let \(U\) be a finite binary Turing machine such that, for all \(\alpha , x, t\), whenever \(M_\alpha \) on \(x\) halts within \(t\) steps with output \(w\), \(U\) on \(z\) halts within \(S\) steps with output \(1w\), and whenever \(M_\alpha \) does not halt on \(x\) within \(t\) steps, \(U\) on \(z\) halts within \(S\) steps with output \(0\). Then for all \(\alpha , x, t\), \(U\) on \(z\) halts within \(S\) steps with output exactly \(A_c(\alpha ,x,t)\), which is \(1w\) if \(M_\alpha \) run on \(x\) for \(t\) steps has halted with output \(w\), and the single bit \(0\) otherwise.

Let \(c\) be a machine-representation scheme, which assigns to every bit string \(\alpha \) a one-work-tape binary Turing machine \(M_\alpha \) (decoding is total). For all bit strings \(\alpha , x\) and \(t \in \mathbb {N}\), let \(A_c(\alpha ,x,t)\) be \(1w\) if \(M_\alpha \) run on \(x\) for \(t\) steps has halted with output \(w\), and the single bit \(0\) otherwise. Then \(A_c(\alpha ,x,t) = 11\) if and only if \(M_\alpha \) on input \(x\) halts within \(t\) steps with output exactly the single bit \(1\).

Let \(c\) be an effective machine-representation scheme: it assigns to every bit string \(\alpha \) a one-work-tape binary Turing machine \(M_\alpha \), and comes with a canonizer machine that, on every input \(\alpha \), outputs the canonical serialization of \(M_\alpha \) within \(T_c(|\alpha |)\) steps, and suppose \(T_c\) is polynomially bounded: \(T_c(n) \le K(n+1)^k\) for all \(n\), for some constants \(K, k\). Then there exist \(A, d \in \mathbb {N}\) such that for all \(m, r, t \in \mathbb {N}\) with \(r \le m\) and \(t \le m\),

For all bit strings \(\alpha , x\) and all \(n, t \in \mathbb {N}\), each of \(|\alpha |\), \(|x|\), \(n\) and \(t\) is at most the length of the quadruple encoding \(\langle \alpha ,\langle x,\langle 1^n,1^t\rangle \rangle \rangle \), where \(\langle a,b\rangle \) is the self-delimiting pair encoding and \(1^k\) is the word of \(k\) ones.

For all bit strings \(y\) and \(w\) with \(|w| = |y| + 1\), the concatenation \(yw\) has odd length and \((|yw| - 1)/2 = |y|\).

Let \(c\) be a machine-representation scheme, which assigns to every bit string \(\alpha \) a one-work-tape binary Turing machine \(M_\alpha \) (decoding is total). For every bit string \(y\), \(y \in \mathrm{TMSAT}_c\) if and only if there is a bit string \(w\) with \(|w| = |y| + 1\) and \(yw \in V_c\). Here, with \(\langle \alpha ,\langle x,\langle 1^n,1^t\rangle \rangle \rangle \), where \(\langle a,b\rangle \) is the self-delimiting pair encoding and \(1^k\) is the word of \(k\) ones, \(\mathrm{TMSAT}_c\) is the set of strings \(\langle \alpha ,\langle x,\langle 1^n,1^t\rangle \rangle \rangle \), over all bit strings \(\alpha , x\) and \(n, t \in \mathbb {N}\), such that \(M_\alpha \) halts on \(\langle x,u\rangle \) within \(t\) steps with output exactly \(1\) for some \(u\) with \(|u| = n\), and \(V_c\) is the set of strings \(y'w'\) with \(|w'| = |y'|+1\) and \(y' = \langle \alpha ,\langle x,\langle 1^n,1^t\rangle \rangle \rangle \) for some \(\alpha , x, n, t\) such that \(M_\alpha \) halts on \(\langle x, w'_{[:n]}\rangle \) within \(t\) steps with output exactly \(1\), where \(w'_{[:n]}\) is the first \(n\) bits of \(w'\).

For every fixed bit string \(w\), the function sending a bit string \(x\) to the single bit that is \(1\) if \(x = w\) and \(0\) otherwise is polynomial-time computable.

Consider the fixed-width little-endian binary increment, which sends a bit string \(w\) to its successor among the words of length \(|w|\), or fails (overflow) when \(w\) consists only of ones, the empty word included. For every bit string \(w\), the increment of \(w\) is never the empty word.

For every bit string \(w\), the fixed-width little-endian binary increment of \(w\) (its successor among the words of length \(|w|\), or overflow when there is none) overflows if and only if \(w = 1^{|w|}\), that is, \(w\) consists only of ones.

The function sending a bit string \(x\) to the single bit that is \(1\) if \(x\) consists only of ones (that is, \(x = 1^{|x|}\), the empty word included) and \(0\) otherwise is polynomial-time computable.

Let \(x\) be a bit string, \(q\) an optional state in \(\{ 0,1,2,3\} \), \(i \le |x|\), \(m \in \mathbb {N}\), \(h \in \mathbb {Z}\) and \(o\) an output word. In the configuration of a one-work-tape binary machine with states \(\{ 0,1,2,3\} \) on input \(x\) that is in state \(q\), has its input head on input position \(i\) (counting from \(0\)), its work tape holding \(1^m\) in cells \(0,\dots ,m-1\), its work head at \(h\) and output \(o\), the scanned input symbol is \(x_i\) if \(i \lt |x|\) and the blank if \(i = |x|\).

Let \(x\) be a bit string, \(i, m \in \mathbb {N}\) with \(i + 2 \le |x|\), and \(b\) a bit with \(x_i = x_{i+1} = b\) (positions counted from \(0\)). Then running \(E\) for \(2\) steps from \(\Delta _x(0, i, m, m, \varepsilon )\) yields \(\Delta _x(0, i+2, m+1, m+1, \varepsilon )\); here \(E\) is the prefix-extraction machine (one work tape, states \(\{ 0,1,2,3\} \)) that counts the aligned data blocks \(00\) and \(11\) of a pair encoding \(\langle a,b\rangle \) in unary on its work tape and then copies bits of \(b\) to its output while moving its work head back along the counter, and \(\Delta _x(q,i,m,h,o)\) denotes the configuration of \(E\) on input \(x\) in state \(q\), with the input head on input position \(i\) (counting from \(0\)), the work tape holding \(1^m\) in cells \(0,\dots ,m-1\) and blanks elsewhere, the work head at \(h\), and output \(o\).

Let \(x\) be a bit string and \(i, m \in \mathbb {N}\) with \(i + 2 \le |x|\), \(x_i = 0\) and \(x_{i+1} = 1\) (positions counted from \(0\)). Then running \(E\) for \(2\) steps from \(\Delta _x(0, i, m, m, \varepsilon )\) yields \(\Delta _x(3, i+2, m, m-1, \varepsilon )\); here \(E\) is the prefix-extraction machine (one work tape, states \(\{ 0,1,2,3\} \)) that counts the aligned data blocks \(00\) and \(11\) of a pair encoding \(\langle a,b\rangle \) in unary on its work tape and then copies bits of \(b\) to its output while moving its work head back along the counter, and \(\Delta _x(q,i,m,h,o)\) denotes the configuration of \(E\) on input \(x\) in state \(q\), with the input head on input position \(i\) (counting from \(0\)), the work tape holding \(1^m\) in cells \(0,\dots ,m-1\) and blanks elsewhere, the work head at \(h\), and output \(o\).

Let \(a, b, p\) be bit strings, \(x = p\, \langle a,b\rangle \) with \(\langle a,b\rangle \) the self-delimiting pair encoding, and \(m \in \mathbb {N}\). Then running \(E\) for \(2|a| + 2\) steps from \(\Delta _x(0, |p|, m, m, \varepsilon )\) yields \(\Delta _x(3, |p| + 2|a| + 2, m + |a|, m + |a| - 1, \varepsilon )\); here \(E\) is the prefix-extraction machine (one work tape, states \(\{ 0,1,2,3\} \)) that counts the aligned data blocks \(00\) and \(11\) of a pair encoding \(\langle a,b\rangle \) in unary on its work tape and then copies bits of \(b\) to its output while moving its work head back along the counter, and \(\Delta _x(q,i,m,h,o)\) denotes the configuration of \(E\) on input \(x\) in state \(q\), with the input head on input position \(i\) (counting from \(0\)), the work tape holding \(1^m\) in cells \(0,\dots ,m-1\) and blanks elsewhere, the work head at \(h\), and output \(o\).

Let \(p\) and \(b\) be bit strings, \(x = pb\), \(m \in \mathbb {N}\), and \(j \le \min (m, |b|)\). Then running \(E\) for \(j\) steps from \(\Delta _x(3, |p|, m, m-1, \varepsilon )\) yields \(\Delta _x(3, |p| + j, m, m - j - 1, b_{[:j]})\), where \(b_{[:j]}\) is the first \(j\) bits of \(b\); here \(E\) is the prefix-extraction machine (one work tape, states \(\{ 0,1,2,3\} \)) that counts the aligned data blocks \(00\) and \(11\) of a pair encoding \(\langle a,b\rangle \) in unary on its work tape and then copies bits of \(b\) to its output while moving its work head back along the counter, and \(\Delta _x(q,i,m,h,o)\) denotes the configuration of \(E\) on input \(x\) in state \(q\), with the input head on input position \(i\) (counting from \(0\)), the work tape holding \(1^m\) in cells \(0,\dots ,m-1\) and blanks elsewhere, the work head at \(h\), and output \(o\).

For all bit strings \(a\) and \(b\), the prefix-extraction machine \(E\) (one work tape, four states; it counts the data blocks of a pair encoding in unary and then copies that many payload bits), started on the self-delimiting pair encoding \(\langle a,b\rangle \), halts within \(|\langle a,b\rangle | + 1\) steps with output exactly the first \(|a|\) bits of \(b\) (all of \(b\) if \(|b| \lt |a|\)).

If \(f\) and \(g\) are polynomial-time computable functions on bit strings, then so is the function sending \(x\) to the first \(|f(x)|\) bits of \(g(x)\) (all of \(g(x)\) when it is shorter).

Let \(z\) be a bit string that parses as a self-delimiting pair encoding, and let \(\pi _1(z)\) and \(\pi _2(z)\) be its decoded first and second components. Then \(z = \langle \pi _1(z), \pi _2(z)\rangle \).

For \(N \in \mathbb {N}\), consider the bounded search returning the least \(i \in \{ 0,\dots ,N\} \) with \(i + 1\cdot (i+1)^1 = N\), if there is one. If the search returns \(i\), then \(i + (i+1) = N\).

For all \(N, i \in \mathbb {N}\) with \(i + (i+1) = N\), the bounded search for the least \(j \in \{ 0,\dots ,N\} \) satisfying \(j + 1\cdot (j+1)^1 = N\) returns exactly \(i\).

For bit strings \(y\) and \(w\) with \(|w| = |y| + 1\), the odd split of \(yw\), namely the self-delimiting pair encoding of its first \(i\) bits and its remaining bits where \(|yw| = 2i + 1\), equals \(\langle y, w\rangle \).

Let \(z\) be a bit string such that \(s(z)\) parses as a pair encoding, where \(s(z)\) is the odd split of \(z\) (the self-delimiting pair encoding \(\langle z_{[:i]}, z_{[i:]}\rangle \) of the first \(i\) bits of \(z\) and the rest when \(|z| = 2i+1\), and the empty word when \(|z|\) is even), and \(\pi _1, \pi _2\) return the first and second components of a pair encoding (the empty word on strings that do not parse as pairs). Then \(z = \pi _1(s(z))\, \pi _2(s(z))\) and \(|\pi _2(s(z))| = |\pi _1(s(z))| + 1\).

For a bit string \(z\), write \(s(z)\) for its odd split (the self-delimiting pair encoding \(\langle z_{[:i]}, z_{[i:]}\rangle \) when \(|z| = 2i+1\), and the empty word when \(|z|\) is even), \(\pi _1, \pi _2\) for the two components of a pair encoding (the empty word when parsing fails), \(Y = \pi _1(s(z))\) and \(W = \pi _2(s(z))\); the code, input, width and clock fields of \(z\) are \(\pi _1(Y)\), \(\pi _1(\pi _2(Y))\), \(\pi _1(\pi _2(\pi _2(Y)))\) and \(\pi _2(\pi _2(\pi _2(Y)))\). The guard \(G(z)\) holds when \(s(z)\), \(Y\), \(\pi _2(Y)\) and \(\pi _2(\pi _2(Y))\) all parse as pair encodings and the width and clock fields consist only of ones. If \(G(z)\) holds, then \(z = YW\), \(|W| = |Y| + 1\), and \(Y = \langle \alpha , \langle x, \langle 1^n, 1^t\rangle \rangle \rangle \), where \(\alpha \) and \(x\) are the code and input fields, \(n\) and \(t\) are the lengths of the width and clock fields, and \(1^k\) is the word of \(k\) ones.

Let \(\alpha , x, w\) be bit strings and \(n, t \in \mathbb {N}\), let \(y = \langle \alpha ,\langle x,\langle 1^n,1^t\rangle \rangle \rangle \) (\(1^k\) the word of \(k\) ones), suppose \(|w| = |y| + 1\), and let \(z = yw\). Write \(s(z)\) for its odd split (the self-delimiting pair encoding \(\langle z_{[:i]}, z_{[i:]}\rangle \) when \(|z| = 2i+1\), and the empty word when \(|z|\) is even), \(\pi _1, \pi _2\) for the two components of a pair encoding (the empty word when parsing fails), \(Y = \pi _1(s(z))\) and \(W = \pi _2(s(z))\); the code, input, width and clock fields of \(z\) are \(\pi _1(Y)\), \(\pi _1(\pi _2(Y))\), \(\pi _1(\pi _2(\pi _2(Y)))\) and \(\pi _2(\pi _2(\pi _2(Y)))\). The guard \(G(z)\) holds when \(s(z)\), \(Y\), \(\pi _2(Y)\) and \(\pi _2(\pi _2(Y))\) all parse as pair encodings and the width and clock fields consist only of ones. Then \(G(z)\) holds, the code field of \(z\) is \(\alpha \), its input field is \(x\), its width and clock fields have lengths \(n\) and \(t\), and \(W = w\).

For a bit string \(z\), write \(s(z)\) for its odd split (the self-delimiting pair encoding \(\langle z_{[:i]}, z_{[i:]}\rangle \) when \(|z| = 2i+1\), and the empty word when \(|z|\) is even), \(\pi _1, \pi _2\) for the two components of a pair encoding (the empty word when parsing fails), \(Y = \pi _1(s(z))\) and \(W = \pi _2(s(z))\); the code, input, width and clock fields of \(z\) are \(\pi _1(Y)\), \(\pi _1(\pi _2(Y))\), \(\pi _1(\pi _2(\pi _2(Y)))\) and \(\pi _2(\pi _2(\pi _2(Y)))\). The guard \(G(z)\) holds when \(s(z)\), \(Y\), \(\pi _2(Y)\) and \(\pi _2(\pi _2(Y))\) all parse as pair encodings and the width and clock fields consist only of ones. Then the maps sending \(z\) to its code field, input field, width field, clock field and to \(W\), and the map sending \(z\) to the single bit \(G(z)\), are all polynomial-time computable.

For a bit string \(z\), write \(s(z)\) for its odd split (the self-delimiting pair encoding \(\langle z_{[:i]}, z_{[i:]}\rangle \) when \(|z| = 2i+1\), and the empty word when \(|z|\) is even), \(\pi _1, \pi _2\) for the two components of a pair encoding (the empty word when parsing fails), \(Y = \pi _1(s(z))\) and \(W = \pi _2(s(z))\); the code, input, width and clock fields of \(z\) are \(\pi _1(Y)\), \(\pi _1(\pi _2(Y))\), \(\pi _1(\pi _2(\pi _2(Y)))\) and \(\pi _2(\pi _2(\pi _2(Y)))\). The guard \(G(z)\) holds when \(s(z)\), \(Y\), \(\pi _2(Y)\) and \(\pi _2(\pi _2(Y))\) all parse as pair encodings and the width and clock fields consist only of ones, and the timed request of \(z\) is \(\langle \langle \mathrm{bin}(t), \alpha \rangle , \langle x, W_{[:n]}\rangle \rangle \) when \(G(z)\) holds, where \(\alpha \) and \(x\) are the code and input fields, \(n\) and \(t\) the lengths of the width and clock fields, \(W_{[:n]}\) the first \(n\) bits of \(W\), and \(\mathrm{bin}(t)\) the little-endian binary representation of \(t\); otherwise it is the fixed request \(\langle \langle \varepsilon ,\varepsilon \rangle ,\varepsilon \rangle \). The map sending \(z\) to its timed request is polynomial-time computable.

For a bit string \(z\), write \(s(z)\) for its odd split (the self-delimiting pair encoding \(\langle z_{[:i]}, z_{[i:]}\rangle \) when \(|z| = 2i+1\), and the empty word when \(|z|\) is even), \(\pi _1, \pi _2\) for the two components of a pair encoding (the empty word when parsing fails), \(Y = \pi _1(s(z))\) and \(W = \pi _2(s(z))\); the code, input, width and clock fields of \(z\) are \(\pi _1(Y)\), \(\pi _1(\pi _2(Y))\), \(\pi _1(\pi _2(\pi _2(Y)))\) and \(\pi _2(\pi _2(\pi _2(Y)))\). The guard \(G(z)\) holds when \(s(z)\), \(Y\), \(\pi _2(Y)\) and \(\pi _2(\pi _2(Y))\) all parse as pair encodings and the width and clock fields consist only of ones. If \(G(z)\) holds, then the code field and the clock field of \(z\) each have length at most \(|z|\).

Let \(c\) be a machine-representation scheme, which assigns to every bit string \(\alpha \) a one-work-tape binary Turing machine \(M_\alpha \) (decoding is total). For a bit string \(z\), write \(s(z)\) for its odd split (the self-delimiting pair encoding \(\langle z_{[:i]}, z_{[i:]}\rangle \) when \(|z| = 2i+1\), and the empty word when \(|z|\) is even), \(\pi _1, \pi _2\) for the two components of a pair encoding (the empty word when parsing fails), \(Y = \pi _1(s(z))\) and \(W = \pi _2(s(z))\); the code, input, width and clock fields of \(z\) are \(\pi _1(Y)\), \(\pi _1(\pi _2(Y))\), \(\pi _1(\pi _2(\pi _2(Y)))\) and \(\pi _2(\pi _2(\pi _2(Y)))\). The guard \(G(z)\) holds when \(s(z)\), \(Y\), \(\pi _2(Y)\) and \(\pi _2(\pi _2(Y))\) all parse as pair encodings and the width and clock fields consist only of ones, and the result for \(z\) is \(A_c(\alpha , \langle x, W_{[:n]}\rangle , t)\) when \(G(z)\) holds, with \(\alpha \), \(x\) the code and input fields, \(n\), \(t\) the lengths of the width and clock fields and \(W_{[:n]}\) the first \(n\) bits of \(W\), and \(A_c(\varepsilon ,\varepsilon ,0)\) otherwise; here \(A_c(\beta , v, t')\) is \(1w'\) if \(M_\beta \) run on \(v\) for \(t'\) steps has halted with output \(w'\), and the single bit \(0\) if it has not halted. Then for every bit string \(z\), the result for \(z\) equals \(11\) if and only if \(z \in V_c\), where \(V_c\) is the set of strings \(y'w'\) with \(|w'| = |y'| + 1\) for which there are bit strings \(\beta , v\) and \(n', t' \in \mathbb {N}\) with \(y' = \langle \beta ,\langle v,\langle 1^{n'},1^{t'}\rangle \rangle \rangle \) such that \(M_\beta \) halts on \(\langle v, w'_{[:n']}\rangle \) within \(t'\) steps with output exactly \(1\), \(w'_{[:n']}\) being the first \(n'\) bits of \(w'\).

For all \(K, B, e, C, c, n \in \mathbb {N}\),

For every fixed bit string \(w\), the constant function sending every bit string to \(w\) is polynomial-time computable.

For all \(C, c \in \mathbb {N}\), the function sending a bit string \(x\) to the little-endian binary representation of \(C(|x|+1)^c\) (the empty word when this value is \(0\)) is polynomial-time computable.

For bit strings \(\alpha , x, \beta , y\) and \(n, t, m, s \in \mathbb {N}\), if \(\langle \alpha ,\langle x,\langle 1^n,1^t\rangle \rangle \rangle = \langle \beta ,\langle y,\langle 1^m,1^s\rangle \rangle \rangle \), where \(\langle a,b\rangle \) is the self-delimiting pair encoding and \(1^k\) the word of \(k\) ones, then \(\alpha = \beta \), \(x = y\), \(n = m\) and \(t = s\).

Let \(c\) be a machine-representation scheme, which assigns to every bit string \(\alpha \) a one-work-tape binary Turing machine \(M_\alpha \) (decoding is total). Let \(L\) and \(V\) be languages of bit strings, \(C, e \in \mathbb {N}\), \(\alpha \) a bit string and \(T \colon \mathbb {N} \to \mathbb {N}\). Suppose that \(x \in L\) if and only if some \(u\) with \(|u| = C(|x|+1)^e\) satisfies \(xu \in V\), and that for all \(x, u\) with \(|u| = C(|x|+1)^e\), \(M_\alpha \) on input \(\langle x,u\rangle \) halts within \(T(|x|)\) steps with output the single bit \([xu \in V]\). Then for every bit string \(x\), \(x \in L\) if and only if \(\langle \alpha ,\langle x,\langle 1^{C(|x|+1)^e},1^{T(|x|)}\rangle \rangle \rangle \in \mathrm{TMSAT}_c\), where \(\langle a,b\rangle \) is the self-delimiting pair encoding, \(1^k\) the word of \(k\) ones, and \(\mathrm{TMSAT}_c\) the set of strings \(\langle \beta ,\langle y,\langle 1^n,1^t\rangle \rangle \rangle \) such that \(M_\beta \) halts on \(\langle y,v\rangle \) within \(t\) steps with output exactly \(1\) for some \(v\) with \(|v| = n\).

For all \(C, c \in \mathbb {N}\), the function sending a bit string \(x\) to the word \(1^{C(|x|+1)^c}\) consisting of \(C(|x|+1)^c\) ones is polynomial-time computable.