Is finding the equivalence of two functions undecidable?

Question

Is it impossible to know if two functions are equivalent? For example, a compiler writer wants to determine if two functions that the developer has written perform the same operation, what methods can he use to figure that one out? Or can what can we do to find out that two TMs are identical? Is there a way to normalize the machines?

Answer 1

Rice's theorem tells us that non-trivial semantic properties of TMs are undecidable.

Take a property of a language that is non-trivial, i.e. it's exhibited by at least one computable language and not exhibited by at least one. One such property is, for example, "language contains 3 strings".

According to Rice, one cannot construct a TM which, given another TM's (say Y's) description as input, can decide if Y accepts exactly 3 strings.

Another semantic property would be "language is equal to language L computed by a machine M". If we had a TM that decides equality of two TMs languages, we would hardcode one of them to be M and we would get a violation of Rice's theorem.

Another approach to this is a reduction from the halting problem -to-> deciding if TMs language is empty -to-> deciding if two TMs have the same language. The last reduction is trivial, so try doing the first one.