The set $B$ is the range of universal function given the domain $\mathsf{K}$, where $\mathsf{K} = \{ n | \varphi_n(n) \textit{ halts} \}$. How can we prove such claim?
Asked
Active
Viewed 80 times
2
-
1Don't use the title and the question box has one. Write the whole question in the question box. – Git Gud Jan 12 '13 at 18:11
-
Presumably you want to know whether $B$ is recursive relative to $K$, i.e. $B \leq_\mathrm{T} K$, not whether it is plain recursive. – Benedict Eastaugh Jan 12 '13 at 18:14
-
I would like to know how to prove $B$ is "plain" recursive. – MeadowMuffins Jan 12 '13 at 18:19
1 Answers
4
You might find it easier to prove the stronger result that $B$ contains all of the natural numbers. (A sneaky question)
Andreas Blass
- 71,833
-
-
+1 - this seems like the easiest method to me. And I will remember this question the next time I teach a computability course. – Carl Mummert Jan 12 '13 at 22:29
-
2@MeadowMuffins Let $k \in \omega$. Let $\Psi_k$ denote the constant function taking value $k$. $\Psi_k$ is clearly computable. Hence $\Psi_k = \varphi_n$ for some $n$. Since $\Psi_k$ is the constant function $\varphi_n(n) \downarrow$ so $n \in K$. Moreover, $\varphi_n(n) = \Psi_k(n) = k$. So $B = \omega$. – William Jan 12 '13 at 23:24