Let $\phi$ be a programming system satisfying the UTM Theorem (i.e., $\phi$ is a $2$-ary partial recursive function such that the list $\phi_0,\phi_1,\ldots$ includes all $1$-ary partial recursive functions, where $\phi_i=\lambda x.\phi(i,x)$ for all $i\in\mathbb{N}$). Suppose that for all recursive functions $f$ with finite range, there exits an $n\in\mathbb{N}$ such that $\phi_n=\phi_{f(n)}$. If $g$ is any recursive function (with finite or infinite range), is there an $n\in\mathbb{N}$ such that $\phi_n=\phi_{g(n)}$.
-
$\begingroup$ Do I understand correctly that your effective programming system satisfies the u-t-m theorem (by definition), but you did not require that it satisfy the s-m-n theorem? $\endgroup$– Andrej BauerMar 13, 2020 at 12:56
-
$\begingroup$ I suppose I am asking in what way your numbering differs from an admissible numbering. $\endgroup$– Andrej BauerMar 13, 2020 at 14:43
-
$\begingroup$ I'd guess you could build a counterexample using a variation of the Friedberg numbering construction. Let $g(n)=n+1$, and mostly make the $\phi_i$ distinct, but occasionally choose a large $i$ and small $j$ and have $\phi_i$ repeat $\phi_j$ to defeat a given $f$. $\endgroup$– Dan TuretskyMar 14, 2020 at 0:06
1 Answer
Expanding on my comment above. There is a Friedberg listing of the partial recursive functions, i.e. a 2-ary p.r. function $\phi$ such that $\phi_i = \lambda x.\phi(i,x)$ lists every p.r. function without repetition. We may assume that $\phi_0$ is the empty function.
Now we'll define a new list $\psi$ with $\psi_{2i} = \phi_i$ for all $i$. We also promise that for each $2i+1$, there will be a $j < 2i+1$ with $\psi_{2i+1} = \psi_{j}$. By induction, we may assume that $j$ is even. Now let $g$ be any total computable function such that $g(n)$ is always an even number strictly greater than $n$. Then $g$ has no fixed points in this system. (Because a fixed point of $g$ would give us $j < i$ with $\phi_j = \phi_i$.)
It remains only to define $\psi_{2i+1}$. If $i = \langle e, k\rangle$, where this is the standard pairing function, then we let $\psi_{2i+1}$ be the empty function until $\phi_e(2i+1)\!\downarrow = j < 2i+1$. Once this occurs, we make $\psi_{2i+1}$ copy $\psi_j$. Then $2i+1$ is a fixed point of $\phi_e$.
If $f = \phi_e$ is total and has a bounded range, then for a sufficiently large $k$, $f(2\langle e,k\rangle+1) < 2\langle e, k\rangle+1$, so $f$ will have a fixed point.