我正在研究算法,我遇到了这个练习:
“证明没有程序/算法可以确定程序 P 是否在给定的输入 x 上使用未初始化的变量。”
这是我想出的证据:
让我们假设有一个算法 Det 来确定程序 P 是否在给定输入 x 上使用未初始化的变量。
让程序成为
P(x) 如果 Det(P,x) 为真,则不执行任何其他操作变量 i 打印 i
在这里,我们看到了一个矛盾。如果 Det(P,x) 为假,那么我们使用了未初始化的变量。我们没有在其他地方使用未初始化的变量,所以只要它返回 true,它就是错误的。
我不确定我的想法是否正确。