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)$.)
3
-
1$\begingroup$ Can you state exactly what it means to be acceptable? $\endgroup$– Joel David HamkinsCommented Dec 12, 2018 at 12:14
-
$\begingroup$ What's wrong with the $\lambda$-notation? Just use it directly. $\endgroup$– Andrej BauerCommented 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$– Andrej BauerCommented Dec 12, 2018 at 19:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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$.
-
$\begingroup$ What's the "$n$" in the definition of $\psi$? $\endgroup$– SalvoCommented 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$ Commented Dec 15, 2018 at 15:20
-
-
$\begingroup$ Thanks for the comment, I just made $s$ strictly increasing in the answer. $\endgroup$ Commented Dec 15, 2018 at 15:37