applecider applecider - 7 months ago 10
Python Question

Is it possible to know if two python functions are functionally equivalent?

Let's say I have two python functions

f
and
g
:

def f(x):
y = x**2 + 1
return y

def g(x):
a = x**2
b = a + 1
return b


These two functions are clearly functionally equivalent (both return
x**2 + 1
).

My definition of functionally equivalent is as follows:

If two functions
f
and
g
always produce the same output given the same input, then
f
and
g
are functionally equivalent.


Further, let's say no global variables are involved in
f
and
g
.

Is it possible to automatically determine (without human inspection) if python functions
f
and
g
are functionally equivalent?

Answer

By Rice's Theorem, no. If you could do this, you could solve the halting problem. (This is true even if f and g are always guaranteed to halt.)

Comments