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

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.

## 1 Answer

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.