Two indexes $c$ and $b$, such that $Dom(\varphi_a)=\{b\}$ and $Dom(\varphi_b)=\{c\}$

61 Views Asked by At

Problem: Assume $\{\varphi_i\}_{i=1}^\infty$ is an effective enumeration of the computable functions. Find two indexes $c$ and $b$, such that $Dom(\varphi_c)=\{b\}$ and $Dom(\varphi_b)=\{c\}$.

Attempt: Denote $Dom(\varphi_d)$ by $D_d$. Define $f$ by $f(a,x)=42\iff x=a$ and $f$ is undefined otherwise. $f$ is partially recursive. Then $f=\varphi_e$ for some $e$. By the $S^1_1$ theorem $f(a,x)=\varphi_{S^1_1(e,a)}(x)$. Now define $g$ by $g(a)=S^1_1(e,a)$. Then for all $a$, $D_{g(a)}=\{a\}$. By the fixed-point theorem applied to $g$, exists and index $h$, such that $\varphi_h=\varphi_{g(h)}$. Now replace both $b$ and $c$ with $h$ and you get the desired result.

Question: My book is not a trickster book. If two different such indexes did not exist it would only ask to find an index $a$, such that $Dom(\varphi_a)=\{a\}$. How can I find two different such indexes?

1

There are 1 best solutions below

1
On BEST ANSWER

This sort of problem is easier for me to approach by the recursion theorem than by the fixed-point theorem. The recursion theorem says that for every partial computable function $F(x, i_1, \ldots, i_k)$ there is an index $e$ such that $$ \phi_e(i_1,\ldots, i_k) \simeq F(e,i_1,\ldots,i_k). $$ Also, let $s$ be the function such that, for all $x,i,y$, we have $$\phi_x(i,y) \simeq \phi_{s(x,i)}(y).$$ So $s$ is one of the functions from the s-m-n theorem.

To solve the question, define a partial computable function $F(x,i,y)$ that halts if and only if $y = s(x,1 \dot{-} i)$. By the recursion theorem, let $e$ be such that, for all $i$ and $y$, $$ \phi_e(i,y) = F(e,i,y) $$ Let $a = s(e,0)$ and $b = s(e,1)$. Then:

  • $\phi_a(y)$ halts if and only if $\phi_e(0,y)$ halts, if and only if $F(e,0,y)$ halts, if and only if $y = s(e,1)$, if and only if $y = b$.

  • $\phi_b(y)$ halts if and only if $\phi_e(1,y)$ halts, if and only if $F(e,1,y)$ halts, if and only if $y = s(e,0)$, if and only if $y = a$.

Thus $\operatorname{dom}\phi_a = \{b\}$ and $\operatorname{dom}\phi_b = \{a\}$.

This approach to this type of problem, using the recursion theorem and the s-m-n theorem together, and using the input $i$ as a kind of "flag" to document which function is desired (in this case, $a$ or $b$) can be applied very generally. For example, there is a computable sequence $\langle e(i) : i \in \omega\rangle$ such that, for all $i \in \omega$, we have $\operatorname{dom}\phi_{e(i)} = \{e(i+1)\}$. We simply take $F(x,i,y)$ to halt if $y = s(x,i+1)$ and apply the same method of proof.

There are also versions of this problem where we use the range instead of the domain. For example, there are indices $a$ and $b$ with $\phi_a(0) = b$ and $\phi_b(0) = a$. These versions can be proved using the same technique.