正确性 (计算机科学) 在理论计算机科学中算法的正确性英语correctness是指一个算法在程序规范下被认定为正确的判定其中功能正确英语functional correctness针对输入输出的行为例如对每一个输入算法都能给出预期的输出 人们将正确性分为两类一类被称为部分正确性英语partial correctness它要求在算法返回结果时这一结果是正确的另一类被称为完全正确性英语total correctness它在部分正确性的基础之上还要求算法必须能够结束由于对于停机问题没有通用的解决方案因此判定完全正确性的断言有着更多需要深层次研究的地方终止的证明是指一类数学证明因为完全正确性需要证明一个算法会终止所以它在程序的形式验证中起着至关重要的作用 例如考虑这样一个问题依次搜索整数列   来看是否存在某个特定现象比如说存在一个奇数为完全数对于这个问题而言我们很容易写出一个部分正确的程序直接对于每个数字做长除法判定其是否完全然而如果我们想证明这个程序是完全正确的那就相当于我们在断言一个在数论里目前还未知的结论 在算法和程序规范都是基于形式化来给出时对正确性的证明应当为一个数学证明然而我们并不期待能够给出特定机器上实现的特定程序的正确性断言因为那样将需要考虑诸如内存限制在内的更多问题 证明论中有一个结论柯里霍华德同构这一结论认为任意一个在构造性逻辑下的功能正确性的证明都对应了一个λ演算程序这种转换证明的方式被称为程序抽出英文program extraction 霍尔逻辑是一个具体的能够严密验证程序正确性的形式系统它用一系列的公理来定义程序语言的语义从而通过称之为霍尔三元组的断言来验证程序的正确性 软件测试是指验证一个程序或系统的某些属性或能力来判断它是否达到预期目的的行为尽管软件测试在软件质量方面起着至关重要的作用并且被程序员和测试员们广泛采用但由于人们对软件的认识十分有限它仍旧是一个艰深的领域软件测试的最大难点在于如何控制其复杂性我们没有办法在一个合理的复杂度内完整地测试一个程序测试不只是调试测试的目的包括但不限于确保软件质量验证其正确性和估算其稳定性我们对测试的定义也可以更加一般化其中正确性测试和稳定性测试是两个最大的研究领域软件测试是预算时间和软件质量的一个平衡