Why Writing Correct Software Is Hard
TL;DR · AI 摘要
Why Writing Correct Software Is Hard Why Writing Correct Software Is Hard 23 Jul 2016 … and why math alone won’t help us...
核心要点
- 主题聚焦:Why Writing Correct Software Is Hard
- 来源:Hacker News Best,建议结合原文判断细节。
- AI 分析暂不可用,本条为保底评分与摘要。
为何编写正确软件如此困难
为何编写正确软件如此困难
2016年7月23日
… 以及为何数学(单独)无法帮助我们
我很高兴再次在Curry On上发表演讲。去年,在与Quasar合作之后,我曾就延续性与单子进行了演讲。今年,我做了一场关于软件验证中计算复杂性结果的演讲,这个主题是在我们为即将推出的Galaxy新版进行形式化规范和验证时产生的兴趣。
以下是对上述演讲的扩展版本(嵌入在上方),包含了一些额外的证明和结果,这些内容由于时间限制未能在演讲中涵盖,还附有脚注,供希望进一步研究这些主题的人参考。阅读时间:约45分钟。
在本文中,我们试图理解程序与正确性之间的关系,特别是为何编写正确的程序如此困难。我们将回顾可计算性理论和复杂性理论中的结果,并看到程序与完全理解(这是正确性所必需的)之间存在根本性的矛盾。本文的主要贡献是将一些关于生产正确软件本质困难性的结果(以及一些参考文献)集中在一个地方。我的动机是网上一些声明(例如这个,尽管远非唯一的一个),声称使用合适的工具可以轻松实现软件正确性。虽然某些工具确实(并且确实)有助于确保程序的正确性,但正确性需要付出显著的代价。正确性的代价——就像减少熵所需的能量代价一样——是计算的“自然法则”的结果,这些法则无法避免。
第一章:基础
理论计算机科学的故事大约始于一百年前。随着数理逻辑的成功发展,数学家大卫·希尔伯特提出了一个将所有数学形式化的计划。他希望证明这种形式化是相容且完整的,并找到一个决策过程,即一种用于确定每个形式化陈述真实性的算法:
相容性:证明在形式化系统中无法得到矛盾。完整性:所有真实的数学陈述都可以在形式化系统中被证明。可判定性:一个决定任何陈述是否为定理的算法(判定问题)
希尔伯特认为,任何可以通过形式化推理处理的事物也可以被完全理解,也就是说,所有属性都可以被证明。19世纪对知识局限性的看法用“ignoramus et ignorabimus”(我们不知道,而且我们将永远不知道)这一格言来表达。为了1930年的退休演讲,希尔伯特在柯尼斯堡向德国科学家和医生学会发表了题为“Naturerkennen und Logik”(自然认知与逻辑)的演讲,挑战了这一观点。他说:
对于数学家来说,不存在Ignorabimus,而且在我看来,自然科学也不存在。……我认为,没有人成功找到一个不可解问题的真实原因在于,根本不存在不可解的问题。与愚蠢的Ignorabimus相反,我们的信念是:我们必须知道,我们终将知道!1
这些话——“Wir müssen wissen. Wir werden wissen.”(我们必须知道,我们终将知道)——被刻在他的墓碑上。
当时希尔伯特并不知道,他的计划在前一天就已经被摧毁,当时库尔特·哥德尔初步宣布了他的第一个不完备性定理2。
哥德尔的不完备定理摧毁了希尔伯特计划的前两根支柱(有些人认为也摧毁了第三根,但希尔伯特本人并未意识到这一点),1936年,丘奇和图灵通过证明今天被称为停机定理的结论,打破了第三根支柱——判定问题。
停机定理(计算机科学的第一个定理)在1936年同时出现在阿隆佐·丘奇和艾伦·图灵的论文中。该定理如此深刻地揭示了计算的本质,以至于它同时出现在两种计算理论的表述中并非偶然。该定理指出,不存在一个算法能够判断任意给定的程序是否会终止。该证明(此处以简化形式呈现)基于对角线法或自指的思想,这与哥德尔在不完备性证明中使用的思想相同。
假设存在这样一个程序H:
H(M, x) := IF M halts on x THEN TRUE
ELSE FALSE我们可以轻松构造出G:
G(y) := IF H(y, y) = FALSE THEN TRUE
ELSE loop forever如果我们让G自指(G(G)),就会出现G的行为与H所声称的G的行为之间的矛盾。
有趣的是,停机定理立即推导出哥德尔第一不完备定理的一个版本。证明非常简洁:假设对于每一个真命题,都存在某个逻辑理论(本质上是一组公理)中的逻辑证明。因此,给定一个程序,我们可以从这些公理出发,通过逻辑推理逐一列举所有定理。由于所有命题(更不用说所有定理)的数量是可数的,且每个命题要么有证明,要么其否定有证明,我们最终总会找到其中一个的证明。因此,给定一个程序,我们可以开始列举所有定理,直到找到一个定理表明该程序会终止,或者找到一个定理表明它不会终止,从而违反停机定理。
然而,停机定理还有一些其他直接推论,这些推论与软件验证问题联系得更紧密,这也是我们关注的重点。第一个推论是关于可达性的简单结论。
不存在这样的程序R,当给定一个程序M、初始状态集合I和状态配置S时,能够确定M在从I中的某个状态开始时是否会达到S。
该证明通过将停机问题简化为停机问题:如果存在这样一个算法,我们可以询问它是否在输入x时会达到停机状态,从而解决停机问题。
一个更有趣的推论是里斯定理。程序可以计算所谓的偏函数。如果它们在给定输入时停止,我们将磁带上写入的输出视为映射到初始输入;如果它们对某个输入永远不终止,我们将该输入视为未映射。里斯定理指出:
对于任何偏函数的非平凡性质,没有算法能够判断一个程序(图灵机)M是否计算具有该性质的偏函数。
例如,不存在算法可以确定一个程序的输出是否始终是其输入的平方。该定理也是通过从停机问题的简化证明的。
对于我们的目的,我认为停机定理最有趣的推论是我们将称之为“忙碌的海狸定理”的结论,因为它最好地体现了分析程序复杂性的概念,并为其提供了量化衡量。与我们在此处讨论的所有结果一样,这个结论既适用于程序的动态视角(即它们运行时的行为),也适用于静态视角(即它们的全局属性),但这个结论分别针对这两种视角进行分析,因此有助于更直观地理解它们是同一枚硬币的两面。
在动态视角下,我们定义如下自然数上的函数:
$f(n)$ = 具有 $n$ 个控制状态的停机图灵机在停机前可能经历的最大步数
图灵机的控制状态构成了它的程序,因此 $n$ 是程序的规模。该函数是良好定义的,因为规模为 $n$ 的图灵机数量是有限的。其中能够终止的子集也是有限的,因此必然存在一个最大值。
该定理指出 $f$ 是不可计算的。假设 $f$ 是可计算的,那么这将违反停机定理。给定一个图灵机,我们统计其控制状态的数量 $n$,计算 $f(n)$(根据我们对 $f$ 可计算性的假设这是可能的),然后运行该机器 $f(n)$ 步。如果它在那时仍未终止——那么根据 $f$ 的定义,它肯定永远不会终止,而我们就能得到一个判定停机问题的可判定过程,这与停机定理相矛盾。
不仅 $f$ 是一个不可计算函数,而且任何已知对所有 $n$ 都大于 $f$ 的函数也是不可计算的,因为如果我们知道这样的函数,同样的过程将再次得出停机问题的判定结果。
同样的论证也适用于程序的静态视角。为了理解这个结果,我们需要知道:给定一个具有有限公理集合的逻辑理论,算法可以从公理开始,逐个应用推理规则,并逐一列举所有定理(可证明的陈述)。
这一次,我们定义如下函数:
$g(n)$ = 尺寸为 $n$ 的停机图灵机的终止证明的最小证明的最大规模
对于每个规模为 $n$ 的终止图灵机,我们选择其终止证明中最短的证明(至少存在一个证明,因为终止的执行轨迹本身就是这样的证明)。然后在所有规模为 $n$ 的终止图灵机中取最大值(这些机器的数量是有限的)。
与 $f$ 类似,$g$ 也必须是不可计算的。如果 $g(n)$ 是可计算的,那么给定一个规模为 $n$ 的图灵机,我们可以通过某些公理描述该机器,然后列举所有证明规模不超过 $g(n)$ 的定理——这是有限数量的——如果找不到任何证明,我们就能确定该机器永远不会终止;这同样与停机定理相矛盾。
这个停机定理的推论揭示了以下事实:无论我们关注动态证明技术还是静态证明技术,将程序规模与证明其终止的难度联系起来的函数都大于所有可计算函数(更精确地说:不存在一个可计算函数,它能被证明对所有 $n$ 的值都大于我们的函数)。
虽然我们无法对所有 $n$ 计算 $f$,但我们可以对某些值计算 $f$ 或其下界。对于 $n = 6$(使用二进制符号表),其值大于 $7.4 \times 10^{36534}$。
另一个值得探讨的问题是:我们已经知道无法设计出一个算法来判断任意程序是否会停止,但是否存在某些特定的程序,我们甚至无法确定它们是否会停止(即使我们为它们量身定制一个判断过程)?
哥德尔第二不完备定理给出了这样的程序。该定理指出,一个逻辑系统无法证明自身的完备性。被广泛接受为数学基础的逻辑系统称为ZFC——即带有选择公理的策梅洛-弗兰克尔集合论;在这个系统中,我们可以证明绝大多数关心的数学定理(仅有一些非常特殊、非常著名的例外)。因此,我们可以构造一个程序,其行为如下:从ZFC公理出发,枚举所有定理,直到遇到矛盾(例如1=2)时停止。该程序会在且仅会在ZFC不一致时停止。我们假设ZFC是一致的,因此预期该程序永远不会停止,但根据第二不完备定理,我们无法证明这一点。
今年五月,Adam Yedidiya和Scott Aaronson发表了一个可以编译为图灵机的程序,其工作原理与上述机制(或等效机制)一致。随后,Stefan O’Rear改进了这一成果,他创造了一个拥有1919个控制状态的图灵机,其终止性无法被证明(即“与ZFC独立”)。这台机器如此小巧,甚至可以轻松放入4K挑战的限制中,其规模相当于一个100到200行的Python程序。
这意味着存在一些规模很小的程序——仅几百行或更少——其行为无法通过数学方法确定。这并非因为分析过程过于庞大或难以处理,而是因为数学本身的力量不足以证明该程序的行为,即使在理论上也是如此。
计算机科学并非数学
无论如何,随着哥德尔、丘奇和图灵的工作,希尔伯特的计划——至少按照最初的设想——在80年前就被彻底终结了。当时,一些简单、紧凑、可以形式化推理但无法完全理解的数学对象(即计算机程序)宣告了这一计划的终结。
还有一个基础性问题需要探讨。停机定理的整个前提都建立在这样一个观念上:需要无限计算步骤的函数是不可计算的。这一点并不显而易见。毕竟,数学经常处理无限对象。丘奇在论文中对此点一笔带过(或许他认为这是显而易见的——他称之为“模糊的直观概念”),而图灵的论文则比丘奇的更具哲学性,他特意解释了算法是人或机器执行的某种过程。
1947年,他在伦敦数学学会做了一场演讲。他说:
几年前,我正在研究现在可以描述为对数字计算机理论可能性和局限性的调查。
在这些理论论证中,内存必须是无限的这一点至关重要……像ACE这样的机器可以被视为这种同类机器的实际版本。
这正是图灵看待其1936年突破性成就的方式。尽管数学形式化可能涉及无限性,但图灵清楚地认识到计算概念与某种物理过程密切相关。如果不是这样,就无法解释停机问题的核心地位及其作为希尔伯特判定问题否定解的用途。算法是物理世界中执行的某种事物。
如今所呈现的丘奇-图灵论题推测,任何由可实现的物理过程完成的计算,都可以通过丘奇和图灵描述的通用计算模型来完成。从某种意义上说,这意味着宇宙中的一切都可以被形式化并模拟为计算机程序。
程序本质上与完全的理解、证明和正确性存在根本性的矛盾。
作为一门学术学科而非工具,数学关注的是小圆圈内部的内容,而计算机科学则主要关注小圆圈外部的内容——正如我们即将看到的,即使那些位于内部圆圈中的程序,许多只能在原则上被证明,而无法实际可行地被证明——我认为计算机科学并不是数学。
第二章:复杂度
从实际角度来看,代数级与指数级之间的差异通常比有限与无限之间的差异更为关键。——杰克·埃德蒙兹,1965
验证(即停机及其推论)是否可判定并不能完全体现问题的难度。由于图灵机可能具有无限行为,验证它们的问题——从某种意义上说——可以被视为类似于对有限或无限长度列表进行排序,或在这样的列表中找到最大元素的问题。两者同样不可能,但当我们限制在有限情况时,它们的难度却大不相同。
这个问题在时间与努力上的重要性在图灵时代就已显现。麦克斯·纽曼是图灵在剑桥大学的导师,也是布莱切利公园的密码破译专家,他在1952年BBC电台首次关于人工智能的公开讨论中向图灵提出了这个问题:
麦克斯·纽曼:说机器可以被制造成做这做那固然很好,但……做这些事情需要多长时间呢?……在机器上解决问题并不意味着要在现在到永恒之间找到方法,而是在合理的时间内找到方法……图灵:在我看来,这个时间因素是涉及所有真正技术难题的唯一问题。
图灵最初论文发表后又过了30年,算法难度问题才被正式定义。计算复杂度理论诞生于1965年,由朱里斯·哈特马尼斯和理查德·斯特恩斯在一篇论文中提出,该论文开篇写道:
在他著名的论文中,A. M. 图灵研究了序列(函数)通过机械过程的可计算性,并证明序列集合可以划分为可计算序列和不可计算序列。然而人们发现,一些可计算序列非常容易计算,而另一些可计算序列似乎具有内在的复杂性,使它们难以计算。在本文中,我们将探讨根据计算难度对序列进行分类的方案。
在1993年图灵奖演讲中,哈特马尼斯表示他将复杂度视为自然法则,类似于物理定律。
我热爱物理,因为它精确的定律能够支配并解释物理世界的行为。在香农的工作中,我第一次看到精确的定量定律支配着信息这一抽象实体的行为……这引发了一个问题:是否存在精确的定量定律支配计算这一抽象过程?而这一过程并不直接受物理定律的约束。是否存在定量定律,能够确定每个问题需要多少计算工作量(工作),以及如何衡量和确定它?16
现在是重新审视Church-Turing论题的好时机,该论题目前的理解是:任何物理系统在宇宙中能够完成的计算,也可以由任何通用计算模型完成。需要强调的是,至今尚未发现任何反例。
该论题的一个更强版本指出:图灵机可以以不超过多项式计算成本模拟任何物理过程。这一版本可能因量子计算机的可能性而被证明是错误的,对这一论点的表述也存在修正,但我们将讨论的复杂度类与那些有趣的复杂度类无关,因此需要强调:
无论发现什么计算界限,它们在多项式范围内也适用于人类。正如Hartmanis所说,它们可以被视为自然规律。人类心智极不可能(尽管理论上可能)计算那些非图灵可计算的问题,也不太可能使用量子算法,从而比图灵机更快地计算;经验上,从未观察到人类违反复杂度界限的例子。
有界停机与摊还有界停机
毫不令人意外的是,正是我们关于停机问题精确难度的疑问,使Hartmanis和Stearns能够证明某些问题的固有难度,并证明现在被称为时间层次定理的结论,该定理指出计算问题形成了一个无限的、严格的难度层次。
我在这里呈现的问题通常被称为“有界停机”,它提出以下问题:判断任意程序M在输入x上是否在n步内停止的复杂度是多少?
假设我们能以较低的开销模拟该程序,那么可以在$O(n)$时间内完成,但能否更快?我们证明这不可能的论证将精确模仿停机定理的对角线化证明(我需要指出,我的证明草图表述不够精确,因为它没有考虑模拟另一台机器的开销,更符合Stephen Cook在1972年针对RAM机器而非图灵机的研究结果17):
让我们假设我们能更快地回答这个问题:
$H_n(M, x)$ := 如果$M$在输入$x$上$n$步内停止,则返回TRUE,否则返回FALSE
使得,$TIME(H_n) \leq n - 2$
然后我们定义:
$G(y)$ := 如果$H_n(y, y)$为FALSE,则返回TRUE;否则循环$n$次并返回FALSE
正如停机定理证明中那样,如果我们随后将$G$传递给自身($G(G)$),就会出现矛盾,因为$G$的行为与$H$声称$G$的行为之间产生矛盾,因为我们注意到$H_n$在$n-2$步内返回结果,而$G$则在再增加一步后返回TRUE,从而在$n$步内终止。
简而言之,你无法在不运行程序的情况下比运行它更快地知道程序会做什么。有界停机问题是$\theta(n)$。
但我们可以将一个输入的结论推广到另一个输入吗?我们是否可以对某些输入付出更多努力,从而在所有其他输入上变得更快?如果对某些输入的程序行为分析能带来其他输入的收益,那么存在足够多的输入数量$K$,使得回答所有这些输入的有界停机问题所需步骤数少于$K \cdot n$。我未在文献中找到这个问题,因此将其命名为“均摊有界停机”,可以精确表述如下:
给定自然数$n$、$K$,是否存在一台机器,对于所有图灵机$M$,$HA_{n,k}(M, x_1,…, x_k)$能在$K \cdot n$步骤内判断$M$是否在所有$x_1…x_k$输入下$n$步内停机?
该问题的答案同样是否定的,可以通过归约到有界停机问题证明。设$UTM$是通用图灵机(它仅模拟输入的机器和输入)。如果这是可能的,我们可以用它来实现$H_{K \cdot n}$如下:
其中$r_1,…, r_{k-1}$是任意输入。
现在,我们关于有界停机问题的$\theta(n)$结果实际上回答了停机问题的复杂性问题。因为我们无法比运行程序更快地回答任何关于程序的问题,而一旦程序进入已访问过的状态,我们就能确定它永远不会停机。在最坏情况下,复杂度至少等于状态数(加上记录状态的开销)。在一般情况下,图灵机可能有无限多个状态,因此最坏情况复杂度是无限的,而一般停机问题的不可判定性则是有界停机问题的一个特例。
我们将这一结果写为$\Omega(|S|)$,正如我们将看到的,它极其稳健;即使我们将机器的计算能力从图灵完备模型降低到更弱的模型,这一结论依然成立。
顺便提及,尽管有界停机问题最早由Hartmanis和Stearns于1965年直接证明,作为时间分层定理的一部分(现在可以将停机问题视为该定理的极限情况),但我认为哥德尔可能更早使用过类似的思想。在他著名的1956年写给冯·诺依曼的信中,他首次提出了P vs. NP问题(尽管当时并未使用现代术语;这些术语直到1971年由Stephen Cook提出),他这样写道:
…在我看来,$\varphi(n) \geq Kn$似乎是唯一可以从判定问题不可解性证明推广得出的估计。
看来哥德尔也意识到了停机定理对角化证明向有限情况的简单扩展。
验证是计算机科学中最难的问题
在继续之前,我想以最一般的方式说明我所说的“验证”——如果可能的话,我们最希望实现的验证目标是什么。给定一个程序$M$和一个可以用某种逻辑描述程序属性的陈述$\varphi$,我们希望确定$M$是否满足$\varphi$:
可以很容易看出,这个非常一般性的问题包含了停机问题、“Rice”(功能指称)、可达性等,因此从计算复杂性角度看,它肯定不比这些问题更容易。
在数理逻辑的表述中,我们说需要验证 $M$ 是否为 $\varphi$ 的模型,因此这个问题更广为人知的是“模型检查问题”(不要与我们稍后简要讨论的特定自动模型检查算法——称为模型检查器——混淆)。
如何确定 $M$ 是否为 $\varphi$ 的模型,即 $M$ 是否满足 $\varphi$,取决于我们的选择。计算复杂性理论研究的是问题本身的难度,而非具体解决方案的难度。例如,我们可能选择通过一组逻辑公理描述 $M$ 的运行方式,并尝试通过演绎推理为 $\varphi$ 找到证明。这是一种特定的满足性证明方式,因此其难度并不比一般模型检查问题更小,仍需受限于其复杂度边界。同样,这些结论适用于机器和人类。
尽管我们已经确立了通用情况下验证的难度(或者说,更准确地说,是其不可能性),但在尝试放弃图灵完备性以寻找可行的验证方法之前,让我们从略微不同的角度再审视一次这个问题。我们甚至可以将范围限制于特定的验证问题——确定一个终止程序的执行结果——这显然是通用模型检查问题的一个特例。按照可计算性与复杂性理论中常见的做法,我们将仅限于决策问题——即返回真或假的问题。此外,我们只考虑那些已知存在总算法(即总是终止的程序)且具有可计算上界复杂度的问题。设 $P$ 为这样一个任意的决策问题,其已知的时间复杂度上界为 $f(n)$($n$ 为 $P$ 的输入 $x$ 的长度)。由于我们已知 $P$ 的复杂度上界,因此存在一个算法 $M_P$,它可以在 $f(n)$ 步内决定 $P$。现在,假设我们有一个验证程序 $V$,当给定一个决策程序 $M_P$ 和输入 $x$ 时,$V$ 能告诉我们 $M$ 是否接受 $x$(返回真)。算法 $V$ 存在且是可判定的,因为最坏情况下,它可以直接模拟 $M_P$。
鉴于以上内容,我们可以将决定 $P$ 的问题简化为回答 $V(M_P, x)$(这等价于 $P(x)$)。由于对于给定的问题 $P$,$M_P$ 是固定的,因此这种归约是多项式时间的。这意味着,如果 $P$ 存在下界复杂度,那么 $V$ 的复杂度必须大于该下界。我们说 $V$ 至少和 $P$ 一样困难。然而,$P$ 是任意选择的,根据时间层次定理,对于任意可计算的 $g(n)$,我们总能找到一个复杂度高于 $g$ 的问题 $P$,因此 $V$ 比所有具有已知计算上界的问题都更难。我们说,任何具有已知上界复杂度的决策问题都可以归约为有界停机问题。换句话说,验证是计算机科学中最困难的问题。
限制我们的范围
为了尝试解决验证问题,我们可以通过限制左侧的机器或右侧检查的属性来简化问题。迄今为止,限制属性对我们的帮助不大,因为即使对于最简单的属性(如停机、结果、可达性),我们也会得到不可判定或难以处理的结果,因此让我们尝试限制机器本身。
一种实现方式是将自己限制在易于证明终止的程序上,通过使用一种要求所有循环和/或递归调用都必须带有递减计数器的编程风格或语言。这些语言被称为全语言(total languages)18,它们允许编写所有全程序的一个有用子集。
然而,如果我们审视有界终止的对角化证明,当我们将$M$限制为使用全语言编写的程序时,$H_n$和$G$也可以用这种语言编写。得出的结论完全相同。验证复杂度仍然是$\Omega(|S|)$。但全语言中程序的规模与其状态数之间存在什么关系呢?显然,它比所有原始递归函数(以及一些非原始递归函数,比如Turner提到的在全语言中容易计算的阿克曼函数)都要大,但它可能仍然是可计算的。无论如何,对于我们的目的来说,它已经可以视为无限大了19。
因此,全语言的限制并不能使验证更容易。事实上,如果发现一个不可能的问题通过轻微限制(比如放弃真皮座椅)就变得容易,这将是令人惊讶的(这不会让汽车成本降低90%)。我们还注意到,每个程序都可以通过给所有循环添加一个大计数器(比如$2^{100}$)被简单地转化为全语言程序——这不会以任何方式改变其物理语义——因此,我们完全可以假设所有现实世界的程序都可以用全语言编写而不会损失一般性。如果全语言真的有帮助,我们早就可以假设所有语言都是全语言了。
为了直观说明全语言程序的验证难度,下面这个10行的Java或C示例采用了全语言风格。所有循环都有递减计数器。它显然总是终止。它也没有进行任何复杂的数学运算——仅仅是减法:
int foo(int x) {
if (x <= 2 || (x & 1) != 0)
return 0;
for (int i = x; i > 0; i--)
if (bar(i) && bar(x - i))
return i;
crash(); // reachable?
}
boolean bar(int x) {
for (int i = x - 1; i >= 2; i--)
for (int s = x; s >= 0; s -= i)
if (s == 0)
return false;
return true;
}然而,数学家们在270年里一直未能证明这个程序永远不会失败(即不会执行到crash())。该程序只有在哥德巴赫猜想不成立时才会崩溃(当然,假设我们将int替换为更大的整数类型;我们已知它对32位整数成立,但对64位整数是否成立尚不确定)。此时,一些读者可能会说:“当然,证明编码了困难数论问题的程序行为会很困难!”但这是对问题的误解。认识到这个程序编码了一个著名的数论难题,只是让我们确信验证这个特定程序确实很困难。但这并不能说明这个程序比我们日常遇到的程序更难验证。如果我们不知道这个程序与哥德巴赫猜想的对应关系(或者哥德巴赫从未提出过这个猜想),仅通过观察代码,我们能否判断验证这个程序会如此困难?
现在,我们还有其他多种方式可以限制计算模型。例如,Stephen Bellantoni 和 Stephen Cook 发明了一种语言,其中每个程序都可以在 PTIME 内计算完成。另一种模型是下推自动机(PDA)。这个模型非常有趣且具有挑战性——尽管该模型允许无限数量的状态,但许多 PDA 的性质仍然可以被验证。然而,即使是最轻微的改动也可能使基于它的语言变得图灵完备(例如,两个 PDA 通信时就具有图灵完备性;要理解原因,可以想象其中一个机器的栈是读写头左侧的磁带,另一个机器的栈是读写头右侧的磁带)。
相反,我们将直接跳到有限状态机,这是仍然有用的最弱计算模型,因为在该模型中我们可以找到最有趣的结论。
用于有限状态机(FSM)完整验证的自动化方法——称为模型检测器——自 20 世纪 80 年代以来就已存在,可能是工业界最常用的正式验证技术。这是因为存在实用的自动化方法,该问题的复杂性已被广泛研究。不过,请不要让术语迷惑你:本节中我将介绍的两个结果涉及模型检测问题的固有复杂性,而不是特定模型检测算法的复杂性。
时序逻辑(由 Amir Pnueli 于 1977 年引入计算机科学领域,他因此获得了图灵奖)自 20 世纪 70 年代末以来一直是描述程序属性的主要逻辑。在 20 世纪 80 年代,针对有限状态机和时序逻辑属性的全自动模型检测算法被发明出来(最早由 Emerson、Clarke 和 Sifakis 提出)。对于一种称为计算树逻辑(CTL)的时序逻辑,模型检测复杂度为 $O(|\varphi||S|)$;对于另一种线性时序逻辑(LTL),复杂度为 $2^{O(|\varphi|)} O(|S|)$。请注意,如果将属性公式 $\varphi$ 的长度视为常数,这两个复杂度上限基本上都是 $O(|S|)$——这与停机问题所决定的复杂度一致。这一结果表明,对于非常有用的逻辑,存在仅与状态空间大小成线性关系的模型检测算法(因此对模型检测问题右侧的复杂度相对不敏感),这一成就使 Emerson、Clarke 和 Sifakis 获得了图灵奖。
正确性无法分解
熟悉的复杂度类有时过于粗糙。参数化复杂度在某些情况下通过引入更精细的分类来解决这个问题。其中最重要的分类是 FPT(固定参数可解),它表示问题可能在某个参数 $k$(实际上是 $k(x)$,输入 $x$ 的函数)上不可解(例如指数级),但其他情况下在输入长度上是多项式时间的。如果一个问题的复杂度为 $f(k) \cdot |x|^{O(1)}$(其中 $k(x)$ 是参数),则该问题属于 FPT。如果在实际应用中参数可以保持较小,问题将变得可解。一个属于 FPT 的问题是 SAT(布尔公式可满足性),它属于 NP 完全问题,但朴素算法的复杂度仅与变量数量呈指数关系,与公式长度呈线性关系。另一个例子是 Hindley-Milner 类型推断,这就是它在实践中效率很高的原因。
验证(FSM)是否属于固定参数可解(FPT)问题,并且在实践中是否可行?2005年的一篇论文探讨了这个问题,尝试通过模块化程序来参数化验证复杂度。其核心思想是:或许每个模块或组件可以独立验证,而组件组合的验证复杂度可能随着组件数量呈指数增长——但组件数量本身会保持较低——而不会随着每个组件的规模或每个组件内部“隐藏”状态的数量而变得难以处理。研究结果是负面的,其证明基于一个关键观察:k个有限状态机可以模拟一个具有约k个磁带单元的非确定性图灵机(NDTM);验证空间受限的NDTM已知不属于FPT:
我们的研究表明,这些问题即使从参数化的FPT角度考虑,也可能并不容易处理……我们认为,通过将k视为参数的其他方式来解决这一难题的可能性不大21。
这一结果具有深远意义。它表明,我们通常无法通过模块化来降低证明程序正确性的努力。正确性无法被分解。
上述foo/bar程序(也即哥德巴赫程序)正体现了这种现象。bar是正确的(即它能正确判断其参数是否为质数,忽略我特定实现中可能存在的漏洞)。这使我们只剩下foo需要分析。前两行代码显然简单,剩下的三行代码则极具挑战性。你无法找到比这更模块化和可组合的代码!它们不过是简单的降序for循环、一次减法操作,以及一次将两个高度模块化的bar调用通过析取组合起来的操作。然而,这三行代码的行为证明却困扰了人们300年,因为bar(即isPrime)尽管本身正确,其行为在某些上下文中可以被推理,但在这种情况下却难以处理。我们看到,一个经过良好定义且正确的模块(bar)的简单组合(foo),仍然会形成一个难以穿透的整体。
语言抽象通常无法被利用
现在我们终于可以讨论语言的问题了。我们不会将程序写成巨大的状态转移图。我们使用具有抽象机制、甚至具备正确语义的编程语言,来创建与状态空间相比非常简洁的程序。那么,我们能否利用有限状态机源代码中的结构?这就是符号模型检测问题。
理论上,存在乐观空间。研究验证问题计算复杂度的Philippe Schnoebelen指出:
从复杂度理论的角度来看,没有理由认为符号模型检测不能在最坏情况下更高效地解决……符号模型检测器只处理一种非常特殊的巨大结构,即那些具有简洁表示的结构……(请注意,通过简单的基数论证可以发现,具有简洁表示的巨大结构非常稀少)22
这里有一个微妙之处,需要我们解释清楚所谓用于编写有限状态机(FSM)的语言到底是什么意思。理论上,图灵完备模型与有限状态机之间的区别非常明确:前者可以识别上下文相关语言,而后者只能识别正则语言。但实际中,由于每台计算机都是有限的,可以说每个实际程序都是一种有限状态机。因此,尽管我将展示的有限状态机结果在一般情况下成立(即,即使对于图灵完备语言,其程序在实践中也是巨大的有限状态机),但当我谈到有限状态机语言时,我指的是那些程序的最大状态数可以从源代码中轻松计算的语言。
不幸的是,事实证明,将自己限制在具有简洁表示的程序上并不能解决问题。符号模型检查问题属于PSPACE完全问题,其复杂度与仅仅展开简洁程序的状态图并完全忽略其语法表示的复杂度相同。这不仅在最坏情况下成立,在许多现实世界案例中也是如此:
换句话说,对于模型检查目的而言,允许简洁表示的Kripke结构并不比任意Kripke结构更简单。
确实,这在许多实例中已被观察到,从可达性问题到等价性问题,如今可以被称为经验事实22。
(Kripke结构基本上是程序的状态转移图,与它所使用的语言无关。这是一种抽象地讨论程序的方式,不考虑其语法表示。)
事实上,我们可以描绘每种编程抽象如何影响验证复杂度。下图摘自Rajeev Alur23的一篇论文,展示了基于语言中可用抽象的模型检查复杂度与程序规模的关系。
一般来说,变量和并发等允许我们创建状态空间的笛卡尔积的抽象,会指数级增加简洁性,但也会以相同程度增加验证复杂度。鉴于上一个结果,这并不令人意外。
实际上,有一种称为层次结构的抽象,可以指数级增加简洁性,但在某些特定情况下仅多项式级增加复杂度。这种抽象在嵌入式和实时软件中被广泛使用,很大程度上正是由于这一特性,但在“普通”编程语言中并不常见(我认为无参数的子程序构成了层次结构)。一个函数的简单抽象,即带参数的子程序,是变量抽象与层次结构抽象的组合。
为了快速说明为什么验证有限状态机都很困难,考虑一种仅包含布尔变量和函数调用的语言。这种语言没有高阶函数、没有递归、也没有迭代。显然,这种语言是一种有限状态机语言。例如,该程序的状态数最多为$2^6$:
A() = B(TRUE) ∧ B(FALSE)
B(a) = C(a, TRUE) ∨ C(a, FALSE)
C(a, b) = D(a, b, TRUE) ∧ D(a, b, FALSE)
D(a, b, c) = E(a, b, c, TRUE) ∨ E(a, b, c, FALSE)
E(a, b, c, d) = F(a, b, c, d, TRUE) ∧ F(a, b, c, d, FALSE)
F(a, b, c, d, e) = X(a, b, c, d, e, TRUE) ∨ X(a, b, c, d, e, FALSE)
X(a, b, c, d, e, f) = ((a ∧ b) ∨ c) ∧ ¬d ∧ (e ∨ f)然而,验证这种语言中的程序是PSPACE难的,因为即使上面那个简单的程序也直接编码了一个TQBF(全称量化布尔公式)问题,而TQBF问题是PSPACE完全的(在这种情况下,公式为$\forall a \exists b \forall c \exists d \forall e \exists f . ((a \land b) \lor c) \land \lnot d \land (e \lor f)$)。
不过,我们必须指出,符号模型检测的结果对模型检测问题的右侧部分非常敏感:语言抽象并不能帮助验证任意属性,但它们可以(并且确实)帮助创建有效的状态空间缩减,这些缩减可用于高效验证某些特定属性;我们将在下一章讨论抽象解释时简要提及这些内容。例如,在上面的简单“TQBF”程序中,我们可以利用语言抽象和抽象解释,以较低的代价检查变量a的值是否可能影响程序的结果。
鉴于我们看到的所有结果,我们可以陈述这个非正式定理:
不存在一种普遍有用的编程语言,使得每个程序都可以被有效验证
现在我们知道了为什么编写正确的程序如此困难:因为这必须如此。然而,虽然我们无法随时验证所有程序——无论它们如何编写——但没有任何东西阻止我们有时验证某些程序的某些属性。
第三章:验证
现在我们知道了为什么编写正确的程序如此困难:因为这必须如此。然而,虽然我们无法随时验证所有程序——无论它们如何编写——但没有任何东西阻止我们有时验证某些程序的某些属性。正如我们将看到的,没有任何软件验证方法能够克服我们已经探讨的限制,而正是这些限制影响了每种验证方法的设计和权衡。当然,软件验证是一个广泛的主题,我在这里的目标只是简要描述这些方法及其与我们讨论的复杂性结果之间的关系。
图灵完全清楚编写正确软件的困难。他在1947年的演讲中这样说道:
[T]he possibilities as to what one may do are immense. One of our difficulties will be the maintenance of an appropriate discipline, so that we do not lose track of what we are doing.
The machine interprets whatever it is told in a quite definite manner without any sense of humour or sense of proportion. Unless in communicating with it one says exactly what one means, trouble is bound to result.
图灵的解决方案?类型!
We shall need a number of efficient librarian types to keep us in order.
[this was a joke that didn’t land…]
我之所以提到类型,是因为这是对编程语言感兴趣的开发人员中普遍讨论的话题,而这些开发人员在在线开发者社区中占比不成比例,他们很可能阅读本文。此外,类型也可以被视为一种形式验证,并且在验证方法讨论的结尾部分与之契合。
作为动机,我想提出以下问题。这里再次是赖斯定理:
然而,这不仅可能,而且确保一个C、Java或Haskell程序返回int类型所需的努力非常小。这为何不与定理矛盾?
一些人似乎认为,由于属性是“通过构造保证正确性”,因此不存在违规情况。这是错误的。Rice定理对构造方式没有任何说明,这是有充分理由的。假设我们能够通过类型轻松证明程序结果的属性,因为“通过构造保证正确性”。那么我们可以采用以下高效算法来验证程序:我用Python编写程序,你将其翻译为Haskell,问题就解决了!这不可能,因为复杂性不仅适用于计算机,也适用于人类。
真正的答案必须直接回应Rice定理:要么该属性是平凡的,要么计算偏函数的并非图灵机。
在返回类型为int的情况下,其实际含义是程序要么永不终止,要么返回一个整数。这是一个平凡属性,因为每个程序要么永不终止,要么返回可以被解释为整数的值。关于结果的任何信息都未被知晓。
现在,你们中的一些人会立即意识到这并非总是成立。例如在Haskell中,你可以相对容易地证明程序结果是一个数字字符串。这指定了大量比特信息,将每个输出字节限制为256种可能中的10种。这为何不违反Rice定理?因为该属性不是由图灵机生成的,而是由有限状态机生成的,我将现在展示这一点。但在开始之前,我们必须先绕道探索其他验证方法。
模型检查器
正如我们所见,对于足够小的有限状态机,存在实用的自动模型检查算法。一般来说,"模型检查器"这一名称适用于不依赖特定程序语法表示的算法。
现代模型检查器使用非常复杂的算法来探索日益扩大的状态空间,甚至在某些情况下是无限状态空间。它们的主要优势在于易于使用且极其通用:它们实际上自动解决模型检查问题。通常,它们检查的属性以时序逻辑的形式指定,这种逻辑足够强大,可以表达任何程序属性。它们的主要缺点在于,由于它们解决模型检查问题,因此会受到所谓的"状态爆炸问题"的影响,即即使是一个小程序也可能产生巨大且高度不规则的状态空间。
这是交替位协议的状态空间示例。程序大约30行:
这是用于汽车的CAN总线协议的状态空间:
幸运的是,历史上需要最严格验证的大多数程序(至少在历史上)都相对较小(硬件或嵌入式实时系统),因此模型检查是工业界使用最广泛的正式验证方法也就不足为奇了。
重要的是要理解,状态爆炸问题影响模型检查器并非因为它们使用的算法,而是因为它们试图在一般情况下精确解决模型检查问题——即所有程序、所有属性——因此它们承受了我们之前看到的结果的全部影响(O(|S|))。
顺便说一句,汉诺塔程序的状态空间是一个谢尔宾斯基三角形!
更多示例可在ProB网站上找到。
演绎证明
演绎证明(即使用 $M \vdash \varphi$ 来证明 $M \vDash \varphi$)是另一种通用方法。与模型检测器类似,它具有精确性,因此在计算复杂度上并不比模型检测问题更容易(事实上,在许多情况下两者可以等价)。
尽管它同样受制于相同的最坏情况复杂度限制,但演绎证明在某些情况下可能比模型检测器更具可扩展性。这是因为它可以针对非常具体的问题进行定制,而使用演绎方法验证的程序通常在编写时就已考虑了演绎证明的需求。使用演绎证明的人不会先编写程序再进行证明,而是边编写边证明,通常会大幅限制程序的复杂度,以确保证明的可行性。
在自动证明工具(特别是SMT求解器)领域,已有许多有趣的进展,这些工具可以帮助证明许多通常较为简单的定理。但总体而言,目前人类仍承担了大部分工作。
实证研究表明,尽管这种方法可以奏效,但成本非常高。不过,它并不比当前用于高保障软件开发的方法(例如国防工业中使用的方法)更昂贵。现在我们明白为什么这些方法如此困难:必须有人承担复杂度的代价,如果计算机无法做到,那就只能由人类来承担。在工业界,手动演绎证明通常用于将自动证明和模型检测的结果联系起来。
即使不考虑寻找证明的难度,一个可行的证明(即长度与程序规模呈多项式关系的证明)可能根本不存在。Cook和Reckhow在1975年证明了一个著名结果:即使在最简单的命题演算中(所有逻辑中最简单的形式,仅包含布尔变量和布尔连接词,如与、或、非),所有重言式都存在短证明当且仅当 $NP = coNP$,而这一等式通常被认为不成立。
抽象解释(静态分析)
验证问题的一个优雅且数学上深刻的解决方案被称为抽象解释,由Patrick和Radhia Cousot在20世纪70年代提出。通常采用该技术的工具被称为静态分析工具。该技术完全自动化,但通过牺牲精度(即可能用“我不知道”作为回答)来避免难以处理的复杂度限制。
其核心思想非常粗略:将程序视为一个输入程序的正确但精度较低的抽象,通常表示为状态数较少的有限状态机(FSM),然后对这个抽象模型进行模型检测。抽象的复杂度是 $O(|S|)$,即状态数的阶数。例如,考虑以下程序:
p0: while (true)
p1: if isEven(x)
p2: then x := x div 2
p3: else x := x + 1 这个程序在状态空间上是无限的(假设x是一个无界整数),但如果只关心x的奇偶性,我们可以对x的值进行如下转换:
然后可以创建一个包含4个状态的抽象程序,并且仍然能够确定标签p2和p3处的值。
这种方法的复杂度成本仍然是 $O(|S|)$,即状态数的阶数,但这里的抽象程序非常小(加上转换的开销)。当然,这种方法的缺点在于,抽象可能无法始终捕捉我们感兴趣的属性,即使能捕捉,也可能在某些情况下失效。在示例中,我们无法在标签p0和p1处确定x的奇偶性。
类型
将类型视为抽象解释的一种方式,是抽象解释理论中的一个观点,其中一组值被抽象为具体的类型。在抽象程序中,变量的取值是类型。这种抽象有多少种状态?状态的数量大致与函数调用链中具体类型的数量相同;每个状态由当前应用的函数和“当前”值(即一个类型)组成,因此状态数量最多是具体类型数量与函数数量的乘积:
具体类型的数量可能大于直接写出来的类型数量,因为程序中可以包含泛型函数的多态类型,这些类型在抽象程序中会变成接受一个具体类型实例并返回另一个类型的函数:就像一个具体函数可能接受值3并返回值5一样,一个抽象函数可能接受抽象值Integer并返回值[Integer](整数列表)。我需要指出的是,这里仅以非常宽泛的方式讨论了类型所创建的抽象的主题。
因此,仅通过我们关于有界终止的结果(即$O(|S|)$)以及对抽象解释的理解,我们就可以立即获得类型推断算法的界限(该算法的复杂度为$\Omega(\text{# 具体类型})$),因为类型推断需要解决一个可能更复杂的约束问题。
在没有依赖类型(如果你还不了解它们,这并不太重要)的编程语言中,这个数量相对较小,且是一个有限状态机。类型表达了有限状态机的属性,因此我们可以证明的属性并非来自图灵完备程序,而是来自有限状态机,因此这与Rice定理没有矛盾。
如果你还需要进一步的证据证明非依赖类型系统仅能编码有限状态机的属性,如果你是Haskell开发者,可以尝试以下练习来说服自己:尝试将每个函数体(包括库函数)替换为一个显然属于有限状态机的函数,方法是使用固定深度或无界深度的递归(在大多数情况下,深度0或1就足以获得一个类型居民)。你会发现,你总能成功地将一个Haskell程序替换为一个有限状态机程序——虽然这个程序与原始程序完全不同且可能完全错误,但无需对任何签名进行修改即可通过类型检查。
修正:读者@samth和@kamatsu8指出,当使用多态递归(Haskell支持但不自动推断)时,上述说法是错误的。他们提供了一个例子,该例子只能被替换为一个具有少量控制状态的下推自动机(对于该模型,模型检查也是可行的),而不是有限状态机。
另一方面,在具有依赖类型的编程语言中,具体类型的数量可能是无限的,因此类型推断(其复杂度仍为$\Omega(|S|)$)具有无限复杂度,即不可判定。这其实非常简单。
那些熟悉类型与演绎证明之间对应关系(称为“命题即类型”或“Curry-Howard对应”)的读者,现在应该能够理解为什么演绎证明也可以被看作是抽象解释的一个特例,但在这里我们不会进一步探讨这一概念。
要结束本节内容,以下是一张来自Xavier Leroy(CompCert的作者,CompCert是一款经过形式验证和认证的C编译器)演讲的精美幻灯片,该幻灯片通过所需努力、提供的保证以及最适合的程序规模三个维度,展示了不同形式验证方法的特性:
结论
在一篇著名文章《没有银弹》30 的后续讨论中,Fred Brooks指出,他曾经论证过程序员生产率不会出现数量级的提升31:
爱因斯坦关于“没有任何东西能比光速更快”的声明是“悲观的”还是“令人沮丧的”?又或者,哥德尔关于“有些事情无法被计算”的结论?……[T]软件本身的特性使得“银弹”的存在极不可能32。
随后,他引用了Wladyslaw M. Turski对《没有银弹》的观点:
在所有误入歧途的科学探索中,没有比寻找“贤者之石”更可悲的了。这种被假想能将贱金属转化为黄金的物质,是炼金术的终极目标,曾被世代研究者热切追求,而这些研究者得到了世俗和精神统治者的慷慨资助。这纯粹是毫无根据的幻想的浓缩体现,是人们普遍认为世界会按照我们期望的方式运行的常见假设。这是一种非常人性化的信念。接受存在无法解决的问题需要付出巨大努力。即使已被证明不存在出路,人们仍然非常强烈地渴望看到一条出路。我们大多数人对那些试图实现不可能之事的勇敢灵魂充满同情。因此,这种现象仍在继续。关于“化圆为方”的论文仍在撰写,恢复失落头发的药水被研制并畅销,提高软件生产率的方法被提出并大获成功。我们常常倾向于追随自己的乐观主义(或利用赞助者的乐观期望)。我们常常愿意忽视理性的声音,而听从万能药推销者的诱惑。
我认为,我们在前两节中讨论的所有内容都构成了数学证明,证明Brooks和Turski的观点是正确的。但我们又能做些什么呢?
对实证主义的呼吁
我们已经看到,计算机科学研究的对象——计算机程序——由非常基础的组件构成,无论是λ演算中的β约简还是图灵机指令,这些组件本身都可以轻易接受完整的数学推理,但它们的交互本质上是难以处理的。我认为这与物理学类似,例如,重力方程非常简单,多个实例的方程组合也极为优雅,但即使三个天体的相互作用就已经变得混沌,且没有封闭解。
我认为我们应该借鉴物理学的经验,拥抱实证主义。让我们再次审视验证问题:
我们必须限制左侧或右侧。到目前为止,我希望已经清楚,我们不太可能找到一个通用的、有用的程序类别,其验证成本是可接受的,因为即使是最简单的计算模型(有限状态机 FSM)的验证,在一般情况下也是不可行的。但我们可以做出一个显而易见的观察:我们关心的所有程序都是由人类创建的。如果愿意,我们可以将人类视为一个巨大的图灵机 TM,它生成了所有机器 $M$。很可能在人类生成的机器中存在某些模式,这些模式可以允许进行一些成本可控的验证。但由于分析人类作为程序是真正不可行的,唯一可行的方法是对人类编写的程序进行实证研究。我们可以从程序类型、规模、成本等分类开始。
这一观察也使右侧的某些限制成为可能。到目前为止,我们考虑的最简单属性(如终止性)都是全局属性。但在实践中,我们知道——实证表明——某些局部属性同样非常有用。一个很好的例子是内存安全性,这已知是常见且代价高昂的错误来源。我们可能能够找到其他有用的局部属性,但这同样需要实证研究。一个很好的起点是按错误原因、普遍性、与程序类型的关联性以及最重要的——成本——对错误进行分类。
这些实证研究需要学术界和工业界的协作。掌握了这些实证知识后,我们就能像物理学那样,使用临时性的数学方法来处理这些有趣的特殊案例:简化假设、启发式方法或近似计算。
一个如此美丽的实证研究例子是多伦多大学最近的一项研究,该研究发现大型分布式系统中绝大多数灾难性故障都是由于程序员没有充分考虑错误处理代码所致。这显然是一个心理效应。
几乎所有(92%)的灾难性系统故障都是由于软件中明确信号的非致命错误处理不当造成的。在58%的灾难性故障中,底层故障本可以通过简单测试错误处理代码轻松检测到 33 。
他们研究了分布式系统中的灾难性故障,发现大量错误是由于人们没有对异常处理代码进行任何思考所致。这显然是人类编写软件的心理现象。研究人员随后创建了一个简单的代码检查工具,用于识别这种危险模式。这个简单的工具本可以防止Cassandra、HBase、HDFS和MapReduce中33%的所有灾难性故障。
计算机科学不是物理学,但它也不是数学。Juris Hartmanis写道:
计算机科学与已知的科学差异如此深远,以至于必须将其视为科学领域中的一个新物种 34 。
复杂性是本质!
最后,我引用Fred Brooks的话作结:“复杂性是我们所从事的行业,也是限制我们的因素。”
然而,正如图尔斯基所指出的,有些人似乎对这一概念在哲学上感到不满,并试图对抗已被证明的局限性。他们认为世界——我这里不仅仅是在谈论计算——本质上是简单的,而正是人们的愚蠢和制度的无谓复杂化(或者在软件领域,“愚蠢”的编程语言)才让事情变得复杂。如果我们运用严谨的数学推理,似乎可以解决任何问题。
如果要用一句话总结计算复杂性理论,那就是“难题没有简单的解决方案”。如果要总结本文呈现的结果,那就是“……如果你的问题是预测、编写或指导一个计算过程,那么它就是困难的”。
计算机科学正是证明了即使在最微小的系统中,本质复杂性也可能出现的学科。然而,有时正是计算机科学家和软件开发者试图挑战他们自身学科的基础。复杂性是本质的。它无法被驯服,也没有一个统一的答案。我们能做的最好的事情——无论是社会还是计算领域——就是应用大量临时性的技术,并尽可能多地了解问题的特定性质。
在线讨论
- Reddit 1
- Reddit 2
- Hacker News
选读书目
条目按其在文章/演讲中被提及的顺序排列。完整的参考文献列表见下方脚注。
- A. M. 图灵, 《论可计算数及其在判定问题中的应用》, 1936
- A. M. 图灵, 《伦敦数学学会演讲》, 1947年2月20日
- J. 哈特马尼斯和R.E. 斯蒂恩斯, 《关于算法的计算复杂性》, 1965
- 约里斯·哈特马尼斯, 图灵奖演讲:《关于计算复杂性与计算机科学的本质》, 1994
- S. 德姆里、F. 拉鲁辛尼和Ph. 施诺贝尔, 《模型检测中状态爆炸问题的参数分析》, 2005
- 皮埃尔·施诺贝尔, 《时态逻辑模型检测的复杂性》, 2002
- 爱德蒙·M. 克莱尔, 《模型检测:我27年克服状态爆炸问题的探索》, 2007
- 爱德蒙·M. 克莱尔, 《模型检测中状态爆炸问题的进展》, 2001
- 大卫·A. 施密特, 《用于抽象和精化的二元关系》, 1999
- 皮埃尔·库索特, 《基于抽象解释的形式方法及未来挑战》, 2001
- 皮埃尔·库索特, 《类型作为抽象解释》, 1997
- 让-伊夫·吉拉德(保罗·泰勒、伊夫·拉丰翻译并附有附录), 《证明与类型》, 1989
- 约里斯·哈特马尼斯, 《关于计算机科学本质的一些观察》, 1993
- 弗雷德里克·P. 布鲁克斯, Jr., 《没有银弹》及《重燃银弹》, 《人月神话》软件工程论文集, 周年版, Addison-Wesley 1995
在会议上,我很高兴看到一些研究人员强调了对工业软件开发和临时性解决方案进行实证研究(或至少考虑实证观察)的必要性。包含这一主题的演讲包括:
- 詹姆斯·诺布尔, 《后后现代现代编程笔记》
- 彼得·奥赫恩, 《快速前进以修复更多问题》
- 罗斯·泰特, 《为工业面向对象重新设计类型系统》
- 艾米娜·托尔拉克, 《为所有人合成与验证》
- 斯科特·麦克迪尔米德, 《编程的未来将是实时的》
此外,请务必观看这个精彩的Truffle/Graal 演示。
- 约翰·W·道森(John W. Dawson, Jr.),《逻辑困境:库尔特·哥德尔的生活与工作》(Logical Dilemmas, The Life and Work of Kurt Gödel),A K Peters出版社,1997年,第71页 ↩
- 道森(Dawson),第69页 ↩
- 萨尔·克里普克(Saul Kripke),《计算的起源与本质》(The Origins and Nature of Computation),特拉维夫大学讲座,2006年6月13日,1:45:50-1:47:10 ↩
- 阿隆佐·丘奇(Alonzo Church),《初等数论中的一个不可解问题》(An Unsolvable Problem of Elementary Number Theory),1936年 ↩
- A. M. 图灵(A. M. Turing),《关于可计算数及其在判定问题中的应用》(On Computable Numbers, with an application to the Entschidungsproblem),1936年 ↩
- 斯科特·阿罗诺森(Scott Aaronson),《通过图灵机证明罗斯定理》(Rosser’s Theorem via Turing machines),2011年7月 ↩
- 为了证明可达性问题与停机问题难度相当,我们可以对任意一个可达性问题进行转换:将所有现有的停机状态替换为无限循环,并将需要测试可达性的状态标记为停机状态。解决停机问题等价于解决可达性问题,因为转换后的程序会在且仅当原程序中被测试的状态可达时才会停机。 ↩
- 蒂博尔·拉多(Tibor Rado),《不可计算函数》(On Non-Computable Functions),1961年 ↩
- 阿达姆·耶迪迪亚(Adam Yedidia)和斯科特·阿罗诺森(Scott Aaronson),《一个行为独立于集合论的相对较小的图灵机》(A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory),2016年 ↩
- 尽管数学中关于无限性的主题一直存在争议,一些逻辑学家对此持反对意见,我认为反对的原因正是由于与计算相关的相同物理限制。 ↩
- A. M. 图灵(A. M. Turing),《伦敦数学学会讲座》(A lecture to the London Mathematical Society),1947年2月20日 ↩
- 一些读者可能会提出异议。毕竟,程序是抽象的数学概念。但正如物理学作为一门学科并不研究所有物理对象的所有属性(否则化学和生物学就不会作为独立学科存在),数学作为一门学科也不必研究所有数学对象(当然,数学作为工具在计算机科学中的应用非常广泛,就像它在物理学、化学和生物学中的应用一样)。 ↩
- 杰克·埃德蒙兹(Jack Edmonds),《路径、树与花》(Paths, Trees, and Flowers),1965年 ↩
- 英国广播公司(BBC)电台的一次专题讨论,录制于1952年1月10日,见B. 杰克·科普兰(B. Jack Copeland)编,《图灵的核心思想:计算、逻辑、哲学、人工智能与人工生命中的开创性著作,以及恩尼格玛密码的奥秘》(The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life: Plus The Secrets of Enigma),牛津大学出版社,2004年,第503页 ↩ ↩ 2
- J. 哈特马尼斯(J. Hartmanis)和R.E. 斯蒂恩斯(R.E. Stearns),《算法的计算复杂性》(On The Computational Complexity of Algorithms),1965年 ↩
- 朱里斯·哈特马尼斯(Juris Hartmanis),《图灵奖讲座:关于计算复杂性与计算机科学的本质》(Turing Award Lecture: On Computational Complexity and the Nature of Computer Science),1994年 ↩
- 斯蒂芬·A·库克(Stephen A. Cook)和罗伯特·A·雷克豪(Robert A. Reckhow),《有界时间随机存取机》(Time Bounded Random Access Machines),1972年 ↩
- D. A. 特纳(D. A. Turner),《全函数编程》(Total Functional Programming),2004年 ↩
- 我需要指出的是,全函数性——尤其是在函数式语言中——可能有其用途;但使验证更容易并不是其中之一。 ↩
- 斯蒂芬·贝兰托尼(Stephen Bellantoni)和斯蒂芬·库克(Stephen Cook),《多项式函数的新递归理论特征化》(A New Recursion-Theoretic Characterization of the Polytime Functions),1992年 ↩
- S. 德姆里(S. Demri)、F. 拉鲁辛尼(F. Laroussinie)和Ph. 施诺贝尔(Ph. Schnoebelen),《模型检测中状态爆炸问题的参数分析》(A Parametric Analysis of the State-Explosion Problem in Model Checking),2005年 ↩
- 皮埃尔·施诺贝尔(Philippe Schnoebelen),《时态逻辑模型检测的复杂性》(The Complexity of Temporal Logic Model Checking),2002年 ↩ ↩ 2
- 拉杰夫·阿卢尔(Rajeev Alur),《分层状态机的形式分析》(Formal Analysis of Hierarchical State Machines),2003年 ↩
- 埃德蒙·M·克拉克(Edmund M. Clarke),《模型检测:我27年克服状态爆炸问题的探索》(Model checking: my 27-year quest to overcome the state explosion problem),2007年,以及《模型检测中状态爆炸问题的进展》(Progress on the State Explosion Problem in Model Checking),2001年 ↩
- 斯蒂芬·A·库克(Stephen A. Cook)和罗伯特·A·雷克豪(Robert A. Reckhow),《命题证明系统的相对效率》(The Relative Efficiency of Propositional Proof Systems),1979年 ↩
- 有关介绍,请参见 Patrick Cousot 的《Abstract Interpretation Based Formal Methods and Future Challenges》(2001)。关于抽象与精化的通用理论的精彩且易读的概述,可参见 David A. Schmidt 的《Binary Relations for Abstraction and Refinement》(1999)。↩
- 类型系统专家可能希望阅读以下两篇论文:Patrick Cousot 的《Types as Abstract Interpretations》(1997)和 Roberta Gori、Giorgio Levi 的《An experiment in type inference and verification by abstract interpretation》(2002)。这些论文远超我的理解范围。↩
- 如需全面概述,可参见 Jean-Yves Girard 的《Proofs and Types》(1989)。↩
- Xavier Leroy,《Desperately seeking software perfection》,2015年10月20日。↩
- F. P. Brooks,《No Silver Bullet: Essence and Accidents of Software Engineering》,1986。↩
- 实际上,Brooks 曾写道:“无论是技术还是管理技术,都没有任何单一的发展能在十年内将生产力、可靠性或简单性提高一个数量级。”鉴于三十年来,即使将所有发展综合考虑,生产力仍未提高一个数量级,且考虑到 Brooks 后来将他的非正式预测视为自然定律,我允许自己进行简化转述。↩
- F. P. Brooks,《No Silver Bullet, Refired》,《The Mythical Man-Month, Essays on Software Engineering, Anniversary Edition》,Addison-Wesley,1995年,第213页。↩
- Ding Yuan 等,《Simple Testing Can Prevent Most Critical Failures: An Analysis of Production Failures in Distributed Data-Intensive Systems》,2014。↩
- Juris Hartmanis,《Some Observations About the Nature of Computer Science》,1993。↩