How can I construct a Turing Machine that accepts the language L = <'M'> which is an encoding of a Turing Machine M?


closed as unclear what you're asking by Luke Mathieson, D.W., David Richerby, Juho, Rick Decker Dec 13 '14 at 19:18

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Is the question whether you can construct a TM that halts and accepts if you give it an encoded TM, and rejects otherwise, given that you have an agreed encoding scheme? Or is it given a string, can it decide whether the string could be interpreted as a TM? $\endgroup$ – Luke Mathieson Dec 13 '14 at 3:31
  • $\begingroup$ What have you tried? What are your thoughts? What self-study have you done? Do you know how to write a program in Python (or your favorite programming language) to do that? We expect you to make a significant effort before asking here, and to explain in the question what you've tried and what you're stuck on. $\endgroup$ – D.W. Dec 13 '14 at 5:57
  • $\begingroup$ It depends if you have any coding restrictions. If you have not (so any coding is acceptable) accept ∑*. $\endgroup$ – 3yakuya Dec 13 '14 at 13:15
  • $\begingroup$ @Byakuya Didn't I already say that? $\endgroup$ – David Richerby Dec 13 '14 at 13:51
  • $\begingroup$ Well, that's why I did not answer the question, just tried to point that it does depend if there are some encoding restrictions, which you did not write about. I upvoted your answer anyway, and I believe stack is a place where any suggestion towards the solution is fine. Am I wrong? $\endgroup$ – 3yakuya Dec 14 '14 at 15:12

Choose a coding of Turing machines such that every string is a valid coding. Then, your Turing machine just needs to accept $\Sigma^*$, which is trivial.


Not the answer you're looking for? Browse other questions tagged or ask your own question.