Why is it true that the relation R and its negation are not semi decidable?

Problem Detail: 

An example given for a relation R where its negation and itself are not semi-decidable was:

$R(x,y)$ holds iff $y = 0$ then $R_{HALT}(x)$ holds, otherwise $y = 1$ and $R_{HALT}(x)$ does not hold.

It's stated with the assumption that the proof is trivial (which for most it probably is), but I am struggling to see why it is the case. Can anyone run me through why it is true?

Asked By : Jeff

Answered By : David Richerby

If the relation $R$ was semi-decidable, then the halting problem would be decidable: if you want to know whether program $x$ terminates, just enumerate the elements of $R$ until you find either $(x,0)$ or $(x,1)$. In the first case, output "$x$ halts"; in the second, "$x$ does not halt." One of these is guaranteed to happen, so you have a decider for the halting problem, contradicting the undecidability of that problem.

The argument for the complement of $R$ is nearly identical: observe that $\overline{R} = \{(x,1-y)\mid (x,y)\in R\}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42261

3200 people like this

 Download Related Notes/Documents