Acceptable Numberings, the s-m-n Theorem, and Recursion: Examples and Counterexamples

By [L1], there is a total specialization map $s_1^1$. Put $e_7:=s_1^1(e_{+},7)\mathrm{.}$ Then for every $v$, ${\phi }_{e_7}({\mathrm{Inp}}_1(v))\simeq {\phi }_{e_{+}}({\mathrm{Inp}}_2(7,v))=7+v\mathrm{.}$

So $e_7$ is an index for the unary residual program $v\mapsto 7+v$. This is exactly the interpretation recorded abstractly in Effective program specialization.

The map $t_{\alpha \to \beta }(e):=<mi\; mathvariant="normal">⌜</mi>0,e{<mi\; mathvariant="normal">⌝</mi>}_{\mathrm{s}\mathrm{e}\mathrm{q}}$ is total computable and satisfies ${\beta }_{t_{\alpha \to \beta }(e)}={\alpha }_e\mathrm{.}$ The decoder-projection $t_{\beta \to \alpha }(j):=\pi (j)$ is also total computable, and by definition of $\beta$ it satisfies ${\alpha }_{t_{\beta \to \alpha }(j)}={\beta }_j$ for every index $j$.

Thus these two numberings are explicitly compiled into each other. This is a concrete instance of [L1].

Let $F$ be the total computable transformer sending an index $e$ to the program that ignores its actual input and prints the numeral $e$. No filesystem or source-file query appears in the description of $F$.

By the fixed-point theorem discussed in [L1], there exists an index $q$ with ${\phi }_q={\phi }_{F(q)}$. Therefore running program $q$ makes it print its own index $q$, even though the construction used only numbering and effective transformation of indices.

This explicit quine is a counterexample to the statement.