2
$\begingroup$

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) ?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ What is "comp(p,x)"? $\endgroup$ – dkaeae May 15 at 7:31
  • $\begingroup$ Presumably, "comp(p,x) is defined" is the same as program $p$ halting on input $x$. Your predicate then states that $p$ is total, and is known to be $\Pi_2$-complete. $\endgroup$ – Yuval Filmus May 15 at 8:04
1
$\begingroup$

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.)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks. I was thinking about defining f(q,y) that returns the code of g. With g being g(x) = 0 if not T(q,y,x) and undefined otherwise. (T Kleene predicate). Then use that f $\endgroup$ – A. Othmane May 15 at 8:29
  • $\begingroup$ Nobody here can be assumed to know your notations, neither "comp" nor "T". Try to use "program $p$ halts on $x$", "program $p$ accepts $x$", and the like. $\endgroup$ – Yuval Filmus May 15 at 8:30
  • $\begingroup$ Duly noted. This is my second post as my first one was this exact question but in the wrong section $\endgroup$ – A. Othmane May 15 at 8:34
  • $\begingroup$ Alternatively, you can keep your notations, but first define them. $\endgroup$ – Yuval Filmus May 15 at 8:35

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.