-1
$\begingroup$

I'm stuck with this problem I have to solve.
Set $A = \{ x | \Phi_{x}(x): defined \}$
Set $B$ is produced from set $A$ by taking out all even numbers.
Is set $B$ r.e.? How does one prove that?

$\endgroup$
3
$\begingroup$

There are two useful ways to think about how a set $S$ is recursively enumerable.

  1. $S$ is recursively enumerable if there is an algorithm that lists its elements.
  2. $S$ is recursively enumerable if there is an algorithm which, given an element of $S$, halts and says “yes”, and which given some other value either halts and says “no” or runs forever. (In this case we say that the algorithm “semidecides” $S$.

Let's use just #1. We are given that $A$ is RE. Then there is an algorithm $M_A$ that lists the elements of $M$. We would like to use this to build an algorithm $M_B$ that lists only the elements of $B$. $M_B$ should contain a copy of $M_A$, examine the outputs of $M_A$, and for each one… ?

Now let's use #2. We are given that $A$ is RE. We are given an algorithm $M_A$ that semidecides $A$: given any element $a$ of $A$, it will halt and say “yes”, and given any other element it will either halt and say “no” or else run forever. We would like to use this to build an algorithm $M_B$ that semidecides $B$: given any element of $b$ of $B$ it must halt and say “yes”, and given anything else it must either halt and say “no” or else run forever. $M_B$ may contain a copy of $M_A$, and when $M_B$ gets some input $x$, it has the option to ask $M_A$ what it thinks of $x$; if $M_A$ halts, then $M_B$ can use $M_A$'s answer in choosing what to do. What should $M_B$ do in order to correctly semidecide whether $x$ is in $B$?

$\endgroup$
  • $\begingroup$ Thanks, but I need a formal proof. $\endgroup$ – mmierins Jun 11 '14 at 9:36
  • $\begingroup$ Then write one. $\endgroup$ – MJD Jun 11 '14 at 14:33
  • $\begingroup$ What I don't understand, why A is not recursive but it is recuresvily enumerable (you say, "we are given that A is RE"). Is it because we cannot say anything specific about the function Fx(x) in other words it is nontrivial and it follows by Rice's theorem? From what follows that it is recursively enumerable? $\endgroup$ – mmierins Jun 16 '14 at 13:33
  • $\begingroup$ Well, if $A$ were recursive, it would also be recursively enumerable, wouldn't it? And that is all we need here, because that is enough to show that $B$ is RE. $\endgroup$ – MJD Jun 16 '14 at 14:41
  • 1
    $\begingroup$ @davidgale But to answer your question, no, $A$ is not recursive. Because it is the set of all $x$ for which $\Phi_x(x)$ halts, and that is not a decidable property, because to find out of $\Phi_x(x)$ halts, you have to run it, and it might not halt, so you cannot be sure of giving a an answer. But it is a RE property, because you can run $\Phi_i(i)$ for each $i\le n$ for at most $n$ steps, and emit the numbers $i$ for which $\Phi_i(i)$ has halted.\, and if you can do this for all $n$ starting from 1, you will eventually emit the number $i$ for any $\Phi_i(i)$ that does halt. $\endgroup$ – MJD Jun 16 '14 at 14:42
1
$\begingroup$

So $B$ is all odd numbers in $A$, just start enumerating $A$, that is preforming the succesive calculations untill they converge and then jut take the odd numbers.

$\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.