证明不存在这样的算法
Prove no such algorithm exists
我正在研究算法并且遇到了这个练习：
'Prove that there is no program/algorithm that determines if a program P uses an uninitialized variable on a given input x.'
这是我得出的证明：
让我们假设有一个算法 Det 来确定程序 P 是否在给定的输入 x 上使用了未初始化的变量。
让程序成为
P(x)
如果 Det(P,x) 为真
没做什么
别的
变量我
打印我
这里我们看到一个矛盾。如果 Det(P,x) 为假，那么我们使用了一个未初始化的变量。我们没有在其他地方使用未初始化的变量，所以只要它 returns 为真，它就是错误的。
我不确定我的想法是否正确。
我觉得你说的差不多了，但是你要多说一点才能真正体现矛盾。
你的程序很完美，即'P(x): if Det(P,x) is true do nothing else variable i print i'。您还展示了 Det(P,x) 计算结果为假的情况，但您忘记提及如果 Det(P,x) 计算结果为真会发生什么（为了完整性需要这种情况）。例如：
假设 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) 选择使用未初始化的变量并且 returns 为真。目前正在努力寻找正确的解决方案（见评论）。
我正在研究算法并且遇到了这个练习：
'Prove that there is no program/algorithm that determines if a program P uses an uninitialized variable on a given input x.'
这是我得出的证明：
让我们假设有一个算法 Det 来确定程序 P 是否在给定的输入 x 上使用了未初始化的变量。
让程序成为
P(x) 如果 Det(P,x) 为真 没做什么 别的 变量我 打印我
这里我们看到一个矛盾。如果 Det(P,x) 为假，那么我们使用了一个未初始化的变量。我们没有在其他地方使用未初始化的变量，所以只要它 returns 为真，它就是错误的。
我不确定我的想法是否正确。
我觉得你说的差不多了，但是你要多说一点才能真正体现矛盾。
你的程序很完美，即'P(x): if Det(P,x) is true do nothing else variable i print i'。您还展示了 Det(P,x) 计算结果为假的情况，但您忘记提及如果 Det(P,x) 计算结果为真会发生什么（为了完整性需要这种情况）。例如：
假设 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) 选择使用未初始化的变量并且 returns 为真。目前正在努力寻找正确的解决方案（见评论）。