#### [SOLVED] Is finding the equivalence of two functions undecidable?

By unj2

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?

Edit: If the general case is undecidable, how much information do you need to have before you can correctly say that two functions are equivalent? #### @Stephen 2015-03-26 19:42:57

Note that the halting problem is decidable for linear bounded automata. Real computers are always bounded, and programs for them will always loop back to a previous configuration after sufficiently many steps. If you are using an unbounded (imaginary) computer to keep track of the configurations, you can detect that looping and take it into account. #### @Doug McClean 2009-10-06 08:47:23

It depends on what you mean by "function."

If the functions you are talking about are guaranteed to terminate -- for example, because they are written in a language in which all functions terminate -- and operate over finite domains, it's "easy" (although it might still take a very, very long time): two functions are equivalent if and only if they have the same value at every point in their shared domain.

This is called "extensional" equivalence to distinguish it from syntactic or "intensional" equivalence. Two functions are extensionally equivalent if they are intensionally equivalent, but the converse does not hold.

(All the other people above noting that it is undecidable in the general case are quite correct, of course, this is a fairly uncommon -- and usually uninteresting in practice -- special case.) #### @mercury0114 2016-08-23 17:12:06

So if we want to compare two `total` functions (those which halt on every input) and return yes if they match for every input, no otherwise. How to prove that this problem is undecidable (is it)? #### @Doug McClean 2016-08-24 16:54:31

If there are finitely many inputs in the domain, and both functions halt for all of them, and you have a decidable equality check for the codomain, then you just try both functions on all the inputs and compare the outputs. #### @Doug McClean 2016-08-26 17:40:32

Then it isn't decidable. #### @mercury0114 2016-08-28 04:49:26

Exactly, so how to prove that? Halt/not halt arguments used for non-total functions no longer work here as everything is guaranteed to halt. #### @Stephan202 2009-07-15 15:32:50

Given an arbitrary function, f, we define a function f' which returns 1 on input n if f halts on input n. Now, for some number x we define a function g which, on input n, returns 1 if n = x, and otherwise calls f'(n).

If functional equivalence were decidable, then deciding whether g is identical to f' decides whether f halts on input x. That would solve the Halting problem. Related to this discussion is Rice's theorem.

Conclusion: functional equivalence is undecidable.

There is some discussion going on below about the validity of this proof. So let me elaborate on what the proof does, and give some example code in Python.

1. The proof creates a function f' which on input n starts to compute f(n). When this computation finishes, f' returns 1. Thus, f'(n) = 1 iff f halts on input n, and f' doesn't halt on n iff f doesn't. Python:

``````def create_f_prime(f):
def f_prime(n):
f(n)
return 1
return f_prime
``````
2. Then we create a function g which takes n as input, and compares it to some value x. If n = x, then g(n) = g(x) = 1, else g(n) = f'(n). Python:

``````def create_g(f_prime, x):
def g(n):
return 1 if n == x else f_prime(n)
return g
``````
3. Now the trick is, that for all n != x we have that g(n) = f'(n). Furthermore, we know that g(x) = 1. So, if g = f', then f'(x) = 1 and hence f(x) halts. Likewise, if g != f' then necessarily f'(x) != 1, which means that f(x) does not halt. So, deciding whether g = f' is equivalent to deciding whether f halts on input x. Using a slightly different notation for the above two functions, we can summarise all this as follows:

``````def halts(f, x):
def f_prime(n): f(n); return 1
def g(n): return 1 if n == x else f_prime(n)
return equiv(f_prime, g) # If only equiv would actually exist...
``````

I'll also toss in an illustration of the proof in Haskell (GHC performs some loop detection, and I'm not really sure whether the use of `seq` is fool proof in this case, but anyway):

``````-- Tells whether two functions f and g are equivalent.
equiv :: (Integer -> Integer) -> (Integer -> Integer) -> Bool
equiv f g = undefined -- If only this could be implemented :)

-- Tells whether f halts on input x
halts :: (Integer -> Integer) -> Integer -> Bool
halts f x = equiv f' g
where
f' n = f n `seq` 1
g  n = if n == x then 1 else f' n
`````` #### @l0b0 2009-07-15 15:42:40

+1, but this begs another question: What is the minimum set of limitations necessary to make this decidable? Obviously, if the input set is defined to be sufficiently small, and a limit is introduced to the execution time, both functions could be brute forced. #### @nlucaroni 2009-07-15 15:44:01

"When is one thing equal to some other thing" -- www.math.harvard.edu/~mazur/preprints/when_is_one.pdf #### @BCS 2009-07-15 16:28:14

What can we show if we only ask if the two functions will /return/ different results? That is a function that never returns, never returns different results than anything. #### @chaos 2009-07-15 16:44:05

That isn't going to help. The 'return value problem' is still equivalent to the halting problem even if it's not halting we're asking about. And besides, you're begging the question of the halting problem by asking to exclude functions that do not halt. (Begging the question in the actual rhetorical meaning, not the way people misuse it conversationally as l0b0 demonstrates.) #### @BCS 2009-07-15 16:46:19

I think you are correct in your conclusion, but I don't think your argument is valid (or maybe I just don't understand it). A better argument would be: given function F and input N derive `G1(n) = (n != N) ? true : (F(n), true)` and `G2(n) = true`. Showing G1 == G2 for all n shows F halts for N #### @BCS 2009-07-15 16:56:00

@chaos, by excluding the halting case, I'm saying that any answerer is valid from the comparator function if either input doesn't halt. So it still doesn't need to answerer that. And I think the original form is "beggaring the question": guardian.co.uk/lifeandstyle/2001/sep/08/weekend.zoewilliams #### @chaos 2009-07-15 17:08:06

Think of it this way: because the halting problem is undecidable, you cannot find out if a program is going to halt other than by running it. Someone who's better at proving this stuff than I am could show you how that also means you can't find out what output a function is going to produce other than by running it, and for this comparison that means running it for all possible inputs, which is certainly possible for some functions and equally certainly not possible for all. #### @chaos 2009-07-15 17:08:46

I don't know what this "beggaring the question" madness is, but it's nothing to do with begging the question. Begging the question means using premises that assume a conclusion to a question that has not actually been resolved: en.wikipedia.org/wiki/Begging_the_question. i.e. someone doing this is "begging" to have another question taken as answered. Nothing to do with making a question "poorer". #### @BCS 2009-07-15 17:32:24

Just because you can't show that a function will halt doesn't imply that you can't show things of the form "If the function halts, it's output will be X" or by extension: "If both functions halt, they will return the same result". Note that nether of these make any claim as to if the function will halt or not and, importantly, the second doesn't even disclaim that one function halts and the other doesn't. -- My assertion is that the halting problem can't be directly used to argue about this problem unless you require correct result for non halting input functions. #### @BCS 2009-07-15 17:33:02

To me "making a question poorer" seems like a nice way say that the question "[uses] premises that assume a conclusion". But I'm not interested enough to argue the point further. #### @mercury0114 2016-02-24 20:52:48

This seems to be a correct proof about partial functions. What about total functions? Is the problem of determining whether a total function f1 is equivalent to a total function f2 undecidable? If yes, why? #### @MSN 2009-07-15 17:33:40

Is it impossible to know if two functions are equivalent?

No. It is possible to know that two functions are equivalent. If you have f(x), you know f(x) is equivalent to f(x).

If the question is "it is possible to determine if f(x) and g(x) are equivalent with f and g being any function and for all functions g and f", then the answer is no.

However, if the question is "can a compiler determine that if f(x) and g(x) are equivalent that they are equivalent?", then the answer is yes if they are equivalent in both output and side effects and order of side effects. In other words, if one is a transformation of the other that preserves behavior, then a compiler of sufficient complexity should be able to detect it. It also means that the compiler can transform a function f into a more optimal and equivalent function g given a particular definition of equivalent. It gets even more fun if f includes undefined behavior, because then g can also include undefined (but different) behavior! #### @BCS 2009-07-15 22:02:03

I think your 3rd assertion is false. I think that no general solution exists for even proving two function are equivalent because there are convincing arguments (see Stephan202's answer) that this can require solving the halting problem. #### @MSN 2009-07-15 23:59:45

I didn't say that, but stackoverflow ate my longer response. I constrained the problem to proving that two functions that are equivalent can be detected as equivalent. The COMDAT folding used by the MSVC linker does just that. #### @starblue 2009-07-15 17:18:42

The general case is undecidable by Rice's Theorem, as others have already said (Rice's Theorem essentially says that any nontrivial property of a Turing-complete formalism is undecidable).

There are special cases where equivalence is decidable, the best-known example is probably equivalence of finite state automata. If I remember correctly equivalence of pushdown automata is already undecidable by reduction to Post's Correspondence Problem.

To prove that two given functions are equivalent you would require as input a proof of the equivalence in some formalism, which you can then check for correctness. The essential parts of this proof are the loop invariants, as these cannot be derived automatically. #### @BCS 2009-07-15 16:31:47

I think if you allow side effects, you can show that the problem can be morphed into the Post correspondence problem so you can't, in general, show if two functions are even capable of having the same side effects. #### @chaos 2009-07-15 15:27:43

Yes, it is undecidable. This is a form of the halting problem.

Note that I mean that it's undecidable for the general case. Just as you can determine halting for sufficiently simple programs, you can determine equivalency for sufficiently simple functions, and it's not inconceivable that this could be of some use for an application. But you cannot make a general method for determining equivalency of any two possible functions. #### @HerdplattenToni 2009-07-15 15:25:44

In the general case it's undecidable whether two turing machines have always the same output for the identical input. Since you can't even decide whether a tm will halt on the input, I don't see how it should be possible to decide whether both halt AND output the same result... #### @BCS 2009-07-15 16:34:55

This isn't enough. It may well be possible to show that 2 functions will result in the same effect (including halting or not) without showing anything about what they do (giving answerers like "both will return the same result or not halt, but I don't know which") #### @amischiefr 2009-07-15 15:23:38

You could check in your compiler to see if they are "exactly" identical, sure, but determining if they return identical values would be difficult and time consuming. You would have to basically call that method and perform its routine over an infinite number of possible calls and compare the value with that from the other routine.

Even if you could do the above, you would have to account for what global values change within the function, what objects are destroyed / changed in the function that do not affect the outcome.

You can really only compare the compiled code. So compile the compiled code to refactor?

Imagine the run time on trying to compile the code with "that" compiler. You could spend a LOT of time on here answering questions saying: "busy compiling..." :) #### @BCS 2009-07-15 17:04:48

The only viable solutions would a glass box one that involves theorem provers and the like. A brute force solution would be easily thwarted by a pair of functions the don't halt for some case.

### [SOLVED] What does the exclamation mark do before the function?

• 2010-09-20 21:21:51
• Sebastian Otto
• 169779 View
• 1254 Score
• Tags:   javascript function

### [SOLVED] Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing

• 2010-08-16 10:26:58
• polygenelubricants
• 268952 View
• 1155 Score
• Tags:   algorithm math