病毒逻辑-伪/ PoC

Question

我正在试着解决这个问题。希望有人能帮上忙。

假设我们有一个名为Confusion的程序；

Program confusion
if(Virus-Finder(Confusion) = false) then
   infect-executable
else
   halt
End program confusion

显然这是伪代码，所以不会运行。

对于任何程序P，我们可以运行Virus-Finder(P)，如果是病毒，则结果为True，如果不是，则结果为False。

infect-executable是一个模块，它扫描内存中的可执行程序，并在这些可执行程序中复制程序Confusion。

我们不知道Virus-Finder实际做了什么，只知道如果输入是病毒，它将返回True，如果不是，则返回False。

能否确定Virus-Finder能否正确判断Confusion是否是病毒？我最初的想法是不，它不可能。但我无法理解其中的逻辑。

Answer 1

您所说的内容定义不明确，但假设如下：

如果p执行infect-executable，则Virus-finder(p)返回true

在这种情况下，很容易证明Virus-finder(p)是不可判定的，并且您的伪代码确实可以做到这一点：

假设Virus-finder(p)是可判定的，因此它总是返回true (resp.false)如果执行p (分别为不执行) infect-executable。然后你的伪代码显示Virus-finder不能决定它是否是病毒。

正如Barmar提到的，这样的推理通常是证明某些问题的不可判断性的一种方法，特别是停顿问题(另一个众所周知的方法是简化为其他不可判定的问题)。