0

Why is this? I'm not necessarily interested in a full proof, but just a quick, simple explanation that makes sense as to why this is.

yuopiop
  • 37
  • 1
    Which definitions of "recursive" and (in particular) "recursively enumerable" do you have to work from? – hmakholm left over Monica Mar 15 '16 at 16:36
  • I'm using the following definitions: Recursive - algorithm decides if an input is in a set in a finite amount of time. Recursively enumerable - algorithm halts if element is in the set and does not if it isn't. – yuopiop Mar 15 '16 at 16:39
  • x @Ellen: With those (nice and sensible) definitions: If you have an algorithm that shows your set is recursive, you can make it into an algorithm that shows that the set is r.e. by replacing print "yes" with halt and print "no" with loop forever. – hmakholm left over Monica Mar 15 '16 at 16:43

2 Answers2

1

Intuitively, a set is recursive if there's a program that will take a number as input and then answer "yes" if the number is in the set and "no" if it isn't.

Similarly, a set is recursively enumerable if there's a program that will take a number as input and then answer "yes" if the number is in the set and either answer "no" or keep running forever if it isn't.

If you know that a set is recursive, thanks to some program, the very same program will also work for showing that it is recursively enumerable.

hmakholm left over Monica
  • 286,031
0

Say $S$ is a recursive set of natural numbers. Given $n$, you have an algorithm to decide whether $n\in S$. So construct a list of the elements of $S$ like so: If $1\in S$ then add $1$ to the list, otherwise don't. If $2\in S$ add $2$ to the list, otherwise don't. Etc. You have enumerated the elements of $S$.

David C. Ullrich
  • 89,985