一个程序可以被证明是“正确”的吗?
不可以。可能会有一些非常小的微缩程序,在特殊条件下可以被证明是“正确”的——也就是,我们可以使用数学方法证明它们不可能给出不正确的结果。5但在现实世界的程序中,答案是否定的。起初,人们以为这只是一个组合数学问题。就是说,如果我们通过一个不太小的程序考虑所有路径组合,我们很快就可以得出结论,穷举测试任何软件都是一个不可能的任务。这与NP完全问题是类似的。但是,实际上,这种穷举测试比NP完全问题更糟糕。证明程序是正确的等价于解决停机问题。而从图灵的工作我们可以知道这是不可能的任务。
那么我们为什么要测试程序?正如我们只能得出结论,理论在我们的实验覆盖的领域中是适用和正确的,我们也只能说程序在我们进行测试的数据集上是正确的。而正如一个“否定实验”可以推翻一个理论,一个“失败的测试”可以指出一个先前被认为没有错误的软件存在缺陷。因此我们永远不能保证一个软件是“没有缺陷”的。我们所能做的是通过对其进行更大更密集数据集的测试来增加我们对它的信心。