Let P(p) <=> for each x, comp(p,x) is defined.
Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityLet P(p) <=> for each x, comp(p,x) is defined.
Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?
Show that your predicate is coRE-hard, that is, every coRE predicate reduces to it. If your predicate were RE, then it would follow that RE=coRE, which is known to be false.
The rest of the answer assumes that "comp(p,x) is defined" is the same as "program $p$ halts on input $x$".
In order to show that your predicate is coRE-hard, you need to show that for every coRE predicate $Q$ there is a computable function $f$ such that $Q(z)$ iff $P(f(z))$. A predicate $Q$ is coRE if there is a computable function $q$ such that $Q(z)$ iff for all $x$, $q(z,x)$. Hence we need
for all $x$, $q(z,x)$ iff for all $x$, $f(z)$ halts on $x$.
You take it from here.
(In fact, your predicate is $\Pi_2$-complete.)