I was wondering why it is not possible. Is it because the corresponding language is not decidable, or because of the fact that it is not guaranteed that a Turing machine halts on every input?

  • $\begingroup$ It is perfectly possible. Take a Turing machine, and add an unreachable state. Both machines calculate the same function. $\endgroup$ – Yuval Filmus Sep 16 '19 at 18:53
  • $\begingroup$ Do you (a) have two particular Turing machines in mind, but you are not telling us which ones, or are you asking (b) given any two Turing machines that calculate the same function, why is it not possible to prove that they calculate the same function? $\endgroup$ – Andrej Bauer Sep 16 '19 at 20:03
  • $\begingroup$ Also, what makes you think this is not possible. Please provide a reference. Where did you see it claimed? $\endgroup$ – Andrej Bauer Sep 16 '19 at 20:03
  • 2
    $\begingroup$ You are misrepresenting the exam question. Please copy the exact wording (even if it is in Italian). $\endgroup$ – Andrej Bauer Sep 16 '19 at 20:29
  • 1
    $\begingroup$ Translation: "Why is it not possible to prove that two Turing machines calculate the same function? Demonstrate all the necessary assertions." I apologize, you did not mispreresent the question. The question is badly stated, it is confusing, and it should be ignored. $\endgroup$ – Andrej Bauer Sep 16 '19 at 20:52

Your exam question makes very little sense. The obvious reading would be this:

Let $M$ and $N$ be two Turing machines. Why is it not possible to prove that $M$ and $N$ compute the same function?

More precisely:

It is not the case that for all Turing machines $M$ and $N$ it is provable that $M$ and $N$ compute the same function.

Well, this is quite obvious: there exist two Turing machines that calculate different functions, say a Turing machine $M$ that computes the function $n \mapsto n + 1$, and a Turing machine $N$ that computes the function $n \mapsto 42 \cdot n$. Therefore, in general, $M$ and $N$ need not compute the same function, so in general we cannot prove that they do.

I am going to guess that whoever asked this question really wanted to ask:

Show that there is no decision procedure which decides, given any Turing machines $M$ and $N$, whether they compute the same function.

This is a standard exercise in computability theory, but is completely different from the question. One should not mix up things like "prove" and "decide".

I suggest that you go back to the author of the question and ask them to participate in this discussion. Then perhaps we can clear up the confusion, and save some students from unnecessary suffering.

Supplemental: A hint on how to show that such comparison is not decidable: given a Turing machine $T$, produce a new Turing machine $M$ which on input $n$ outputs $1$ if $T$ halts in fewer than $n$ steps, and $0$ otherwise. Compare $M$ to the machine which always output $0$.

| cite | improve this answer | |
  • $\begingroup$ Thanks for your help. I also thought that it could be more a decision problem. $\endgroup$ – Fabio Nardelli Sep 16 '19 at 21:09
  • $\begingroup$ So, if your last assumption is right (and I think it is) the answer is that it is not possible to show that M and N compute the same function because the relative problem/language is not decidable, thus I have to prove that it is not decidable, maybe through diagonalization, like for the halting problem. $\endgroup$ – Fabio Nardelli Sep 16 '19 at 21:18
  • $\begingroup$ It's easier to reduce to Halting problem. $\endgroup$ – Andrej Bauer Sep 17 '19 at 6:00
  • $\begingroup$ Thank you sir, could you give me an example of reduction, or suggest me a good read? I wasn't able to find any. $\endgroup$ – Fabio Nardelli Sep 17 '19 at 17:12

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.