SEP：可计算性与复杂性（一）

本文使用 Zhihu On VSCode 创作并发布

SEP:可计算性与复杂度（Computability and Complexity）

*由L. T. F. Kanud of Vihara译出(译： cjy、校： 虎猫(第一节到第三节)， 羽川翼(第四节))

曾载于豆瓣： douban.com/note/7850701...

*作者 Neil Immerman (immerman@cs.umass.edu)是马萨诸塞大学的一位理论计算机科学家，1995年哥德尔奖获得者，描述复杂性(descriptive complexity)理论的主要开发者之一。

*参考文献部分请参原文: plato.stanford.edu/entr...

*本文是一篇关于， 图灵机， 丘奇-图灵论题，递归可枚举， 递归函数等关键概念，与计算理论中的可计算性理论及 计算复杂性理论的，简单而优秀的科普。上面给出了有进一步专门词条的超链接，有兴趣的或许可做进一步阅读。

First published Thu Jun 24, 2004; substantive revision Wed Sep 2, 2015

一个数学问题是可计算的(computable)，当其原则上是可由一个计算手段解决的(computing devices)。关于“可计算的”的一些常见同义词是，“可解的(solvable)”，“可判定的(decidable)”，“递归的(recursive)”。希尔伯特相信所有数学问题都是可解的，但是在1930年代，哥德尔，图灵，丘奇，表明事实并不如此。而这里就会有一个广泛的研究与分类是关于，哪些数学问题是可计算的，而哪些不是。另外，根据这个问题的计算量，有一个广泛的分类，将可计算的问题分为到不同的计算复杂性类(computational complexity classes)中，而计算量指，需要多少计算去回答问题的实例，根据于该问题实例的大小。令人惊讶的是，被描绘出的这些分类是如此的清晰，优雅与精确。

目录

•1. What can be computed in principle? Introduction and History

•2. Turing Machines

o2.1 Universal Machines

o2.2 The Halting Problem

o2.3 Computable Functions and Enumerability

o2.4 The Unsolvability of the Halting Problem

•3. Primitive Recursive Functions

o3.1 Recursive Functions

•4. Computational Complexity: Functions Computable in Practice

o4.1 Significance of Complexity

•Bibliography

•Academic Tools

•Other Internet Resources

•Related Entries

1. What can be computed in principle? Introduction and History

在1930年代，也就是远在计算机被发明出来之前,世界各地的数学家发现了关于，“什么是可计算的”这个东西的，精确与独立的定义。丘奇定义了lambda演算(lambda calculus)。哥德尔定义了递归函数(recursive functions)。斯蒂芬克莱尼定义了形式系统(formal systems)。马尔可夫定义了被人们熟知的马尔可夫算法(Markov algorithms)，波斯特与图灵定义了现在被人们熟知的波斯特-图灵机(Post machines and Turing machines)的抽象的机器。

令人惊奇的是，所有这些模型都是精确相等的：所有在lambda演算中是可计算的，在图灵机中也是，并且对于上述所有系统的其他对子来说也都是如此。在此被证明之后，丘奇表示，“原则上可计算”这个直观概念，可以被定义为上述的精确概念。这个信念，现在被称作丘奇-图灵论题(Church-Turing Thesis)，并被数学家们统一接受。

编纂什么是可计算的，的部动力来自于数学家大卫希尔伯特。希尔伯特相信，所有数学都能被精确地公理化(axiomatized)。他认为，一旦做到这一点，我们就将有一个“能行的程序(effective procedure)”，即，一种算法，它将任何一个精确的数学陈述作为输入，经过有限步之后，决定这个数学陈述是正确的还是错误的。希尔伯特现在要的就是，对所有的数学去进行判定的这样一个判定程序(decision procedure)。

作为判定问题的一个特殊的例子，希尔伯特考虑了一阶逻辑的有效性问题(validity problem)，一阶逻辑是一个可以形式化大多数数学陈述的数学语言。任何一个一阶逻辑中的陈述，在任意适合的逻辑结构中，都有一个精确的意义，即，其在任何一个这样的结构中，要么为真要么为假。那些在所有适合的结构中都为真的陈述被称为有效的。那些在某个结构中为真的陈述被称为可满足的(satisfiable)。注意，一个公式φ是有效的，当且仅当，其否定¬φ是不可满足的。

希尔伯特将一阶逻辑的有效性问题称为判定问题(entscheidungsproblem)。在一本希尔伯特与阿克曼所著的教科书上(Principles of Mathematical Logic)有这样写道，“当我们掌握了一个程序，其允许，在有限步的运算中能够判定，任何被给定的逻辑表达式是有效的或者可满足的时，我们就解决了判定问题……而判定问题必须被考虑作数理逻辑的主要问题” (Böerger, Grädel, & Gurevich 1997)。

哥德尔在他1930年的博士论文中，基于罗素与怀特海的《数学原理》(Principia Mathematica)，提出了一阶逻辑的完全公理化。哥德尔证明了他的完全性定理(Completeness Theorem)，即， 一个式子是可由公理证明的，当且仅当其是有效的。哥德尔的完全性定理跨出了朝向解决希尔伯特判定问题的一步。

特别地，由于公理很好辨别并且推理规则也很简单，我们就将会有一个机械化程序可以列出所有的证明。注意，在证明中，每一行，要么是公理，要么是经由其中一个推理规则从前面的行中所推出的。对于任何给定的字符串，我们都可以辨别其是否是一个证明。这样，我们便可系统性地列出所有长度为1，2，3等等的符号串，然后检查它们是否是一个证明。如果是，那么我们就可以将证明中的最后一列加入到，定理的列表中。这样，我们便可列出所有证明，即，通过一个简单的机械化程序，能准确地列出所有一阶逻辑的有效式。更精确地说，有效式的集，就是可计算函数(computable function)的值域。用当代的术语来说就是，一阶逻辑有效式的集是，递归可枚举的(recursively enumerable(r.e.))

然而，哥德尔完全性定理对于给出一个判定问题的明确解答来说并不充分。给定一个式子，φ，如果φ是有效的，那么上述程序最终将会列出它，并且给出“是，φ是有效的”这样一个答案。然而，如果φ不是有效的，我们可能终究都不会得到这个事实。现在缺少的就是一个程序，去列出所有非有效式，或者等价地去列出所有可满足的式子。

一年后，也就是1931年，哥德尔提出了他的不完备性定理(Incompleteness Theorem)震惊了整个数学界：我们没有完全的且可计算的，关于自然数的一阶理论的公理化。这意味着，没有这样一个合理的列表，我们可以从中准确地证明出所有数论中的真命题(Gödel 1931).。

几年之后，丘奇与图灵独立证明了判定问题是不可解的。丘奇通过运用哥德尔不完备性定理中的手段，展示了，一阶逻辑的可满足的公式集不是递归可枚举的，即，它们不可被系统化地，经lambda演算的可计算函数列出。图灵引入了他的机器，并证明了许多我们将在下一节中会讨论到的有趣定理。特别地，他证明了停机问题(halting problem)是不可解的。同时作为推论，他也得到了判定问题同样也是不可解的。

希尔伯特非常失望，因为他的计划，关于所有数学判定程序，被证明为是不可能的。然而，如我们将要看到的那样，我们将会学到大量关于计算的基础性质的知识。

1. Turing Machines

在图灵1936年的论文(On Computable Numbers, with an Application to the Entscheidungsproblem)中，他引入了这个机器，并奠定了它们的基本性质。

他清晰而理论性地给出了什么是，机器执行计算任务，的意义。图灵如下定义了他的机器：

• 一个有限的可能状态集Q，因为任何设备都必须处在，有限的可能状态的其中一个之下。

• 一个潜无穷的磁带，其由单元格σ₁，σ₂，σ₃组成，它们来自于某个有限字母表Σ；(Σ可以是包含至少两个符号的任意有限集。出于方便，可以固定Σ＝{0，1，b} ，即该字母表包含二进制字母再加上空白单元符。我们通常假设磁带的有限初始段包含二进制符号，而余下部分则为空白。)

• 一个磁带读写探头，h ≥ 1，扫描磁带的单元格σₕ；以及最后，

• 一个转换函数，δ：Q × Σ → Q × Σ × {–1，0，1}。(这个转换函数的意思是，从任意给定状态q，以及读取到的任意给定的符号，σₕ，δ告诉我们机器应该进入的新状态，应被记在当前方格中的新符号，以及下一个探头位置，h'＝h＋d，其中d ∈ {–1，0，1}是由δ给出的位移。)

与内存(随机存取存储器，random access memory)相比，存储磁带的线性性质是一个对运算速度的限制，但并没有限制其运算力：图灵机可以寻找到任意存储位置，即，磁带单元格，只是这可能会花些时间，因为其必须一步步地沿着磁带移动其探头。

图灵机的美妙之处在于，这是一个极其简单的模型，然而运算力却十分强大。图灵机具有潜无穷的工作空间，使其能够处理任意大的输入，比如，两个大数相乘，然而其每一步只能读取或者记录有限量的信息，即，一个符号。甚至在图灵机被证明，与其他关于计算的数学模型等价之前，以及丘奇图灵论题被表述之前，图灵就令人信服地表明了，他的机器和其他任何可能的计算设备一样强大。

2.1 Universal Machines

每一台图灵机都可以被唯一地描述为其转换表：对每一个状态q，以及每一个符号，σ，δ(q，σ)是一个新状态，新符号，以及探头位移。这些转换表可以被记作有限的符号串，以给出了每一台图灵机的完整指令集。进一步，这些符号串可以被如下地以词典顺序列出，M₁，M₂，M₃ . . .，在这里Mᵢ是转换表，即，完整指令集，对每个图灵机编号i，转换表Mᵢ就是图灵机的程序，或者更准确地说是iᵗʰ的程序。

图灵展示了他可以构造一台*通用的(universal)*图灵机，U，其可以运行任何其他图灵机的程序。更明确地，对于任意i，以及任意输入w，U在输入i与w时，将完全按照M_i在输入w时那样运行，用符号表示就是，

U(i，ω)＝Mᵢ(ω)

图灵对通用机的构造给我们了一个关于计算的最基础性的启示，一台机器就能运行其他任何程序。无论我们需要在未来执行什么样的计算任务，仅需一台机器就能够执行所有它们。图灵的这个见解使得搭建与销售计算机成为可能。一台计算机就能运行所有程序。我们不需要在要解决新任务的时候每次都买台新计算机。当然，在个人电脑的时代，这个事实已是个基本假定，以至于我们很难退后一步去重新审视它。

2.2 The Halting Problem

因为其被设计出来去体现所有可能的计算，图灵机有一个不可避免的缺陷，图灵机进行某些输入后将永远不会停机。其不能停机的某些原因十分愚蠢，比如我们可以对图灵机做出一个错误的编程，致使其进入一个紧凑循环(tight loop)，例如，在状态17中若读取到1，其可能会进入状态17并写下1，然后将探头移到0。不那么傻的是，我们可以到达一个空白符，其右边也全是空白符，同时也保持一直处在同一个状态——向右移动一格寻找一个“1”。这两个不能停机的例子，都可以被一个像样的编译器简单地检测到与修正。然而，考虑图灵机Mғ，输入“0”并系统性地搜索费马大定理(Fermat's last theorem)的第一个反例，当找到它时便输出这个反例并停机。而这直到最近安德鲁·怀尔斯(Andrew Wiles)证明了费马大定理之前，所有数学家工作了超过三个世纪都没能决定，Mғ输入0后，最终是否停机。现在我们知道了它永远不会停。

2.3 Computable Functions and Enumerability

既然图灵机在一定输入上可能不会停机，那么我们对于如何通过图灵机来定义可计算函数上便必须十分小心。让自然数N为一个集合{0，1，2，. . .}，并让我们把图灵机考虑作一个从N到N的部分函数

设M为一台图灵机，n为一个自然数，我们称M的磁带包含数字n，当，M的磁带以一个数的二进制表达开始(没有不必要的前导0)，而在这之后全是空白。

如果我们将图灵机M开始于含有n的磁带上，而它最终停机时，磁带含有m，则我们说M在输入n时计算出m。M(n)＝m 如果我们将M开始于输入n，而它或者不能停机，或者停机时，不含有一个自然数，比如它含有0或是中间有空白符，那么我们便说M(n)是未定义的(undefined)，用符号表达为： M(n)＝↗。如此，我们便可为每个图灵机M关联一个部分函数，M：N → N∪{↗} 。我们说这个函数M是全函数，当，对于所有n ∈ N M(n) ∈ N，即M(n)总是被定义的时。

现在我们便可形式化地定义，再之前非形式化描述过的，递归可枚举。若S ⊆ N，而S是递归可枚举的，当且仅当，我们有某个图灵机M，其使得S是经由M计算的函数的像，符号地，S＝{M(n)│n ∈ N；M(n) ≠ ↗}

这样，S是递归可枚举的，仅当，它可以被某个图灵机列出。若S是递归可枚举的，且其元素可由图灵机M像上面那样列举出来。这样，我们就可以描述另一个图灵机P，其在输入n时，以循环的方式运行图灵机M与其所有可能的输入，直到最终输出n。如果这发生了，那么P停机，并输出“1”，即，P(n)＝1，如果n ∉ S，那么，M将永远不会输出n所以P(n)也永远不会停机，即P(n)＝↗。

设P(n)↓意味着，图灵机P在输入n时，最终能够停机。对于一个图灵机P，定义L(P)，即P所接受的集合为，那些当输入进P而P能最终停机的，L(P)＝{n│P(n)↓}

上述论证表明，如果一个集合S是递归可枚举的，那么其可以被图灵机P接受，即S＝L(P)。这个式子的逆同样也成立。这样，S是递归可枚举的，当且仅当，它能被某个图灵机P所接受。

我们说一个集合S是可判定的，当且仅当，有一个全图灵机M，其可以判定，对于所有的n ∈ N，是否有n ∈ S，把值“1”作为是，“0”则为不是。对于所有n ∈ N，如果n ∈ S，则M(n)＝1，即，M在输入n上最终停机，并输出“是”，而如果n ∉ S，则M(n)＝0，即M在输入n上最终停机，并输出“否”。关于可判定的同义词是，可计算的，可解的，递归的。

对于S ⊆ N，S的补便是N – S，即，所有不在S中的自然数的集。我们说集合S是共递归可枚举的(co-r.e.)，当且仅当，其补是递归可枚举的且共递归可枚举的，然后我们可以在第一列中列出所有它的元素，而在第二列中列出所有它的非元素。通过这样的方式，我们可以判定，给定元素n，是否属于S，这只需要浏览一下这两行然后等着n出现就行了。如果其出现在第一行，那么n ∈ S，反之出现在第二行，就是n ∉ S。事实上，一个集合是递归的，当且仅当，它是递归可枚举的且共递归可枚举的。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。