1
$\begingroup$

I have a Turing machine M and I have to answer the question are there infinitely many Turing machines that recognize L(M)? I also need to describe a Turing machine that solves this problem. My idea is to say that we can simply increase the number of states by adding a new unreachable state. Each time I add a new state, it's still considered a new TM and because they're unreachable, I can say that they still accept the same language.

The only problem I'm having is describing a TM that can solve the problem. I was thinking that if I create a new TM (let's call it N) that represents M, I could say that N just needs to modify the transition function to create an unreachable state and once it does that it can add an infinite number of unreachable states which means there exists an infinite number of TM's. My problem is that I'm not sure if this is all I have to do to prove this and if it is then is my TM N enough to solve the problem or does it need to do more than just modify the transition function? N has to be decidable so it can't just keep adding states or else it will go on forever.

$\endgroup$
  • $\begingroup$ This is a trick question, as the answer below points out. I found this kind of questions to be fairly frequent in computability courses, so I'd suggest to somehow expect them. Sometimes the question is far easier than it looks, and the whole point of the exercise is to realize that. $\endgroup$ – chi Nov 23 '17 at 9:01
1
$\begingroup$

Given $L(M)$, there are countably infinite number of Turing machines that accept this language. You already describe in your post how to generate these machines. Thus the problem

are there infinitely many Turing machines that recognize L(M)

is decidable. The TM machine that decides it simply outputs $1$ (ACCEPTS) on any input $\langle M \rangle$.

Note that your TM $N$ does not need to construct all machines, it just needs to always response "YES" since for any $M$ indeed there exists infinite number of TMs accepting $L(M)$.

$\endgroup$
  • 1
    $\begingroup$ An important point that cannot be over-stressed: the TM doesn’t need to be able to compute or check the answer. It only needs to be able to assert it. $\endgroup$ – Stella Biderman Nov 23 '17 at 7:27

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.