这个系列当算是去年「说说数理逻辑」那篇的后续吧。在上一篇中，我们最后以哥德尔不完全性定理作为结尾，并给可计算性与可判定性问题开了个头，于是过渡到理论计算机科学这一领域。在这个系列的文章中，我们简单地对理论计算机科学的基础内容做一浅显的介绍。理论计算机科学大致分为三个部分内容：可计算性理论，形式语言与自动机，以及计算复杂性理论。这篇先介绍第一部分，即可计算性理论…的第一部分。
可计算性的定义
问：计算机的功能是什么？
答：计算。
问：啥叫计算？
答：就是那个，汇编指令一条一条执行的过程（？）
当然，这样的回答并不是针对理论计算机科学而言的，而是针对计算机技术而言的。正如数理逻辑中语法和语义之间的关系一样，实体的计算机是一种在语义上能正确运作的机器，而与之相对应的语法上形式的计算机，即计算模型，才是理论计算机重点讨论的对象。或者说，实体的计算机是计算机的实然状态，那么计算机的应然状态应该是什么？
这是个好问题。我们对计算的形式化定义必须满足可靠性和完全性两个条件，可靠性即指满足这个定义条件的事物都属于这个概念的范围，完全性即指属于这个概念范围的事物都必须满足这个定义条件。这可不是一件容易的事情。
二十世纪以来，数学家们提出了一系列计算模型，包括图灵机、递归函数、文法、λ 演算等等，其中图灵机想必应该是最出名的一种机器了。所谓图灵机，粗糙地说，就是能在一条纸带上涂涂写写的机器，最后算出一个结果留在带子上作为输出。
噢，听起来就像是一个机器人在纸上拼命算积分的场景，和大学生做计算题有那么几分相似。当然上面这说法太粗糙了，相对准确的定义应该这么说：图灵机有有限多个状态，一条无穷长的纸带，和一个指向纸带的可移动读写头，图灵机在每一步都可以决定自己在状态 q，以及读写头指向位置处内容为 x 时下一步应如何进行，可选择的动作包括将该处的内容改为 y，左移读写头，或者右移读写头。
图灵对自己的机器感到非常满意，并由此给出了图灵机的形式化定义：
M = (Q, Γ, b, Σ, δ, q0, F)
完了，这个式子一出来读者全被吓跑了。我们这里不打算仔细说明它，它的具体含义可以参见维基百科 - Turing machine。
好，所以我们现在有了一个关于计算的形式化定义。那么回到前面的问题，这样的定义是可靠的吗？图灵机结构这么简单，所做的不过是改改内容和动动读写头，计算机当然都可以实现。
这样的定义是完全的吗？图灵机结构这么简单，我们认为计算机可以完成的计算任务，图灵机都有能力完成吗？或者换一种说法，图灵机能够实现所有算法吗？这似乎并不容易回答。
考虑一下如何只使用改内容和移动读写头这两种操作来实现解决下面问题的算法：
- 判断一个字符串中 a 和 b 的个数是否相同
- 给定正整数 a 和 b，求 a 的 b 次方
- 求两个正整数的最大公约数
1
2
3
4
5
（留白思考区）
好了不为难你了，实际上这些都是可以做到的（证明留给读者嘻嘻）。那么对于更多更复杂的计算任务，图灵机是否都有能力做到呢？
图灵说：你居然敢质疑我的机器？于是我们就有了下列丘奇-图灵论题（Church-Turing thesis）：
所有可计算的函数都是图灵机可计算的。 ——Church & Turing
我靠这不是耍赖吗？你凭啥说你这个小机器能解决所有的计算问题？证据呢？
正常人都会这么质疑，这属于合理怀疑。不过，如果你怀疑图灵机不行，可不可以给出一个大家直觉上觉得肯定可以计算的函数，使得图灵机无法计算呢？
到目前为止，这样的计算任务都还没有被发现。当然这并不意味着丘奇-图灵论题就是正确的，实际上这个论题的正确性是没有办法论证的，其原因就在于，直觉上可计算的函数并不是一个良定义的概念，也正因为如此，我们才需要一个计算的形式化定义来为“可计算”这一性质作出合理的界定。所以，我们称上面的表述为丘奇-图灵论题，而非丘奇-图灵定理。
至于为什么论题里还会冠名丘奇这个人，是因为丘奇（比图灵早一年）提出了 λ 演算作为计算模型，并且宣称所有可计算的函数都可由 λ 演算定义。后来发现它和图灵机的计算能力是相同的，所以这两个人的论断实际上说的是同一回事，于是就合并为一个论题了。
诶等会儿，我们退一步说，你怎么说明你的图灵机是对可计算性的一种合理的刻画？
张立昂教授在其编著的「可计算性与计算复杂性导引」一书中提出了另一种和程序语言更为相近的计算模型，称之为 S 语言。在 S 语言的程序中，只能使用以下三种语句：
- 自增语句，即 x = x + 1
- 自减语句，即 x = x - 1（x = 0 时不往下减）
- 条件跳转，即 IF (x != 0) GOTO A（A 为标签）
熟悉程序设计（和汇编语言）的读者很容易意识到，这些简单的操作足以完成所有 C 语言程序的功能。而且可以证明（也可以想象），这样的 S 语言可计算的函数类和图灵机可计算的函数类是一样的。事实上，张教授的书中就是先介绍 S 语言，后介绍图灵机的，这样的编排应该能让程序员们对可计算性有个更自然和直观的认识。
你现在有点相信图灵机的合理性了吗？相比起人们暂时没有找到直观可计算，而图灵不可计算函数的反例这一说辞而言，许多风格迥异的计算模型最终都与图灵机有着完全相同的计算能力，这样的证据更能让人相信图灵机计算能力的强大。
下面是一些风格迥异的计算模型的简单介绍（看不懂也没关系，毕竟每一个都可以写很长）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A. λ演算
使用两种函数手段
abstraction (λx.M)，表示输入 x 返回 M 的一个函数
application (M N)，表示函数 M 以 N 为输入的结果
以及两种归约手段
α-conversion (λx.M[x]) → (λy.M[y])，即约束变元换名
β-reduction ((λx.M) E) → (M[x:=E])，即自由变元替换
B. 递归函数
使用三种初始函数
零函数 zero(x) = 0
后继函数 succ(x) = x + 1
投影函数 proj_j (x_1, ..., x_n) = x_j
以及三种递归运算
复合、原始递归和极小化
C. 文法
对起始变元不断使用一些产生式进行字符串的替换
最终得到所有字符串的集合作为接受的语言
（这个要简短地解释清楚实在是太难了，请参见维基百科 - Formal grammar）
从中可以看到，各路数学家、语言学家、计算机科学家都在为给出一个令人满意的可计算性的形式化定义而努力，但最终发现这些模型的计算能力全都与图灵机相同。这是一件不可思议的事情，仿佛图灵机已经把我们可计算函数的范围给全都罩住了。所以，在可计算性理论中，我们一般认为丘奇-图灵论题总是成立的，这一论题成为可计算性理论的基础与核心，后续一切定理都在此基础之上进行论证。
哈，你不会到这里真的相信丘奇-图灵论题成立了吧？毫无疑问，我们依然有千万种理由来否认丘奇-图灵论题，包括但不限于：死皮赖脸否认法、直觉主义否认法、普遍怀疑否认法等等（三头雾水）。
那么一个需要思考的问题是：我们平时与实体计算机相关的经验，是否限制了我们对可计算函数的认识？正如胡塞尔在「纯粹现象学通论」一书中所阐述的那样：
普遍而言，每一个别存在都是“偶然的”。它如是存在着，就其本质而言它可以不如是存在。即使存在有某些自然法则，按照该法则某种实在状况事实上存在，那么某种确定的结果事实上也必定存在：这些法则只是表现了事实性规则，这些规则本身完全可能是另外一种样子，而且它们已假定，按照从一开始就属于可能经验的对象的本质，由这些法则所支配的可能经验的对象，就其本身而言仍然是偶然性的。
但是这种被称作事实性的偶然性的意义是有限制的，因为它与一种必然性相关，此必然性并不意味着在诸时空事实间并置关系的有效规则这种纯事实性的组成，而是具有本质必然性的特性，并因此具有一种涉及本质一般性的关系。当我们说，任何事实“按其自身本质”可以是其他样子时，我们已经是在说，每一偶然事物按其意义已具有一种可被纯粹把握的本质，并因而具有一种艾多斯（eidos）可被归入种种一般性等级的本质真理。
——Edmund Husserl
总而言之，当下的实体计算机（就计算的本质而言）不应当是计算机的唯一实现方式。当我们把对现代计算机的认识与态度进行悬搁之后，可计算性的本质又应当如何被把握？人们是否有能力造出比图灵机计算能力更强大的计算模型？
那么首先，我们需要认识到，图灵机并不是万能的——的确存在图灵机无法计算的函数，其中最著名的当属停机问题（halting problem），即问是否存在这样一台图灵机，它能够判断任何一台图灵机对给定的输入是否停机？
答案是否定的，不存在这样的图灵机（关于不可计算函数我们下次再聊）。所以，图灵机的局限必然是有的。由此引发的研究如何打造一种计算模型，使之能够拥有比图灵机更为强大计算能力的理论计算机学科分支，就称为超计算（hypercomputation）。
超计算模型，可以说是数学家和计算机科学家脑洞的天堂了，一些典型的超计算模型如下：
- 图灵自己提出的谕示机（oracle machines）。在图灵机的基础上，增添了一个能解决某个计算任务的 oracle 来辅助，这个 oracle 解决的问题不必是图灵可计算的，你也不知道它是怎么算出来的，反正它就是能算，不服你就打我啊。当然在现实中还是有可能实现的，例如一个事先给定的数据库，任何一个输入都可以在数据库中找到一个与之相匹配的输出。
-
Blum-Shub-Smale 机。允许计算机存储无限精度的实数，注意由于图灵机只能存整数，所以与现在计算机中的浮点数类似，图灵机只能表示实数的近似，但图灵机的空间是不受限制的，所以可以以任意精度逼近任意的可计算实数。这个 BSS 机还有一点很有意思，它可以把计算推广到任意的环上。
-
受芝诺悖论启发的芝诺机，允许图灵机在有限的时间里计算无限的步数（这里无限包括任意的无穷序数），比如，我能计算 π 的最后一位数字。但这样的机器将导致在有限时间之后，机器的状态在逻辑上无法确定。
-
量子计算机。一些理论科学家认为，如果利用量子计算机使用无穷多个叠加状态，可以实现图灵不可计算函数的计算。不过现实的量子计算机是达不到这一点的，而且其计算能力有上限，称为布莱梅曼极限（Bremermann’s limit）。
- 利用相对论或 Malament-Hogarth 时空等来实现有限时间的无穷计算。
……
计算机科学家都疯了。
不过，这些超计算模型在实现世界中基本是造不出的。我们目前的实体计算机，由于存在空间上的限制，实际上还比图灵机弱一些。所以，从这个角度来说，图灵机可以认为是理论与实践之间关系最紧密的模型了，超计算模型可以看成是对计算的哲学性探讨，而接受丘奇-图灵论题，对于实际的计算机技术发展，以及算法设计与研究都是非常有必要且有重要意义的。
好，关于可计算性的定义就说到这儿，我们下回再见。
