applecider - 11 months ago 23

Python Question

Let's say I have two python functions

`f`

`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:

`f`

`g`

`f`

`g`

Further, let's say no global variables are involved in

`f`

`g`

Is it possible to automatically determine (without human inspection) if python functions

`f`

`g`

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.)