1
$\begingroup$

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)}$.

$\endgroup$
3
  • $\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$ Mar 13, 2020 at 12:56
  • $\begingroup$ I suppose I am asking in what way your numbering differs from an admissible numbering. $\endgroup$ Mar 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$ Mar 14, 2020 at 0:06

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.