比较可计算吗？

Question

考虑程序比较（P1，P2）其中：

Input: source code for procedures p1, and p2. 
Output: True if p1 and p2 always produce identical outputs; False otherwise 

是比较（P1，P2）可计算或不？为什么或者为什么不？

罐人解释这是什么意思？

Answer 1

这是不可计算的。

我不记得确切的原因，但它是关于一个特殊情况下，你compare本身compare本身，你可以用它来证明它是不可能写这样的功能。

Answer 2

一般情况下不是。确切的任务是确定p1和p2是否停止并产生相同的输出。因为如果p1和p2暂停（或甚至其中一个），它是不可计算的，所以比较也是不可计算的。然而，如果p1和p2被约束到所有可计算函数的集合的某个子集（例如没有递归的函数，即无循环），则比较即使在线性时间也是可计算的。