0
$\begingroup$

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?

$\endgroup$

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