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

  • $\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.