1
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.