If predicate P is partially-decidable, is ¬P decidable, partially decidable or undecidable?

Question

I was learning about decidability when I thought of this question: If P is partially decidable, is ¬P decidable, partially decidable or undecidable?

I think it is Undecidable since if ¬P holds then P doesn't hold, and the characteristic function of P is undefined when P doesn't hold so we can't come up with a characteristic function that results in 1 when ¬P holds.

However, I'm not sure if my answer and reasoning are correct. It'll be helpful if you can shed some light on this.

Answer 1

There is no definitive answer. If predicate $P$ is partially-decidable, $\neg P$ can be decidable, partially-decidable or undecidable.

• Let $P(n)$ be "is $n>1$?". $P$ is partially decidable. $\neg P(n)$ is "is $n\not\gt 1$?", which is decidable. (Note that a partially-decidable predicate such as $P$ can be decidable.)
• Let $P(n)$ be "is $n>1$?". $P$ is partially decidable. $\neg P(n)$ is "is $n\not\gt 1$?", which is partially-decidable. (Note that a decidable predicate is also partially-decidable.)
• Let $P(n)$ be "does the $n$-th Turing machine halt on blank tape?". $P$ is partially decidable. $\neg P(x)$ is "does the $n$-th Turing machine run forever on blank tape?", which is undecidable.

A predicate is called co-partially-decidable if its negation is partially-decidable.

To summarize, if predicate $P$ is partially-decidable, then $\lnot p$ is co-partially-decidable. A co-partially-decidable predicate can be decidable, partially-decidable, or undecidable. (If you think I am saying nothing, then you have understood the situation clearly.)

By the way, "partially-decidable" is also named "computably-enumerable (c.e.)", "recursively-enumerable (r.e.)", "semi-decidable", or "Turing-recognizable". You may add the prefix "co-" to each of them.