1
$\begingroup$

let's call a set $A \subseteq \mathbb{N}$ recursively enumerable if it's "partial characteristic function" $\tilde{\chi}_A$ is computable, whereby $\tilde{\chi}_A$ is defined as: $\tilde{\chi}_A$:= 1, if $x \in A$ and $\tilde{\chi}_A$ is undefined otherwise.

Now for $i = 0,1$ let $P_i$ be the set of all programmes p that terminate for input p and have output i. It's clear that $P_0 \cap P_1 = \emptyset$.
I'd be glad if you could help me with showing that the sets $P_0$ and $P_1$ are recursively enumerable, but that there's no decidable set E with $P_0 \subseteq E$, $P_1 \subseteq \mathbb{N}\backslash E$.

Looking forward to your suggestions!

$\endgroup$
1
$\begingroup$

The partial characteristic function of $P_0$ is computable by the algorithm: "On input $p$, run program $p$ with input $p$; if and when it terminates with output $0$, print $1$." $P_1$ is recursively enumerable similarly.

If they were separated by a decidable set $E$ as in the question, let $p$ be a program that outputs $1$ when $p\in E$ and outputs $0$ when $p\notin E$, i.e., $p$ computes the characteristic function of $E$. What would $p$ do when fed input $p$? It must eventually halt and output $0$ or $1$, since that's all $p$ ever does on any input. If it outputs $0$, then that means $p\in P_0\subseteq E$, so, by our choice of $p$, it should, on input $p$, compute $1$. Similarly, if $p$ on input $p$ outputs $1$, then $p\in P_1$, so $p\notin E$, and $p$ on input $p$ should output $0$. So we have a contradiction in either case. Therefore, no such program $p$ can exist.

$\endgroup$
  • $\begingroup$ Oh, I understand, it's so much easier than I thought! Thank you very much for the good explanation! $\endgroup$ – Studentu Dec 26 '18 at 21:12
  • $\begingroup$ "if and when it terminates with output 0, print 1". - You meant "print 0", right? and "therefore, no such program p can exist" implies that therefore such a decidable set E can't exist either? $\endgroup$ – Studentu Jan 6 at 14:07
  • 1
    $\begingroup$ @Studentu No, I meant what I wrote. If and when the computation of program $p$ on input $p$ terminates with output $0$, this shows that $p\in P_0$, and therefore the partial characteristic function of $P_0$ (as in the first paragraph of the question)is defined at $p$ and has value $1$ (not $0$) there. $\endgroup$ – Andreas Blass Jan 6 at 16:15
  • $\begingroup$ Yeah, this part I understood. This is the contradiction we want. But for simply considering a program $P_0$ in the beginning, you wrote The partial characteristic function of $P_0$ is computable by the algorithm: "On input p, run program p with input p; if and when it terminates with output 0, print 1." So why "print 1"? Did you just write this to emphasize that the partial characteristic function has output 1 and therefore $P_0$ is recursively enumerable? $\endgroup$ – Studentu Jan 6 at 16:42
  • 1
    $\begingroup$ @Studentu To prove that $P_0$ is recursively enumerable, using the definition in the first paragraph of the question, I must give a program that computes the partial characteristic function of $P_0$. That partial characteristic function has (still quoting the definition) value $1$, not $0$, wherever it is defined. So a program that computes it had better print $1$'s not $0$'s. $\endgroup$ – Andreas Blass Jan 6 at 16:48

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.