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

Give a direct proof that the set $\{x|\Phi_x(1) \downarrow\}$ (which is a set of program numbers that halt on input $1$) is not recursive.

I've got an idea that indirect proof must work. Assuming that the set is recursive and ... But I have no idea how to go on from here.

The course source is Computability, Complexity, and Languages, Second Edition: Fundamentals of Theoretical Computer Science by Davis. So I'm familiar with notation used there and understand it better, if possible.

share|cite|improve this question
Do you know any sets that are incomputable? – Quinn Culver May 11 '13 at 5:57
@QuinnCulver: What do you mean? Are you saying there is a relationship between this problem and the halting problem? – Gigili May 11 '13 at 6:04
Indeed, there is. – Quinn Culver May 11 '13 at 6:05
Welcome back +1 – Babak S. May 11 '13 at 7:54

Try reduce the problem to Halting problem ,
Halting problem: given M, Turing machine and input x,decide if M(x) halts .
so you want to find a computable functions that take instance of Halting problem and convert it to instance of this problem .

share|cite|improve this answer

The following is not a (completely) formal proof, the reason is that there are many different model for computation and I don't not which one to choose. Anyway I'm pretty much confident that the argument can be easily applied in every model you choose.

For start let's remind that your set is recursive if and only if the predicate $\Phi_x(1)\downarrow$ is decidable.

The key for the proof is that the function which send every $n \in \mathbb N$ in the number representing the function

$$f(x) = \Phi_n(n)$$

is total recursive.

So for every $x \in \mathbb N$ we have that $$\Phi_{f(x)}(1) \downarrow \iff f(x)(1) = \Phi_x(x) \downarrow$$ so the predicate $\Phi_{f(x)}(1)\downarrow$ is equivalent to the predicate $\Phi_x(x)\downarrow$. Because $f$ is total recursive the predicate $\Phi_{f(x)}(1)\downarrow$ is decidable too. But we proved that this predicate is equivalent to the predicate $\Phi_x(x)\downarrow$ and so it should be decidable too but we know that this cannot be because of the halting problem.

Hope this help, feel free to ask if something is not clear.

share|cite|improve this answer

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.