2
$\begingroup$

I have this exercise and I really don't know how to complete it:

Prove that for all finite sets S of Turing Machines it is decidable
whether or not given any two Turing Machines M1 and M2 in S they
recognize the same language, that is, L(M1)=L(M2)

I know that the problem of equivalence of languages is undecidable in general, but the additional hypothesis of the finiteness of the set S of machines does not suggest me any reason why this case should be different. Can somebody help me?

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Have you tried small cases, e.g., a set S of size 1? a set S of size 2? a set S of size 3? Trying easier special cases is often a good problem-solving strategy. In this case, that already is enough to understand the main ideas needed for this exercise. We want to help you with conceptual issues, but solving your particular exercise for you isn't likely to help you nor anyone else in the future. It's like learning to ride a bicycle: you can't learn to ride a bicycle by watching someone else do it. $\endgroup$ – D.W. Sep 1 '15 at 16:52
  • $\begingroup$ I can say that if |S| = 1 it follows that L(M)=L(M), but if |S|>1, couldn't there be infinite languages among those of the turing machines? How can I check that they are equal? This is mainly what gives me doubt $\endgroup$ – Giulia Frascaria Sep 2 '15 at 16:43
  • 1
    $\begingroup$ You do not have to check it, look at the collection of $2^{|S|^2}$ Turing machines, each corresponding to a different possibility. You can think of them as binary strings of length $|S|^2$ where the i'th entry is $1$ if the i'th pair of Turing machines in $S$ decide the same language. Clearly one of those $2^{|S|^2}$ decides the language your interested in, hence it is decidable. Like Yuval Filmus answered, imagine someone told you the answer for all the machines in $S$, hard code his answers to your machine (if $S$ would be infinite, you wouldn't be able to do that). $\endgroup$ – Ariel Sep 2 '15 at 20:59
3
$\begingroup$

Hint: Since $S$ is finite, there are finitely many legal queries, and we can hardcode the answers to all of them.

$\endgroup$
  • $\begingroup$ Could you please explain me what you mean by legal query? $\endgroup$ – Giulia Frascaria Sep 1 '15 at 17:44
  • 1
    $\begingroup$ I mean a query involving two Turing machines from $S$. $\endgroup$ – Yuval Filmus Sep 1 '15 at 17:45

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.