algorithm - 证明不存在这样的算法

Question

我正在研究算法，我遇到了这个练习：

“证明没有程序/算法可以确定程序 P 是否在给定的输入 x 上使用未初始化的变量。”

这是我想出的证据：

让我们假设有一个算法 Det 来确定程序 P 是否在给定输入 x 上使用未初始化的变量。

让程序成为

P(x) 如果 Det(P,x) 为真，则不执行任何其他操作变量 i 打印 i

在这里，我们看到了一个矛盾。如果 Det(P,x) 为假，那么我们使用了未初始化的变量。我们没有在其他地方使用未初始化的变量，所以只要它返回 true，它就是错误的。

我不确定我的想法是否正确。

Answer 1

我想你差不多了，但你必须多说一点才能真正表现出矛盾。

您的程序是完美的，即'P(x)：如果 Det(P,x) 为真，则不执行任何其他变量 i print i'。您还展示了 Det(P,x) 计算结果为 false 的情况，但您忘记提及如果 Det(P,x) 计算结果为 true 会发生什么（这种情况是完整性所必需的）。例如：

假设 Det(P,x) 为真。然后，Det 已确定 P(x) 使用带有输入 x 的未初始化变量。但这是不可能的，因为 P 声明如果 Det(P,x) 为真，那么我们不使用未初始化的变量。

现在假设 Det(P,x) 为假。然后，Det 确定 P(x) 没有使用未初始化的变量。但这是不可能的，因为 P 声明如果 Det(P,x) 为真，那么我们使用未初始化的变量 i。

因此，评估 Det(P,x) 总是会导致矛盾，这意味着它不存在。

编辑：这个证明是不正确的！观察 Det(P,x) 可以检查 P，如果 Det(P,x) 看到对自身的调用，则 Det(P,x) 选择使用未初始化的变量并返回 true。目前正试图找到一个正确的解决方案（见评论）。