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.
$\begingroup$
$\endgroup$
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.
answered Mar 15 '16 at 16:39
hmakholm left over Monicahmakholm left over Monica
268k20 gold badges369 silver badges623 bronze badges
$\begingroup$
$\endgroup$
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$.
answered Mar 15 '16 at 16:43
print "yes"withhaltandprint "no"withloop forever. $\endgroup$ – hmakholm left over Monica Mar 15 '16 at 16:43