找到两个函数的等价性是不可判定的吗? [英] Is finding the equivalence of two functions undecidable?
问题描述
是否不可能知道两个函数是否等价?例如，编译器编写者想确定开发人员编写的两个函数是否执行相同的操作，他可以使用什么方法来解决这个问题?或者我们可以做些什么来发现两个 TM 是相同的?有没有办法使机器正常化?
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?
如果一般情况是不可判定的，你需要有多少信息才能正确地说两个函数是等价的?
If the general case is undecidable, how much information do you need to have before you can correctly say that two functions are equivalent?
推荐答案
给定一个任意函数 f，我们定义一个函数 f' 返回 1 在输入 n 上，如果 f 在输入 n 上停止.现在，对于某个数字 x，我们定义了一个函数 g，它在输入 n 时，如果 返回 1>n = x，否则调用 f'(n).
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).
如果功能等价是可判定的，那么决定 g 是否与 f' 相同就决定了 f 是否在输入 x<时停止/em>.这将解决停机问题.与此讨论相关的是 Rice 定理.
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.
结论:功能等效性是不可判定的.
下面有一些关于这个证明有效性的讨论.那么让我详细说明一下证明的作用，并给出一些 Python 中的示例代码.
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.
证明创建了一个函数 f'，它在输入 n 时开始计算 f(n).当这个计算完成时，f' 返回 1.因此，f'(n) = 1 iff f 在输入 n 上停止，并且 f' 不会停在 n 上，如果 f 不会.蟒蛇:
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
然后我们创建一个函数 g，它接受 n 作为输入，并将它与某个值 x 进行比较.如果n = x，则g(n) = g(x) = 1，否则g(n) = f'(n).蟒蛇:
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
现在的诀窍是，对于所有 n != x 我们都有 g(n) = f'(n).此外，我们知道 g(x) = 1.因此，如果 g = f'，则 f'(x) = 1 并且因此 f(x) 停止.同样，如果 g != f' 那么必然 f'(x) != 1，这意味着 f(x) 不会停止.因此，决定 g = f' 是否等同于决定 f 是否在输入 x 时停止.对上述两个函数使用稍微不同的符号，我们可以总结如下:
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...
我还将在 Haskell 中展示证明的插图(GHC 执行一些循环检测，我不确定在这种情况下使用 seq 是否是万无一失的，但是无论如何):
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
这篇关于找到两个函数的等价性是不可判定的吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
