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) ?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ What is "comp(p,x)"? $\endgroup$ – dkaeae May 15 '19 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 '19 at 8:04
Add a comment
|
$\begingroup$
$\endgroup$
4
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.)
answered May 15 '19 at 8:12
-
$\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 '19 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 '19 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 '19 at 8:34
-
$\begingroup$ Alternatively, you can keep your notations, but first define them. $\endgroup$ – Yuval Filmus May 15 '19 at 8:35
