Mathematics – Is it unknovable?

def create_f_prime(f):
 def f_prime (n):
 f(n)
 return 1
 return f_prime

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

-- Tells whether two functions f and g are equivalent.
equiv :: (Integer -> Integer) -> (Integer -> Integer) -> Bool
equiv fg = undefined - If only this could be implemented :)
 
-- Tells whether f halts on input x
halts :: (Integer -> Integer) -> Integer -> Bool
halts fx = equiv f'g
 where
 f'n = fn `seq` 1
 gn = if n == x then 1 else f'n

Don’t you know whether the two functions Is it the same? For example, a compiler writer wants to determine whether two functions written by a developer perform the same operation. What methods can he use to calculate that function? Or what can we do to find out that two TMs are the same? Is there a way to regulate the machine?

Edit: If the general situation is undecidable, how much information do you need before you can correctly say that the two functions are equivalent?

Given an arbitrary function f, we define a function f’, if f stops on input n, it will return 1 on input n. Now , For a certain number x, we define a function g, if n = x, then return 1 on the input n, otherwise call f'(n).

If the function is equivalent Determined, then determine whether g is the same as f’and determine whether f stops on input x. This will solve the Halting problem. Related to this discussion is Rice’s theorem.

Conclusion: Functional equivalence is not possible Decided.

About the validity of this proof, there are some discussions below. Let me explain in detail the role of the proof and give some sample codes in Python.

>Proof creation A function f’that starts calculating f(n) on input n. When this calculation ends, f’returns 1. Therefore, if ff stops on input n, then f'(n) = 1, if f does not f, then f’does not stop on n. Python:

def create_f_prime(f):
 def f_prime(n):
 f(n) 
 return 1
 return f_prime

> Then we create a function g that takes n as input and compares it with some value x. If n = x, then g(n)= g(x)= 1, otherwise 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

>The trick now is, for all n! = x, we have g(n) = f'(n). Also, we know that g(x) = 1. Therefore, if g = f’, then f'(x) = 1, so f(x) stops .Similarly, if g! = f’then must be f'(x)! = 1, which means that f(x) will not stop. Therefore, judging whether g = f’is equivalent to determining whether f stops on input x. Using slightly different notations for the above two functions, we can summarize it 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 will also explain the proof in Haskell (GHC performs some loop detection, I’m not sure if the use of seq in this case is foolproof, but anyway):

-- Tells whether two functions f and g are equivalent.
equiv :: (Integer -> Integer) -> (Integer -> Integer) -> Bool
equiv fg = undefined - If only this could be implemented :)
 
-- Tells whether f halts on input x
halts :: (Integer -> Integer) -> Integer -> Bool
halts fx = equiv f'g
 where
 f'n = fn `seq` 1
 gn = if n == x then 1 else f'n