4
$\begingroup$

Let $\phi(x,y)$ be an acceptable programming system (i.e., $\phi(x,y)$ is a partial recursive function such that, for every partial recursive function $f(x,y)$, there exists a recursive function $r(x)$ such that, for all $x$ and $y$, $\phi(r(x), y) = f(x,y)$). Is there an acceptable programming system $\psi$ such that, for all $x$, $\mathit{Range}(\phi_x)=\mathit{Domain}(\psi_x)$?. (Note that, for all functions $\alpha(x,y)$ and all $x$, $\alpha_x$ denotes the function $\lambda y.\alpha(x,y)$.)

$\endgroup$
3
  • 1
    $\begingroup$ Can you state exactly what it means to be acceptable? $\endgroup$ Dec 12, 2018 at 12:14
  • $\begingroup$ What's wrong with the $\lambda$-notation? Just use it directly. $\endgroup$ Dec 12, 2018 at 19:22
  • $\begingroup$ @JoelDavidHamkins: the way to remember the definition of "acceptable" is "it satisfies the u-t-m and s-m-n theorems". For the categorically minded, it's the reason for the effective topos being cartesian closed. $\endgroup$ Dec 12, 2018 at 19:25

1 Answer 1

3
$\begingroup$

The answer is positive.

For each $n$ we can find effectively an index $s(n)$ such that $Range(\phi_{s(n)})=Domain(\phi_n)$ and $s(n)>s(m)$ for all $m<n$. Then $Range(s)$ is computable, and we can define $$ \psi_x(y)=\begin{cases}\phi_{n}(y), & \mbox{if }x=s(n);\cr 0,& \mbox{if }x\notin Range(s)\ \& \ y\in Range(\phi_x);\cr \uparrow&\mbox{otherwise}. \end{cases} $$ Now $\phi_n=\psi_{s(n)}$ for all $n$, and $Range(\phi_x)=Domain(\psi_x)$ for all $x$.

$\endgroup$
4
  • $\begingroup$ What's the "$n$" in the definition of $\psi$? $\endgroup$
    – Salvo
    Dec 15, 2018 at 14:02
  • $\begingroup$ Ok, $s$ must be chosen injective by s-m-n theorem and padding lemma. Then $n=s^{-1}(x)$. $\endgroup$ Dec 15, 2018 at 15:20
  • $\begingroup$ Ok, nice answer! $\endgroup$
    – Salvo
    Dec 15, 2018 at 15:33
  • $\begingroup$ Thanks for the comment, I just made $s$ strictly increasing in the answer. $\endgroup$ Dec 15, 2018 at 15:37

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.