-1

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?

Asaf Karagila
  • 393,674
mmierins
  • 139

2 Answers2

3

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

MJD
  • 65,394
  • 39
  • 298
  • 580
  • Thanks, but I need a formal proof. – mmierins Jun 11 '14 at 09:36
  • Then write one. – MJD Jun 11 '14 at 14:33
  • 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? – mmierins Jun 16 '14 at 13:33
  • 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. – MJD Jun 16 '14 at 14:41
  • 1
    @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. – MJD Jun 16 '14 at 14:42
  • Thanks for explanations. Do I get your pointers correctly (in your original answer) that if we have an algorithm Ma for deciding whether some number belongs to set A we can use that algorithm plus additionally check whether this number is odd and that way determine that it belongs to B? And since we have an algorithm - we can say that set B is r.e.? – mmierins Jun 17 '14 at 12:36
  • “An algorithm for deciding whether some number belongs to set $A$” would mean that $A$ is recursive, not that A was recursively enumerable. – MJD Jun 17 '14 at 12:38
  • OK. I meant "An algorithm for semideciding whether some number belongs to set A" – mmierins Jun 17 '14 at 12:45
  • Yes. One way to say this is that if $A$ is RE and $O$ is recursive then $A\cap O$ is RE. Because since $A$ is RE, we have a semidecider $M_A$ for $A$, and a decider $M_O$ for $O$, and if we use $M_O$ as a filter to filter the output of $M_A$, we get a semidecider $M_{A\cap O}$ for $A\cap O$. – MJD Jun 17 '14 at 13:03
  • O in this case is function that determines whether a given number is odd? Or I'm confusing something again? – mmierins Jun 17 '14 at 14:25
  • Let us continue this discussion in chat. – MJD Jun 17 '14 at 14:29
1

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.

Rene Schipperus
  • 39,526