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\}$.
Question Source : http://cs.stackexchange.com/questions/42261
0 comments:
Post a Comment
Let us know your responses and feedback