当代计算机的源头，归根结底，还是数学家的结晶。今天向介绍的是计算模型，它包括但不限于这几个模型：图灵机、λ演算、递归、有限状态机

缘起

为什么我会对计算模型感兴趣？这其中有对计算机能表现出“智能”而感到的好奇，也有对它巨大威力的惊奇。但最为重要的、令我深究至此的直接原因，源自数学中对自然数的定义 —— 皮亚诺公理。

当然，对自然数的描述不止皮亚诺公理这一种，还有基于集合论的描述，这里暂不讨论。

皮亚诺的这五条公理用非形式化的方法叙述如下：

1. 0是自然数；
2. 每一个确定的自然数a，都有一个确定的后继数a’ ，a’ 也是自然数；
3. 对于每个自然数b、c，b=c当且仅当b的后继数=c的后继数；
4. 0不是任何自然数的后继数；
5. 任意关于自然数的命题，如果证明：它对自然数0是真的，且假定它对自然数a为真时，可以证明对a’ 也真。那么，命题对所有自然数都真。

最后一条公理有些特殊，它保证了数学归纳法的成立, 由于这个公理不仅涉及变量, 同时也涉及性质, 所以它在本质上与其他四个公理是不同的。事实上, 公理 5 严格来说应该被称为公理模式而非公理——它是一个模板而不是一个独立的公理,在这个模板上可以构造出很多个 (无穷多个) 公理。总之，有了这五条公理以后，我们就可以在此基础上递归的定义加法，乘法，减法和除法，以及一切自然数的运算。然后，我们就可以用一种递归的形式“计算”出 1 + 1 = 2 。至于什么要说是递归的形式，让我们先来了解一下对加法的定义。

定义 1 (自然数的加法) 令 m 为一个自然数,我们定义 m 加上 0 为0 + m := m。 现在递归地假设我们已经定义了如何把 m 加上 n, 那么我们把 m 加上 n + + 定义为 (n + +) + m := (n + m) + +。

引理 2 对任意的自然数 n, n + 0 = n 恒成立。

注意, 不能根据 0 + m = m 立即推导出该结论, 这是因为目前我们还不知道有 a + b = b + a。

证明: 采用归纳法来证明。 因为 0 + m = m 对任意自然数 m 均成立并且 0 是一个自然数, 所以我们能得到最基本的情况 0+0 = 0。 现在归纳性地假设 n+0 = n 成立。 我们希望证明 (n++)+0 = n++。 根据加法的定义, (n++)+0 = (n+0)++; 又根据 n+0 = n 可以推导出 (n+0)++ = n++。 至此整个归纳过程就结束了。

引理 3 对任意的自然数 n 和 m, 有 n + (m + +) = (n + m) + + 成立。

同样,因为目前我们还不知道有 a + b = b + a,所以不能从 (n + +) + m = (n + m) + + 中推导出本结论。

证明: 将 m 设为定值, 对 n 采用归纳法。 首先考虑最基本的情况, n = 0。 此时我们必须证明 0+(m++) = (0+m)++。 根据加法的定义可得, 0+(m++) = m++ 以及 0 + m = m。所以,要证明等式的两端均与 m + + 相等,进而该等式两端相等。现在归纳性地假定 n + (m + +) = (n + m) + + 成立,那么我们必须证明 (n + +) + (m + +) = ((n + +) + m) + +。根据加法的定义,上式左端等于(n + (m + +)) + +, 又由归纳假设可得 (n + (m + +)) + + = ((n + m) + +) + +。 类似地, 根据加法的定义可得, (n + +) + m = (n + m) + +, 从而等式的右端也等于((n + m) + +) + +。 因此我们证明了等式左端等于右端, 从而整个归纳过程到这里就结束了。

作为引理 2.2.2 与引理 2.2.3 的一个特别推论, 我们得到 n + + = n + 1。

命题 4 (加法是可交换的) 对任意的自然数 n 和 m, 有 n + m = m + n 成立。

证明: 将 m 设为定值, 对 n 采用归纳法。 首先证明当 n = 0 时结论成立, 也就是证明 0+m = m+0。 一方面, 根据加法的定义可以推出 0+m = m; 另一方面, 根据引理 2.2.2 可得 m+0 = m。 于是 n = 0 时结论成立。 现在归纳性地假设 n+m = m+n 成立,那么我们要证明 (n + +) + m = m + (n + +) 来完成归纳。根据加法的定义, (n++)+m = (n+m)++; 根据引理 2.2.3, m+(n++) = (m+n)++, 但由归纳假设 n+m = m+n 可知 (m+n)++ = (n+m)++。 因此 (n++)+m = m+(n++), 进而归纳过程结束。

命题 5 (加法是可结合的) 对任意三个自然数 a、 b、 c, 有 (a + b) + c = a + (b + c) 成立。

证明: 略。

命题 6 (消去律) 令 a、 b、 c 为任意三个自然数并且满足 a + b = a + c, 那么 b = c 成立。

注意, 由于目前我们还没有给出减法和负数的概念, 所以这里不能利用减法或者负数对该命题进行证明。 事实上, 消去律对于后面我们定义减法 (和整数) 的概念至关重要, 因为在正式定义减法之前, 消去律就涉及一种 “虚拟减法” 。

证明: 我们通过对 a 进行归纳来证明该命题。首先考虑最基本的情况 a = 0, 我们有 0 + b = 0 + c, 那么根据加法的定义, 由 0 + b = 0 + c 可以得到 b = c, 故当 a = 0 时结论得证。 现在归纳性假设关于 a 的消去律成立 (进而从 a + b = a + c 中可以得到 b = c) ,接下来我们要证明关于 a + + 的消去律也成立。换言之,就是在假设 (a + +) + b = (a + +) + c 成立时,去证明 b = c 成立。根据加法的定义, 我们有 (a + +) + b = (a + b) + + 和 (a + +) + c = (a + c) + +, 从而可以得到(a + b) + + = (a + c) + +。 根据公理 2.4, 我们进一步得到 a + b = a + c。 因为我们已知关于 a 的消去律成立, 所以有 b = c 成立, 结论得证。 至此归纳法结束。

定义 7(正自然数) 称一个自然数 n 是正的, 当且仅当它不等于 0。

命题 8 如果 a 是正的并且 b 是自然数, 那么 a + b 是正的 (从而根据命题2.2.4 可知, b + a 也是正的) 。

证明: 我们通过对 b 进行归纳来证明该命题。 如果 b = 0, 那么 a+b = a+0 = a 显然是正的, 从而 b = 0 时的结论得证。 现在归纳性地假设 a + b 是正的。 那么根据公理 2.3 可知, a + (b + +) = (a + b) + + 不等于零, 从而 a + (b + +) 是正的。 至此归纳法结束。

推论 9 如果 a 和 b 是自然数并且满足 a + b = 0, 那么 a = 0 且 b = 0。

证明: 假设结论的反面 a ?= 0 或 b ?= 0 成立。 如果 a ?= 0, 那么 a 是正的, 从而根据命题 2.2.8 可知, a + b 是正的, 这显然与已知条件 a + b = 0 相矛盾。 类似地, 如果 b ?= 0, 那么 b 是正的, 同样根据命题 2.2.8 可知, a + b 是正的, 这与 a + b = 0 相矛盾。 于是 a 和 b 必须同时为 0。

引理 10 令 a 表示一个正自然数, 那么恰存在一个自然数 b 使得 b++ = a。

证明: 略。

定义 11(自然数的排序) 令 n 和 m 表示任意两个自然数。 我们称 n 大于等于 m, 并且记作 n >= m 或者 m <= n, 当且仅当存在自然数 a 使得 n = m + a。 我们称 n 严格大于 m, 并且记作 n > m 或者 m < n, 当且仅当 n >= m 且 n != m。

命题 12(自然数的序的基本性质) 令 a、 b、 c 为任意自然数, 那么:

(a) (序是自反的) a >= a。

(b) (序是可传递的) 如果 a >= b 并且 b >= c, 那么 a >= c。

(c) (序是反对称的) 如果 a >= b 并且 b >= a, 那么 a = b。

(d) (加法保持序不变) a >= b, 当且仅当 a + c >= b + c。

(e) a < b, 当且仅当 a + + <= b。

(f) a < b, 当且仅当存在正自然数 d 使得 b = a + d。

证明: 略。

至此，有关加法的定义这里先告一段落。我们来分析一下，我们是如何计算出 1 + 1 = 2 的。

根据 定义 1 , 1 + 1 => (0++) + 1 => (0 + 1)++, 而 0 + 1 := 1, 故 1 + 1 = 1++ = 0++ ++。所以，我们最终得到 1 + 1 的结果等于 0 的后继数的后继数，我们把它写为便于书写的形式 —— 2 。

现在，给我们任意两个自然数求和，我们都可以通过这样的“推理”或者说“递归的重复”，得到 0++ ++ … ++ 这种形式的结果。至于如何把它精简的表示出来，不同的民族有不同的智慧，中国人有“一、二、三…”或者“壹、贰、叁…”，罗马人有“I、II、III…”，阿拉伯仁人有“1、2、3…”。¹ 这些形式并不重要，重要的是，人脑如何进行的运算？其实仔细观察一下你会发现，我们所谓的智能，某种程度上，只是一种对已知模式的不断重复。

这便是第一种计算模型，递归。

计算模型

有非常之多的计算模型，他们目前已被证明在数学上完全等价，或者说他们的计算能力相同，即不存在某个问题只能被一种计算模型解决，而无法被另外的模型解决。下面简要介绍几种别的计算模型，每一种计算模型，都是对计算本质不同角度的诠释。

马尔可夫算法

定义

1. 自顶向下依次检查规则，看是否能在符号串中找到任何在箭头左边的字符串。
2. 如果没有找到，停止执行算法。
3. 如果找到一个或多个，把符号串中的最左匹配的文字替换为在第一个相应规则的箭头右边的字符串。
4. 返回步骤1并继续。（如果应用的规则是终止规则，则停止执行算法。）

马尔可夫算法是使用类似形式文法的规则在符号串上操作的字符串重写系统。马尔可夫算法被证明是图灵完全的，这意味着它们适合作为一般的计算模型，并可以用它的简单概念表示任何数学表达式。

所以说，计算的本质，还可以理解为对字符串的替换。回想一下，在我们还是弱小无助的小学生时，加法不正是这样被老师们强硬的塞进我们的脑子里的吗？所以说，人类的本质是复读机，确实道出了本质。😂

图灵机

大名顶顶的图灵机，不多赘述，图灵机有非形式化定义的版本，但是冗余而陈杂，相当啰嗦，这里给出另外一种我比较喜欢的定义。

形式化定义

一台图灵机是一个七元有序组 \((Q,\Sigma ,\Gamma ,\delta ,q_{0},q_{accept},q_{reject})\)，其中 \(Q,\Sigma ,\Gamma\)都是有限集合，且满足：

1. \( Q \)是非空有穷状态集合；
2. \( \Sigma \) 是非空有穷输入字母表，其中不包含特殊的空白符 {\displaystyle \square } \square；
3. \( \Gamma \) 是非空有穷带字母表且 \( \Sigma \subset \Gamma \)；
4. \( \square \in \Gamma -\Sigma \) 为空白符，也是唯一允许出现无限次的字符；
5. \( \delta :Q\times \Gamma \to Q\times \Gamma \times {L,R,-} \) 是转移函数，其中 \( L, R \)表示读写头是向左移还是向右移, - 表示不移动；
6. \( q_0 \in Q \)是起始状态；
7. \( q_{accept} \in Q \)是接受状态。 \( q_{reject}\in Q \)是拒绝状态，且 \( q_{reject}\neq q_{accept} \)。

细胞自动机

相信玩过 Mathematica 的同学都知道的吧，又叫做元胞自动机，生命游戏，被 Wolfram 玩出了花，还写了本书，书名起的正如他本人一样自负，叫 A New Kind of Science。

有限状态机

有限状态机（英语：finite-state machine，缩写：FSM）又称有限状态自动机，简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

形式化定义

依据类型不同有多种定义。接受器有限状态机是五元组 \( (\Sigma ,S,s_{0},\delta ,F) \)，这里的：

• \( \Sigma \) 是输入字母表（符号的非空有限集合）。
• \( S \)是状态的非空有限集合。
• \( s_{0} \)是初始状态，它是 \( S \) 的元素。在非确定有限状态自动机中，\( s_{0} \) 是初始状态的集合。
• \( \delta \) 是状态转移函数：\( \delta :S\times \Sigma \rightarrow S \)。
• \( F \) 是最终状态的集合，\( S \) 的（可能为空）子集。

变换器 有限状态自动机是六元组 \( (\Sigma ,\Gamma ,S,s_{0},\delta ,\omega ) \)，这里的：

• \( \Sigma \) 是输入字母表（符号的非空有限集合）;
• \( \Gamma \) 是输出字母表（符号的非空有限集合）;
• \( S \) 是状态的非空有限集合;
• \( s_{0} \) 是初始状态，它是 \( S \) 的元素。在非确定有限状态自动机中，\( s_{0} \) 是初始状态的集合;
• \( \delta \) 是状态转移函数： \( \delta :S\times \Sigma \rightarrow S \);
• \( \omega \) 是输出函数。

如果输出函数是状态和输入字母表的函数 \( (\omega :S\times \Sigma \rightarrow \Gamma) \) ，则定义对应于 Mealy模型 ，它可以建模为 Mealy机 。如果输出函数只依赖于状态 \( (\omega :S\rightarrow \Gamma) \)，则定义对应于 Moore模型 ，它可建模为 Moore机 。根本没有输出函数的有限状态机叫做半自动机或转移系统。

状态机编程

状态机和面向对象编程。

Unity 的 PlayMaker 就是一个完全基于 FSM 的可视化编程框架，号称可以让不懂程序的人轻松制作游戏，它也确实做到了这一点。当然，那只是某一种程度上会对编程起到简化作用，你让美术人员用 FSM 撸出来一个魔兽世界，那难度堪比自己造火箭上月球。不过理论上来说，完全可以做到，因为 FSM 与图灵机完全等价！PlayMaker 对 Unity 来说，是对面向对象编程范式的一种补充，在某些实际情况中的数学模型可能更加适合被 FSM 所描述，而面向对象的编程仅仅是一个工程实践，而不是一种原理，OOP 并不是万能。更多讨论请看博主这篇文章。

λ演算

重磅成员，也是最值得大篇幅讨论的计算模型。

暂时先空着，留着以后慢慢写。

人工神经网络

想不到吧，竟然还有它！

人工神经网络（英语：Artificial Neural Network，ANN），简称 神经网络（Neural Network，NN）。也有非常多要说的，篇幅有限，这里不多做介绍，懂的人自然都了解。

理论性质

计算能力

多层感知器（Multilayer Perceptron，缩写MLP）是一个通用的函数逼近器，由Cybenko定理证明。然而，证明不依赖特定的神经元数量或权重。Hava Siegelmann和Eduardo D. Sontag的工作证明了，一个具有有理数权重值的特定递归结构（与全精度实数权重值相对应）由有限个神经元和标准的线性关系构成的神经网络相当于一个 通用图灵机 。他们进一步表明，使用无理数权重值会产生一个超图灵机。

结论

请注意，上述这种神经网络等同于通用图灵机，推导一下 人脑 <=> 神经网络 <=> 通用图灵机 <=> 马尔可夫算法(抽象文本替换算法)。(大雾)

Sooooooooo!我们得出了一个惊人结论，人类的本质等价于复读机！！！

最后

关于计算理论的探讨暂时告一段落，下次我们将继续这个话题，讨论一下停机问题和哥德尔不完备定理，以及集合论的一些内容。这里先立个小 Flag 🚩，免得以后我忘了写，看到这里的同学也可以留言提醒我一下回来更新。