0

我正在研究算法,我遇到了这个练习:

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

这是我想出的证据:

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

让程序成为

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

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

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

4

1 回答 1

2

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

您的程序是完美的,即'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。目前正试图找到一个正确的解决方案(见评论)。

于 2016-04-01T02:24:19.447 回答