1
$\begingroup$

Consider a Gödelian numbering of partial recursive functions. Consider the set of indexes corresponding to some function $\phi$. It may be seen that this set is not recursively enumerable. Does this set contain a recursively enumerable non-recursive subset?

$\endgroup$
1
$\begingroup$

I guess the answer is yes, but please check critically. One can easily construct an infinite recursive set of indices of $\phi$ (adding "comments" to a program). From this infinite recursive set one can pick out a non recursively enumerable subset.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes - this is basically the padding lemma (not to be confused with the padding argument). $\endgroup$ – Noah Schweber Dec 23 '19 at 11:33

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.