Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Don'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
up vote 4 down vote accepted

You might find it easier to prove the stronger result that $B$ contains all of the natural numbers. (A sneaky question)

share|cite|improve this answer
How can you be sure that $B \leftrightarrow \mathbb{N}$? – MeadowMuffins Jan 12 '13 at 20:42
+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
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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