可计算性和计算复杂度

虽然很多人都知道, 但是第一个将这样的想法写成书籍的恐怕是Neil Jones. 也就是说, Turing机器和Gödel配数其实可以看成是很难用的编程语言, 没有必要局限于此, 我们可以使用真正的编程语言刻画想法, 进行证明.

前言

本书是对于可计算理论和复杂度理论的一般性介绍. 它应该对于想要了解可计算理论和复杂度理论的编程语言研究者而言是有趣的, 或许反过来也是一样.

俯瞰主题

与绝大多数计算机科学领域都不相同, 可计算理论和复杂度理论既处理综合也处理分析, 并且与某些显然带有绝对性质的概念打交道. 过去近一个世纪的逻辑学和递归函数论的进展已经相当精确地刻画了有效过程 (effective procedure) , 可判定问题 (decidable problem) 和半可判定问题 (semi-decidable problem) 的概念和性质, 并且以本质上相对于所用计算设备和逻辑理论不变的方式建立了它们.

令人惊讶的是, 一些类似的不变概念也从有界资源计算中诞生: 多项式时间 (作为判定问题的输入规模的函数), 多项式存储, 带或不带非确定性的计算 (非确定性即一种"猜"的能力), 以及仅有"只读"数据访问能力的计算.

不仅是理论研究者会对于可计算理论和复杂度理论感兴趣, 编程实践者也应该关心它们. 例如, "复杂度下界"的角色就类似于工程中的信道容量: 不管编码有多聪明, 界就不可能被克服.

不幸的是, 人们对于这种领域的印象就是不可理解的基础定义, 定理证明, 甚至对于定理和问题定义的陈述也不那么简单. 以我之见, 这在某种程度上是一种历史债. 若是我们能够从面向Turing机器和Gödel配数的古典方法转向更多使用编程语言概念的道路, 想必这能将可计算理论和复杂度理论的传统结果渲染得更平易近人, 而且也使得那些非常强的定理更加容易从直觉上理解, 更加容易应用到实际问题上来.

本书包含了计算的古典模型和可计算理论与复杂度理论里的核心结果. 然而, 在以下两个方面上, 其与传统文献迥然相异:

  1. 本书显然更加容易理解, 但并不牺牲精确性, 这是因为我们呈现可计算理论和复杂度理论的方式运用了编程技术, 并且受到了编程语言理论的启发.
  2. 本书缓解了复杂度理论中的特定结果与日常编程实践之间的长久以来的一种紧张感. 这种更好的匹配是通过一种新颖的计算模型完成的, 其与传统模型在特定的重要方面有所不同.
而且, 许多古典理论中繁琐的 (baroque) 构造在编程的上下文中变得异常简单, 有时甚至将我们引向更强的结果, 其后果是许多通常只能草绘大概的构造现在可用更加精确和令人信服的方式完成.

The perspective of the book

对于那些已经熟悉可计算理论和复杂度理论的人而言, 以上两点可以阐述得更加具体.

对于第一点, 我引入了一个非常简单的编程语言WHILE, 其基本上就是Pascal或者LISP的一个很小的子集. WHILE语言似乎是表达力和简单性的精当混合. 当我们将程序作为数据对象处理时, 表达力是重要的. WHILE的数据结构特别适合于编码程序文本, 这避免了Gödel配数的技术性灾难, 而几乎所有以前的文献都使用了Gödel配数. 简单性对于证明关于程序及其性质的定理而言也是重要的, 因为太过复杂的语言难以全然理解.

从更一般的角度来说, 我认为可计算理论和复杂度理论以及编程语言和语义学之间有很多可以提供给对方的洞察. 从一个方向上说, 可计算理论和复杂度理论的广度, 深度, 一般性是目前的编程语言理论中尚且很难见到的, 并且一个传统在于提出整个学界都感兴趣的精确定义的开放问题. 更进一步来说, 和解决特定关于程序的问题的程序的内蕴不可行性有关的一些问题对于编程语言研究者而言应该也是很有趣的. 例如, 许多出现在程序分析和转换领域中的问题都被证明是不可判定的或者具有无法克服的高复杂度.

从另一个方向上来说, 编程语言界对于设计, 呈现, 实现算法具有坚实的理解, 并且建立了诸多框架以精确地刻画各种编程语言概念的语义, 这些编程语言概念包括函数式编程, 逻辑编程, 命令式编程, 控制运算符, 通信和并发, 面向对象等等. 而且, 编程语言所构造的计算模型往往在某些特定的重要方面比那些传统的计算模型更加切实.

以下是可计算理论和编程语言之间的一个具体联系. 自1930年代起, 可计算理论中的枯燥无味的"s-m-n定理"就已经为人所知, 但是似乎只是在特定证明中有用的一个技巧而已. 然而, 令许多人惊讶的是, 在过去的20年间, s-m-n定理以部分求值或者说程序特化的别名证明了其自身的价值: 当部分求值器被有效实现时, 其可以用来进行实际编译, 而当其应用于自身时, 其也可以用来生成程序生成器.

译者注记. 所谓的生成程序生成器, 实际上指的是第三二村投影, 即将部分求值器应用于自身时, 可以得到一个编译器生成器, 其以解释器作为输入, 而以编译器作为输出.

可计算理论的另一块基石, 即"通用机器", 无非就是一个自解释器而已, 这在编程语言界是众所周知的概念. 而且, 在可计算理论和复杂度理论的导论里, "模拟"通常是藉由非形式化的编译器或者有时是解释器达成的.

对于前文的第二点, 长久以来可计算理论和复杂度理论与"实际计算"之间的紧张, 至少有一部分原因是在于所谓的Turing机器加速定理, 这是复杂度理论中最早被证明的结果之一. 这个定理断言了一个反直觉但却正确的事实: 任意的Turing机器程序, 若能在超线性时间内运行完成, 则其可被替换以一个等价的程序在极限意义下以两倍的速度完成. 编程语言理论中有效自解释器的存在性则将我们引向了相反的结果: 一种层次定理表明, 对于一种比Turing机器更加实际的计算模型而言, 常量时间因子的确是重要的. 更精确地说, 给定时间界f⁡(n), 其中n度量了问题输入的规模, 那么存在问题可在时间(1+ε)⁢f⁡(n)内解决但是却不能在时间f⁡(n)内解决. 因此, 给可用时间乘上一个常量因子的确真扩大(properly increase)了可被解决的问题类.

这样或那样使用编程语言概念的例子产生了可计算理论和复杂度理论领域中更加容易理解的定理陈述与证明 (至少对于计算机科学家而言), 甚至是更强的结果. 这些更深刻的结果包括对于著名的问题类LOGSPACE和PTIME的"内蕴"刻画, 其只依赖于程序的句法本身, 而无需借助于任何外部指定的空间或者时间界.

最后我们想说的是, 在这种角度下, 许多旧有的可计算理论和计算复杂度问题重获新生, 而一些新的问题又自然而然出现了. 一类重要的新问题 (尽管尚没能完全解决) 是: 我们所采取的编程风格, 例如函数式, 命令式, 对于我们所写的程序的效率有何影响?

如何阅读本书

预备要求

预期的读者是已经学习过某种理论的研究生新生, 或者是具备良好数学成熟度的高年级本科生. 具体来说, 本书自由地运用了集合, 函数, 图, 递归定义等概念. 虽然这些概念在附录里都有解释, 然而其太过紧凑而不适合用作导引. 熟悉某种编程语言是必要的, 然而至于是何种语言则并无所谓.

简而言之, 本书的新颖之处

本书关于古典可计算理论的结果包括停机问题的不可解性, 以及一些其他自然的问题, 诸如上下文无关歧义和Hilbert第十问题; Rice关于所有非平凡外延性程序性质均不可判定的结果; 对于递归函数, 递归集合, 递归可枚举集合的刻画; Kleene的s-m-n定理, 第二递归定理, 正规形式定理; 基于不动点的递归; Rogers的同构定理; Gödel的不完备定理.

古典复杂度理论的结果则包括

和关于可计算理论与复杂度理论的传统书籍相比, 我们的处理具有以下特色:

  1. WHILE语言, 带有类似LISP的数据. 优点: 在牵扯将程序作为数据的构造上既方便又可读; 免于存储管理的烦扰.
  2. 与大家熟知的计算机科学概念的强烈关联: 编译 (模拟), 解释 (通用程序), 程序特化 (s-m-n定理), 最优程序的存在与否.
  3. 自应用和编译器自举的关系.
  4. 程序特化以加速程序运行的部分求值的形式出现, 或者以通过特化解释器来编译或者生成编译器的形式出现.
  5. 对于基础概念的"健壮性"的更简单的构造, 包括函数式语言和lambda演算.
  6. 一种证明Kleene第二递归定理的构造, 其给出的程序远比传统证明有效.

第一部分 迈向理论

第1章 导引

本书是关于可计算理论和复杂度理论的. 在这第一章里, 我们想要去传达 (convey) 可计算理论和复杂度理论的疆界和技巧. 本章我们有意写得非形式化; 甚至在某些时候我们将会引入不甚严格的定义或者命题, 它们依赖于特定的直觉性想法.

第1.1节 可计算理论的疆界和目标

可计算理论会问这样的问题: 是否存在任何有效过程均不可解的问题? 或者更不严格地说, 是否存在这样的一个问题, 其在任何计算机上以任何可以想象到的编程语言的任何程序都无法解决?

我们的编程直觉或许会给出否定的答案, 因为我们的经验告诉我们, 一旦一个问题被以specification的形式精确定义, 那么编写满足specification的程序就或多或少成为了一个常规的任务. 诚然如此, 类似的一种直觉也占据了Hilbert关于数学基础的工作, 见第1.6节: 他们预设一切的数学都可以被公理化. 然而, 我们将发现这些直觉都错得离谱. 的确有不能被有效过程解决的问题.

为了证明这点, 我们必然需要精确定义什么是有效过程, 什么是问题. 任何对于有效过程的单一形式化是否就足够了呢, 这并非先验. 似乎, 任何特定的选择都太过狭隘, 因为其会排除具有特定能力的其他计算设备. 因此, 不同的选择或许会导致不同的可计算理论. 然而, 可计算理论领域里的最重要的一个洞察在于1930年代的人们逐步认识到的一个事实, 即对于有效过程的概念的形式化的任何理智的选择都会在某种意义上导致相同的理论. 此即所谓的Church-Turing论题, 这是因为Alonzo Church和Alan M. Turing最早陈述并证明了这种洞察的一个版本. [译注: 与其说这是一个命题, 不如说这是一种指导思想.] 解释为何不同的形式化会导向相同的理论本身就是可计算理论的重要主题之一, 因而我们在这方面也花了很多精力.

在有对于问题和有效过程的精确定义的保证下, 可计算理论关心的是可计算和不可计算之间的分野, 并试图解决以下问题:

如果一个问题可被一个有效过程解决, 那么我们称其是有效可解的, 或者就说是可解的. 一个问题的不可解性并非完全负面的结果, 因为这意味着寻找解决问题的有效过程的行为只可能是徒劳.

在接下来的两节里, 我们将讨论有效过程和问题的概念的形式化. 在此之后, 我们将非形式化地呈现可计算理论的一些初等结果, 其中包含两个被精确陈述的不可解问题.

第1.2节 什么是有效过程?

为了形式化有效过程的概念, 我们可以采取各种各样的策略. 当然, 我们可以按照我们自己的喜好自由地定义概念, 只是这个定义必须捕获对于有效过程的直觉性想法. 例如, 不应该出现以下情况: 某个问题根据我们的理论是不可解的, 然而在一个真实世界里的计算机上却是可以被解决的. 因此, 这个形式化所刻画的有效过程恰好也应该是我们直觉上有效的过程.

第1.2.1小节 Alan Turing对于计算的分析
第1.2.2小节 Church-Turing论题

在Turing的分析中所提及的机器被称为Turing机器.

除了Turing机器, 还有其他对于有效过程概念的形式化, 例如

尽管它们有着相当的不同, 但其实也共享一些特征 [155]:

  1. 一个有效过程是通过一集有限长度的指令给出的, 只有有限多个不同的指令.
  2. 计算是以离散的按步风格执行的, 不使用连续方法或者模拟设备.
  3. 计算是以确定的方式执行的, 不采取随机方法或者随机设备, 例如骰子.
  4. 对于存储空间和时间没有先验的固定边界, 但是终止的计算不能依赖于无限的空间或者无限的时间.
  5. 每个计算步骤只牵涉有限数量的数据.

以上这些有限过程的概念的形式化实际上是等价的. 因此, 有时Church-Turing论题以如下形式表达:

  1. 所有对于有效过程的直觉概念的合理形式化都是等价的;
  2. Turing机器可计算性是对于有效可计算性的一个合理形式化.

为了支持这个观点, 之后的章节里我们会考虑许多不同的形式化并且证明它们都是等价的. 不过, 对于本章的剩余部分, 有效过程或者算法的概念将维持直觉性的观念.

第1.2.3小节 算法是硬件还是软件?

讨论算法是硬件还是软件的问题有点类似于讨论先有鸡还是先有蛋, 但是这的确是值得的, 因为关于可计算理论和复杂度理论的材料, 特别是复杂度理论的材料, 都隐含地偏向其中一种观点. 例如, "Turing机器"携带了硬件的弦外之音, 而Turing的论证中的"心灵的状态"似乎对应于机器的状态.

硬件观点认为算法是实现意图的计算的机能装置的一部分. "指令集"是对于其架构的刻画. 在任何一个时间点整个机器的状态由其正在执行的指令和其存储状态构成. 更大的算法对应于更大的硬件.

不限制存储的量的问题可以用多种方法解决:

最后一种方法与所谓的电路复杂度有关. 人们通常要求序列M1,M2,…是一致的, 于是更大的数据不会由迥然相异的机器处理.

软件观点认为算法是指令的集合或者序列. 例如, 一个算法可以是以某人最爱的编程语言写成的程序. "计算代理"然后解释算法; 这可以是一块硬件, 但也可以是软件的: 以某个低层次语言写成的解释器程序. 从操作的角度来看, 一个解释器维护了一个到当前指令的指针, 以及对于算法的当前存储状态的表示. 更大的算法对应于更大的被解释程序, 但是解释器本身仍然是固定的, 不论是硬件还是程序.

最初完全自动的计算机器是von Neumann的"存储程序"机器.

第2章 WHILE语言

导引章节的概念 (例如"有效可计算") 是不精确的, 因为它们依赖于对于"有效过程"的直觉性理解. 现在我们呈现一个计算模型, 或者说编程语言, 其被称为WHILE. 之后我们将精确地定义前一章的直觉性概念, 通过将"有效过程"和"WHILE程序"等同起来.

第2.1节 WHILE数据和程序的句法

第2.1.1小节 作为数据值的二叉树
定义2.1.1. 树的集合𝔻定义如下:
  1. 原子nil是𝔻的一个元素;
  2. 每当d1和d2是𝔻的元素, 那么(d1,d2)也是; 并且
  3. 𝔻是满足前两点的最小集合.
定义2.1.2. 函数
第2.1.2小节 WHILE程序的句法

第3章 程序作为数据对象

第二部分 可计算性导论

第4章 自解释: WHILE和I的通用程序

第5章 可计算理论基础

第5.1节 可计算性, 可判定性, 可枚举性

定义5.1.1. 一个部分函数f:𝔻→𝔻⊥是WHILE可计算的当且仅当存在一个WHILE程序p使得f=⟦p⟧, 即对所有d,e∈𝔻:
  1. 如果f⁡(d)=⊥, 那么⟦p⟧⁡(d)=⊥.
  2. 如果f⁡(d)=e∈𝔻, 那么⟦p⟧⁡(d)=e.

集合A是可判定的, 如果关于A的成员资格问题可由一个总是终止的程序回答.

第6章 元编程, 自解释和编译器生成

第7章 计算的其他顺序模型