I have a language that contains all encodings of the Turing machines that accept at least one word.

Is this language recursive, recursively enumerable, or neither?

  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Jun 7 '18 at 21:43
  • $\begingroup$ I guess encoding is the right word—will change. I'm pondering how to prove this—was thinking about a reduction from UTM, but couldn't think of one. So really, I'm just not sure how to go about a proof either way. $\endgroup$ – Tin Man Jun 7 '18 at 21:47
  • $\begingroup$ BTW, this is not a homework assignment. Rather, I'm studying for a test. $\endgroup$ – Tin Man Jun 7 '18 at 21:48
  • $\begingroup$ @D.W. I'm thinking now: perhaps Rice's theorem can prove this, as acceepting a word is in itself a non-trivial property. Am I right in that thinking? $\endgroup$ – Tin Man Jun 7 '18 at 22:05
  • $\begingroup$ As explained at the link in my comment, it doesn't really matter whether it's your homework assignment or not; the point is that you have provided us the text of an exercise-style question and are asking us to solve it for you, without any indication of progress or what specifically you're stuck on and without any specific question articulated about that exercise. Those kinds of questions tend not to be a good fit here. See the link I gave for a more detailed explanation and advice on how to make good use of this site for learning the material. Thanks for your understanding! $\endgroup$ – D.W. Jun 7 '18 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.