undecidable problem and its negation is undecidable - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T14:34:39Z https://cs.stackexchange.com/feeds/question/45826 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/45826 13 undecidable problem and its negation is undecidable Giulia Frascaria https://cs.stackexchange.com/users/37986 2015-09-03T18:14:45Z 2015-09-03T22:37:53Z <p>A lot of "famous" undecidable problems are nonetheless at least semidecidable, with their complement being undecidable. One example above all can be the halting problem and its complement.</p> <p>However, can anybody give me an example in which both a problem and its complement are undecidable and not semidecidable? I thought about the diagonalization language Ld, but it does not seem to me that the complement is undecidable.</p> <p>In that case, does that mean that a Turing Machine M can "lose" some strings that instead should be recognized, since they're part of the language we're trying to indentify?</p> https://cs.stackexchange.com/questions/45826/-/45828#45828 15 Answer by D.W. for undecidable problem and its negation is undecidable D.W. https://cs.stackexchange.com/users/755 2015-09-03T18:44:34Z 2015-09-03T18:44:34Z <p>Consider the following language:</p> <p>$$L_2 = \{(M_1,x_1,M_2,x_2) : \text{M_1 halts on input x_1 and M_2 doesn't halt on input x_2}\}.$$</p> <p>$L_2$ is undecidable and not semi-decidable, and same is true of its complement. Why? The intuition is "$M_2$ doesn't halt on input $x_2$" isn't semi-decidable, so $L_2$ is not semi-decidable; and when you look at the complement of $L_2$, the same thing happens for $M_1$. This can be formalized more carefully using reductions.</p> <p>More generally, if $L$ is a language that is undecidable and not semi-decidable, then</p> <p>$$L' = \{(x,y) : x \in L, y \notin L\}$$</p> <p>meets your requirements: $L'$ is undecidable and not semi-decidable, and the same is true of the complement of $L'$.</p> https://cs.stackexchange.com/questions/45826/-/45829#45829 7 Answer by David Richerby for undecidable problem and its negation is undecidable David Richerby https://cs.stackexchange.com/users/9550 2015-09-03T19:13:32Z 2015-09-03T19:13:32Z <p>Note that the overwhelming majority of problems fit the criterion you're looking for: both the problem and its complement are not semi-decidable. This is because there are only countably many semi-decidable problems but there are uncountably many problems.</p> <p>For an example, let $H$ be the halting problem for Turing machines and let $\cal{M}$ be the class of Turing machines with an oracle for&nbsp;$H$. Let $H_2$ be the halting problem for&nbsp;$\cal{M}$. I claim that neither $H_2$ nor&nbsp;$\overline{H_2}$ is semi-decidable</p> <p>We can show that $H_2$ is not decided by any machine in&nbsp;$\cal{M}$: the argument is the same as the argument that the ordinary Turing machine halting problem&nbsp;$H$ is not decided by any ordinary Turing machine. Now, suppose for contradiction that $H_2$&nbsp;is semi-decided by some ordinary Turing machine&nbsp;$T$. Well, with an oracle for&nbsp;$H$, we can test whether $T$&nbsp;halts for any particular input, contradicting the fact that no machine in&nbsp;$\cal{M}$ decides&nbsp;$H_2$. So $H_2$&nbsp;is not semi-decidable.</p> <p>It remains to show that $\overline{H_2}$ is not semi-decidable. First, note that it is semi-decided by a machine in&nbsp;$\cal{M}$: again, the argument is the same as $H$&nbsp;being semi-decided by an ordinary Turing machine. $\overline{H_2}$&nbsp;cannot be semi-decided by some machine in&nbsp;$\cal{M}$ because, if it was, $H_2$ and&nbsp;$\overline{H_2}$ would both be semi-decided by machines in&nbsp;$\cal{M}$, so both languages would be decided by machines in&nbsp;$\cal{M}$. But we already know that $H_2$&nbsp;is not decided by any machine in&nbsp;$\cal{M}$. Therefore, $\overline{H_2}$&nbsp;is not semi-decided by any machine in&nbsp;$\cal{M}$. Further, $\overline{H_2}$ is not semi-decided by any ordinary Turing machine, since $\cal{M}$&nbsp;contains every ordinary Turing machine. (An ordinary Turing machine is a Turing machine with an oracle for&nbsp;$H$ that never uses that oracle.)</p> https://cs.stackexchange.com/questions/45826/-/45834#45834 7 Answer by Yuval Filmus for undecidable problem and its negation is undecidable Yuval Filmus https://cs.stackexchange.com/users/683 2015-09-03T22:37:53Z 2015-09-03T22:37:53Z <p>Here are some natural examples:</p> <ul> <li><p>The language of all Turing machines halting on <em>all</em> inputs, sometimes denoted TOT. This language is $\Pi_2^0$-complete.</p></li> <li><p>The language of all Turing machines halting on <em>infinitely many</em> inputs, sometimes denoted INF. This language is also $\Pi_2^0$-complete.</p></li> <li><p>The language of all Turing machines halting on <em>arbitrarily long</em> inputs, sometimes denoted COF. This language is $\Sigma_3^0$-complete.</p></li> </ul> <p>$\Pi_2^0$ and $\Sigma_3^0$ are levels of the <a href="https://en.wikipedia.org/wiki/Arithmetical_hierarchy">arithmetical hierarchy</a>. The completeness results imply, in particular, that these languages are neither semidecidable nor co-semidecidable.</p>