比較可計算嗎？

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被約束到所有可計算函數的集合的某個子集（例如沒有遞歸的函數，即無循環），則比較即使在線性時間也是可計算的。