Does every Turing Recognizable language has a subset which is not turing recognizable? i can give some examples but can't prove in general

  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Mar 25 '16 at 12:03

No, finite languages don't have subsets which aren't Turing recognizable. However, infinite languages (Turing recognizable or not) always have subsets which are not Turing recognizable, simply because they have uncountably many subsets, but there are only countably many Turing recognizable languages.

  • $\begingroup$ thanks . and for the infinite ones is this not Turing recognizable subset infinite? $\endgroup$ – mindal Mar 25 '16 at 9:53
  • $\begingroup$ Definitely – all finite languages are Turing recognizable. $\endgroup$ – Yuval Filmus Mar 25 '16 at 9:53

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.