I have a professor who is really poor at explaining the material, which is what makes answering his questions very hard. Here is the question:

Recursive language with non-recursive subsets. Does one exist?

I'm sure it is a very simple and easy answer but I can't figure it out. Don't give me the answer just point me in the right direction and I'm sure I'll figure it out.


Hint. Take a very big recursive language over any alphabet you like. Verrrry big. Something so big it has all kinds of subsets.

  • $\begingroup$ Looks like I need more than a hint. I think it is possible to have a non-recursive subset, but I can't come up with an example. Can you help out more? $\endgroup$
    – flashburn
    Nov 10 '13 at 1:28
  • $\begingroup$ Your intuition is correct. What's the biggest recursive langauge you can think of? $\endgroup$ Nov 10 '13 at 1:42
  • $\begingroup$ In our class we blazed through the topic so fast and in such general terms that I think nobody understood what the professor was talking about. So the only recursive language I can think of is the set of natural numbers. $\endgroup$
    – flashburn
    Nov 10 '13 at 1:46
  • $\begingroup$ I think I got it. I can take any recursive language L. An empty set is part a subset of L. Empty set is non recursive. $\endgroup$
    – flashburn
    Nov 10 '13 at 2:22
  • 3
    $\begingroup$ The empty set is recursive: it's accepted by the Turing machine that always says "no". But, as you say, the set of natural numbers is recursive. Can you think of a non-recursive subset of them? $\endgroup$ Nov 10 '13 at 9:09

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.