Acceptable Numberings, the s-m-n Theorem, and Recursion

This family is a numbering of the partial computable unary functions. If $f$ is partial computable, some deterministic one-tape Turing machine computes it. Relabel that machine's finite state set and tape alphabet by integers so that the start, accept, and reject states become $0,1,2$ and the symbols become the normalized alphabets of [L3]. The resulting coded machine has some code $e$, and by construction ${\phi }_e=f$.

The numbering is universal. On input $(e,x)$, first run the total decoder from [L2]. If $e$ is malformed, diverge forever. If $e$ decodes to a machine $M_e$, simulate $M_e$ on input $x$ and output exactly what $M_e$ outputs if it halts. This produces a partial computable binary function $U(e,x)$ with $U(e,x)\simeq {\phi }_e(x)$.

For hard-wiring, given $e$ and $a$, first run the total decoder [L2]. If $e$ is malformed, construct a fixed machine $N_{e,a}$ that diverges on every input. Otherwise construct a coded machine $N_{e,a}$ that on input $x$ first computes the pair code $<mi\; mathvariant="normal">⌜</mi>a,x{<mi\; mathvariant="normal">⌝</mi>}_{\mathrm{s}\mathrm{e}\mathrm{q}}$, then simulates the machine coded by $e$ on that code, and copies out the simulated output if the simulation halts. By [L2] and [L3], this case-defined map $(e,a)\mapsto <mi\; mathvariant="normal">⌜</mi>N_{e,a}<mi\; mathvariant="normal">⌝</mi>$ is total and computable.

By construction, for every $x$ one has ${\phi }_{<mi\; mathvariant="normal">⌜</mi>N_{e,a}<mi\; mathvariant="normal">⌝</mi>}(x)\simeq {\phi }_e(<mi\; mathvariant="normal">⌜</mi>a,x{<mi\; mathvariant="normal">⌝</mi>}_{\mathrm{s}\mathrm{e}\mathrm{q}})\mathrm{.}$ So the function $s(e,a):=<mi\; mathvariant="normal">⌜</mi>N_{e,a}<mi\; mathvariant="normal">⌝</mi>$ is the required hard-wiring operation from [L1].

Steps 1.1, 1.2, and 2.1 show that $({\phi }_e)$ is a numbering, is universal, and has the required hard-wiring map. Therefore the fixed machine coding gives an acceptable numbering.

Define the functions $s_m^n$ recursively from the binary map of [L1]: $s_0^n(e):=e,$ and $s_{m+1}^n(e,a_1,\dots ,a_{m+1}):=s(s_m^{n+1}(e,a_1,\dots ,a_m),a_{m+1})\mathrm{.}$ Because $s$ is total computable and composition preserves total computability, each $s_m^n$ is total computable.

We prove the defining identity from [L2] by induction on $m$. For $m=0$, step 1.1 gives $s_0^n(e)=e$, so the statement is immediate. Assume it holds for $m$. Then for every input tuple $b_1,\dots ,b_n$, ${\phi }_{s_{m+1}^n(e,a_1,\dots ,a_{m+1})}({\mathrm{Inp}}_n(b_1,\dots ,b_n))$ $\simeq {\phi }_{s_m^{n+1}(e,a_1,\dots ,a_m)}(<mi\; mathvariant="normal">⌜</mi>a_{m+1},{\mathrm{Inp}}_n(b_1,\dots ,b_n){<mi\; mathvariant="normal">⌝</mi>}_{\mathrm{s}\mathrm{e}\mathrm{q}})$ by [L1]. By the definition in [L2], that inner code is exactly ${\mathrm{Inp}}_{n+1}(a_{m+1},b_1,\dots ,b_n)\mathrm{.}$ The induction hypothesis therefore turns the right-hand side into ${\phi }_e({\mathrm{Inp}}_{m+n+1}(a_1,\dots ,a_m,a_{m+1},b_1,\dots ,b_n))\mathrm{.}$ So the required identity also holds for $m+1$.

Therefore for every $m,n$ the recursively defined $s_m^n$ is a parameter-specialization function.

Apply [L1] to the chosen pair $(m,n)$. The number $e^{\mathrm{\prime }}:=s_m^n(e,a_1,\dots ,a_m)$ is effectively computable from the data.

By the defining property of $s_m^n$, the indexed function ${\phi }_{e^{\mathrm{\prime }}}$ agrees on every remaining input tuple with the original program ${\phi }_e$ after the first $m$ inputs have been fixed to $a_1,\dots ,a_m$. Thus $e^{\mathrm{\prime }}$ is the desired residual-program index.

Therefore program specialization is effective.

Let $s_1^1$ be the specialization map from [L1]. Define $d(u):=s_1^1(u,u)\mathrm{.}$ Because $s_1^1$ is total computable, so is $d$.

By the defining property of $s_1^1$, for every $u$ and $x$ one has ${\phi }_{d(u)}(x)={\phi }_{s_1^1(u,u)}(x)\simeq {\phi }_u(<mi\; mathvariant="normal">⌜</mi>u,x{<mi\; mathvariant="normal">⌝</mi>}_{\mathrm{s}\mathrm{e}\mathrm{q}})\mathrm{.}$ That is exactly the required diagonal identity.

Therefore the desired total computable self-reference constructor exists.

Let $d$ be the diagonal map from [L2]. Because $F$ is total computable by [L1], the binary partial function $\mathrm{\Psi }(z,x):={\phi }_{F(d(z))}(x)$ is partial computable. Since we are working inside a numbering of all partial computable functions, choose an index $q$ with ${\phi }_q(<mi\; mathvariant="normal">⌜</mi>z,x{<mi\; mathvariant="normal">⌝</mi>}_{\mathrm{s}\mathrm{e}\mathrm{q}})\simeq \mathrm{\Psi }(z,x)$ for all $z,x$.

Set $e:=d(q)$. Then for every input $x$, ${\phi }_e(x)\simeq {\phi }_q(<mi\; mathvariant="normal">⌜</mi>q,x{<mi\; mathvariant="normal">⌝</mi>}_{\mathrm{s}\mathrm{e}\mathrm{q}})\simeq \mathrm{\Psi }(q,x)={\phi }_{F(d(q))}(x)={\phi }_{F(e)}(x),$ where the first equivalence is [L2] and the last equality is the definition of $e$. Hence ${\phi }_e={\phi }_{F(e)}$.

Therefore every computable program transformer has a fixed point.

Let $s_2^1$ be the specialization function from [L1]. Define a ternary partial computable function by $\mathrm{\Psi }(a,u,x):={\phi }_{F(a,s_2^1(u,a,u))}(x)\mathrm{.}$ Because $F$ and $s_2^1$ are total computable, $\mathrm{\Psi }$ is partial computable, so choose an index $r$ with ${\phi }_r(<mi\; mathvariant="normal">⌜</mi>a,<mi\; mathvariant="normal">⌜</mi>u,x{<mi\; mathvariant="normal">⌝</mi>}_{\mathrm{s}\mathrm{e}\mathrm{q}}{<mi\; mathvariant="normal">⌝</mi>}_{\mathrm{s}\mathrm{e}\mathrm{q}})\simeq \mathrm{\Psi }(a,u,x)$ for all $a,u,x$.

Define $q(a):=s_2^1(r,a,r)\mathrm{.}$ This function is total computable because $s_2^1$ is.

For every $a$ and $x$, ${\phi }_{q(a)}(x)\simeq {\phi }_r(<mi\; mathvariant="normal">⌜</mi>a,<mi\; mathvariant="normal">⌜</mi>r,x{<mi\; mathvariant="normal">⌝</mi>}_{\mathrm{s}\mathrm{e}\mathrm{q}}{<mi\; mathvariant="normal">⌝</mi>}_{\mathrm{s}\mathrm{e}\mathrm{q}})=\mathrm{\Psi }(a,r,x)={\phi }_{F(a,s_2^1(r,a,r))}(x)={\phi }_{F(a,q(a))}(x)\mathrm{.}$ Hence ${\phi }_{q(a)}={\phi }_{F(a,q(a))}$ for every parameter $a$.

Therefore the fixed-point construction can be carried out uniformly in the external parameter.

The set $K$ is computably enumerable: dovetail over all indices $e$, decode each one using [L3], and simulate the decoded machine on input $e$. Enumerate $e$ exactly when that simulation halts. By [L2], this lists precisely the numbers in $K$.

For each $e$, build a coded machine $Q_e$ that on input $x$ simulates the enumeration of $W_e$ and halts exactly when the number $x$ appears in that enumeration. Let $p(e):=<mi\; mathvariant="normal">⌜</mi>Q_e<mi\; mathvariant="normal">⌝</mi>$. The effective machine coding makes $p$ total computable; productivity in [L1] does not require this particular witness to be injective.

Assume $W_e\subseteq \mathbb{N}\setminus K$. If $p(e)\in W_e$, then by the definition of $Q_e$ the computation $Q_e(p(e))$ halts, so $p(e)\in K$, which contradicts $W_e\subseteq \mathbb{N}\setminus K$. Therefore $p(e)\mathrm{\notin }{W}_e$. But then the simulation inside $Q_e$ never sees $p(e)$ enter $W_e$, so $Q_e(p(e))$ diverges and hence $p(e)\mathrm{\notin }K$. Thus $p(e)\in (\mathbb{N}\setminus K)\setminus W_e$.

Step 2.1 shows that $p$ is a productive function for $\mathbb{N}\setminus K$. By [L1], the complement of $K$ is productive. Together with step 1.1, [L1] gives that $K$ is creative.

Every c.e. set one-one reduces to $K$. If $C=W_e$, let $m_e(x)$ be the code of a machine that ignores its actual input, enumerates $W_e$, and halts exactly when $x$ appears. Add to its finite description an unreachable chain of states whose length encodes $x$. This does not change its behaviour, and the fixed injective machine coding makes $x\mapsto m_e(x)$ total computable and one-one. Thus $x\in C⟺m_e(x)\in K\mathrm{.}$

Let $C$ be creative, put $P=\mathbb{N}\setminus C$, and choose a normalized total one-one productive function $p$ from [L1]. The fixed coding supplies a total computable padding map $\mathrm{pad}(e,y)$: it builds a machine simulating program $e$ and adds an unreachable state chain encoding the pair $(e,y)$. Hence ${\phi }_{\mathrm{pad}(e,y)}={\phi }_e$, and $\mathrm{pad}$ is one-one in the pair. Apply [L3] to the transformer that, from $(y,e)$, returns an index whose domain is $\{p(\mathrm{pad}(e,y))\}$ if program $y$ halts on $y$, and is empty otherwise. We obtain a total computable $q$ satisfying this fixed-point equation. Put $n(y):=\mathrm{pad}(q(y),y),g(y):=p(n(y))\mathrm{.}$ Then $n$, and therefore $g$, is one-one, and padding gives $W_{n(y)}=W_{q(y)}=\{\begin{array}{ll}\{g(y)\},& y\in K,\\ \mathrm{\varnothing },& y\mathrm{\notin }K\mathrm{.}\end{array}$ If $y\in K$ and $g(y)\in P$, productivity applied to $W_{n(y)}\subseteq P$ would force $g(y)\mathrm{\notin }{W}_{n(y)}$, a contradiction. If $y\mathrm{\notin }K$, then $W_{n(y)}=\mathrm{\varnothing }\subseteq P$, so productivity gives $g(y)\in P$. Therefore $y\in K⟺g(y)\in C,$ and $g$ is a one-one computable reduction $K{\le }_{1}C$.

Applying step 1.1 to $A$ and then step 1.2 to $B$ gives a one-one reduction $A{\le }_{1}B$ by composition. Reversing the roles of $A$ and $B$ gives $B{\le }_{1}A$.

Let $f$ witness $A{\le }_{1}B$ and let $g$ witness $B{\le }_{1}A$. Build finite membership-preserving partial bijections $h_s$ by stages. At a domain stage, choose the least $x\mathrm{\notin }\mathrm{dom}{h}_s$ and start with $y_0=f(x)$. While $y_i\in \mathrm{rng}{h}_s$, set $x_{i+1}=h_s^{-1}(y_i)$ and $y_{i+1}=f(x_{i+1})$. This search must leave the finite range: otherwise a repeated $y_i$ and injectivity of $f$ would eventually put the original unused $x$ in $\mathrm{dom}{h}_s$. Pair $x$ with the first unused $y_i$. Each passage through $f$ and $h_s^{-1}$ preserves and reflects membership, so the new pair does too.

At the alternating range stage, choose the least $y\mathrm{\notin }\mathrm{rng}{h}_s$ and start with $x_0=g(y)$. While $x_i\in \mathrm{dom}{h}_s$, set $y_{i+1}=h_s(x_i)$ and $x_{i+1}=g(y_{i+1})$. The symmetric injectivity argument finds an unused $x_i$ after finitely many steps. Pair that $x_i$ with $y$; again all traversed maps preserve and reflect membership. Thus every stage effectively extends the finite membership-preserving partial bijection.

Let $h:={\bigcup }_s{h}_s$. The alternating least-unused choices put every natural number eventually into both its domain and range, so $h$ is a bijection. It is computable because, on input $x$, one simulates stages until $x$ is paired. Every stage preserves $x\in A⟺h(x)\in B$, hence this equivalence holds for all $x$.

So $h$ is a computable permutation sending $A$ onto $B$. Taking $B=K$ and using [L2] gives the final clause.

By [L1], let $({\phi }_e)$ denote the standard acceptable numbering coming from the fixed machine coding. Because $\alpha$ is universal by [L2], the partial function $(e,x)\mapsto {\phi }_e(x)$ has some $\alpha$-index $u$. Because $\alpha$ is acceptable, [L2] supplies a total computable hard-wiring map $s_{\alpha }$, and then $t_{\phi \to \alpha }(e):=s_{\alpha }(u,e)$ satisfies ${\alpha }_{t_{\phi \to \alpha }(e)}(x)\simeq {\alpha }_u(<mi\; mathvariant="normal">⌜</mi>e,x{<mi\; mathvariant="normal">⌝</mi>}_{\mathrm{s}\mathrm{e}\mathrm{q}})={\phi }_e(x)\mathrm{.}$ So $\phi$ translates computably into $\alpha$. The same argument gives a computable translator $t_{\phi \to \beta }$ from $\phi$ into $\beta$.

Because $\phi$ is universal and $\alpha$ is acceptable, the same argument with the roles reversed gives a total computable translator $t_{\alpha \to \phi }$ with ${\phi }_{t_{\alpha \to \phi }(e)}={\alpha }_e\mathrm{.}$ Likewise there is $t_{\beta \to \phi }$ with ${\phi }_{t_{\beta \to \phi }(e)}={\beta }_e\mathrm{.}$

Compose the translators through the hub numbering $\phi$: $t_{\alpha \to \beta }:=t_{\phi \to \beta }\circ t_{\alpha \to \phi },t_{\beta \to \alpha }:=t_{\phi \to \alpha }\circ t_{\beta \to \phi }\mathrm{.}$ Then ${\beta }_{t_{\alpha \to \beta }(e)}={\phi }_{t_{\alpha \to \phi }(e)}={\alpha }_e,$ and similarly ${\alpha }_{t_{\beta \to \alpha }(e)}={\beta }_e$.

Therefore any two acceptable numberings are computably intertranslatable.

Consider the total computable transformer $F$ that sends an index $e$ to a program which ignores its actual input and simply outputs the numeral $e$. This transformer manipulates indices only; it does not read any source file.

By [L1], there exists $q$ with ${\phi }_q={\phi }_{F(q)}\mathrm{.}$ But ${\phi }_{F(q)}$ is precisely the constant program that outputs $q$, so ${\phi }_q$ does the same. Thus a quine-style fixed point exists without any inspection of a literal source file.

Therefore the statement is false. The recursion theorem needs numbering, specialization, and computable index transformation, not filesystem access.

Consider the total computable transformer $F(e):=e+1.$ It changes only the numerical index and is therefore a computable program transformer.

By [L1], there exists an index $e$ with ${\phi }_e={\phi }_{F(e)}={\phi }_{e+1}\mathrm{.}$ Since $e\mathrm{\ne }e+1$, the same partial computable function has at least two distinct indices.

Therefore the statement is false: a partial computable function can have many distinct indices.