3
$\begingroup$

I want to show this problem is decidable by describing a TM that answers the question.
I originally thought this was quite simple, and that the answer would just be a TM that outputs "yes" for any valid input of a TM M. My reasoning was that given any TM M, we can just add a new unreachable state to it and the new machine M' will still recognize the same language as M.
However, a Turing machine can only have a finite set of states so now I'm unsure if this reasoning is correct in order to produce infinitely many Turing machines and I'm unsure where to go from here.

Any help would be much appreciated.

|cite|improve this question
$\endgroup$
  • $\begingroup$ If unreachable states are an issue; you can simply build $M_1, M_2, M_3, ...$ in which each $M_i$ is equal to $M$ but, at the beginning of the computation, simply performs $i$ steps to the right and $i$ steps to the left without modifying the tape (adding $2i$ more states to $M$) before entering the starting state of $M$. Clearly for all $i$, $L(M_i) = L(M)$. $\endgroup$ – Vor Nov 20 '17 at 10:22
  • $\begingroup$ Here's another fun proof that's totally nonconstructive. Determining whether a Turing machine recognizes a given language is undecidable, regardless of the language (consequence of Rice's theorem). Therefore, for any $M$ there must be an infinite number of TMs that recognize the same language as $M$, since otherwise you could decide whether a TM recognizes the same language as $M$ by just checking the TM against a finite list. $\endgroup$ – Aaron Rotenberg Jan 24 '18 at 16:55
4
$\begingroup$

Your attempt is fine. Yes, a Turing machine can only have a finite number of states, but you can add $i$ unreachable states for any natural number $i$ and there are infinitely many natural numbers, even though each one of them is finite.

|cite|improve this answer
$\endgroup$

Your Answer

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

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