Hopefully this question is not a duplicate.

How do I show the problem below is decidable by describing a Turing machine?

Input: Turing machine M

Question: Are there infinitely many Turing machines that all recognize L(M)?

I know a language is decidable if there exists a Turing machine that halts on all inputs when running on that language, where it accepts if a string is in the language and rejects otherwise.

Now I know that a Turing machine can simulate the behavior of another turing machine, so in theory a turing machine, say T, CAN simulate the behavior of M, therefore accepting the language of M.

Wouldn't it then be possible if I argue that there can exist an infinite amount of turing machines that all simulate the behaviour of M, and as a result accept L(M)?

Or is what I'm proposing not doing its job of showing the problem is decidable?


marked as duplicate by Yuval Filmus, chi, David Richerby, Evil, fade2black Nov 24 '17 at 21:13

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ In fact, this is an exact duplicate. Are you taking the same class? $\endgroup$ – Yuval Filmus Nov 24 '17 at 12:29
  • $\begingroup$ Oh never mind, I see it's a duplicate now. And looking at the question I think we are in the same class yes. $\endgroup$ – Iamlegend1996 Nov 27 '17 at 19:49