• 等价的计算模型
  • 学习目标
  • 8.1 RAM机与NAND-RAM
  • 8.2 具体细节(可选)
    • 8.2.1 NAND-TM中的索引访问
    • 8.2.2 NAND-TM中的二维数组
    • 8.2.3 其他细节
  • 8.3 图灵等价性(讨论)
    • 8.3.1 “两全其美“的范式
    • 8.3.2 浅谈抽象层次
    • 8.3.3 图灵完备性与等价性的形式化定义(可选)
  • 8.4 元胞自动机
    • 8.4.1 一维元胞自动机的图灵完备性
    • 8.4.2 图灵机格局与状态转移函数
  • 8.5 λ演算与函数式编程语言
    • 8.5.1 函数的高阶应用
    • 8.5.2 通过柯里化实现多参数函数
    • 8.5.3 λ演算的形式化描述
    • 8.5.4 λ演算中的无限循环
  • 8.6 增强λ演算
    • 8.6.1 增强λ演算中的函数计算
    • 8.6.2 增强λ演算的图灵完备性
  • 8.7 从增强λ演算到纯λ演算
    • 8.7.1 列表处理
    • 8.7.2 Y组合子: 不需要递归的递归
  • 8.8 Church-Turing论题(讨论)
    • 8.8.1 不同的计算模型
  • 8.9 习题
  • 8.10 参考文献

等价的计算模型

学习目标

• 了解RAM机(RAM Machine)与λ演算(λ Calculus)
• 掌握这些模型与图灵机及其他模型的等价关系
• 认识元胞自动机(Cellular Automata)与各种图灵机格局
• 理解Church-Turing论题

到目前为止, 我们已经定义了使用图灵机计算函数的概念, 但这与实际的计算方法并不完全吻合. 本章将通过证明可计算函数的定义在各种计算模型下保持不变, 来论证这一选择的合理性. 这一概念被称为图灵完备性(Church completeness)或图灵等价性(Church equivalence), 是计算机科学中最基本的事实之一. 实际上, 被广泛认同的Church-Turing论题做了出了如下主张: 任何对可计算函数的“合理“定义, 都等价于通过图灵机可计算的概念. 我们将在8.8节讨论Church-Turing论题以及“合理“的可能定义.

本章讨论的主要计算模型包括:

• RAM机: 图灵机与具备随机存取存储器(RAM, Random Access Memory)的标准计算架构并不对应, RAM机的数学模型更接近实际计算机, 但我们将看到它在计算能力上与图灵机等价. 我们还将讨论RAM机的一种编程语言变体, 称之为NAND-RAM. 图灵机与RAM机的等价性使得我们能够证明诸多流行编程语言的图灵等价性, 包括现实中使用的所有通用编程语言, 如C、Python、JavaScript等.
• 元胞自动机: 许多自然的和人工的系统都可以被建模为简单组件的集合, 每个组件根据其自身状态及其直接邻居的状态, 按照简单的规则进行演化. 一个著名的例子是康威的生命游戏(Conway’s Game of Life). 为了证明元胞自动机与图灵机等价, 我们将引入图灵机格局(configurations of Turing machines). 这些格局还有其他应用, 特别是在第11章用于证明哥德尔不完备定理——数学中的一个核心结果.
• λ演算: λ演算是一种表达计算模型, 起源于20世纪30年代, 不过它与当今广泛使用的函数式编程语言密切相关. 证明λ演算与图灵机等价涉及一种名为“Y组合子“(Y Combinator)的消除递归的巧妙方法.

8.1 RAM机与NAND-RAM

图灵机(以及NAND-TM程序)的一个局限性在于, 我们每次只能访问数组或磁带的一个位置. 如果磁头位于磁带的第$22$位, 而我们想要访问第$957$个位置, 那么我们至少需要$923$步才能到达该位置. 相比之下, 几乎每种编程语言都提供了直接访问内存位置的形式化方法. 实际的物理计算机也提供了可以被视为一个大型数组Memory的随机存取存储器(RAM), 给定索引$p$(即内存地址或指针), 我们可以读取和写入Memory的第$p$个位置. (“随机存取存储器“这一名称实际上用词有误, 因为它与概率无关, 但既然这是计算理论与实践中的标准术语, 我们也将沿用这一说法).

中这种内存访问进行建模的计算模型是RAM机(有时也称为字RAM模型(Word RAM Model)), 如图 8.2所示. RAM机的内存是一个大小无界的数组, 其中每个单元可以存储一个字(Word), 我们将其视为$\{0,1{\}}^w$的字符串, 同时(等价地)也视为$[2^w]$中的一个数字. 例如, 许多现代计算架构使用64位的字, 每个内存位置保存一个$\{0,1{\}}^{64}$中的字符串, 这也可以视为一个介于$0$到$2^{64}-1=18,446,744,073,709,551,615$之间的数字. 参数$w$被称为字长(Word Size). 在实践中, $w$通常是一个固定数字(比如64), 但在理论研究中, 我们将$w$建模为一个可以依赖于输入长度或步骤数的参数. (你可以将$2^w$大致视为我们在计算中使用的最大内存地址)除了内存数组, RAM机还包含恒定数量的寄存器(Register)$r_0,\dots ,r_{k-1},$ 每个寄存器也能保存一个字.

RAM机可以执行的操作包括:

• 数据移动: 将内存中某个单元的数据加载到寄存器中, 或将寄存器的内容存储到内存的某个单元. RAM机可以直接访问内存的任何单元, 而无需像图灵机那样将“磁头“移动到该位置. 也就是说, RAM机可以在一步中将由寄存器$r_j$索引的内存单元的内容加载到寄存器$r_i$中, 或将寄存器$r_i$的内容存储到由寄存器$r_j$索引的内存单元中.
• 计算: RAM机可以对寄存器执行计算, 例如算术运算、逻辑运算和比较.
• 控制流: 与图灵机一样, 接下来执行什么指令的选择可以取决于RAM机的状态, 这由其寄存器的内容捕获.

我们不会给出RAM机的正式定义, 但参考文献部分(第8.10节)包含了这些定义的来源. 正如NAND-TM编程语言模拟图灵机一样, 我们也可以定义一种模拟RAM机的NAND-RAM编程语言. NAND-RAM编程语言通过添加以下特性扩展了NAND-TM:

• NAND-RAM的变量允许是(非负)整数值的, 而不仅仅是NAND-TM中的布尔值. 也就是说, 标量变量foo保存的是$\mathbb{N}$中的非负整数(而不仅仅是$\{0,1\}$中的一位), 数组变量Bar保存的是一个整数数组. 与RAM机的情况一样, 我们不允许无界大小的整数. 具体来说, 每个变量保存一个介于$0$和$T-1$之间的数字, 其中$T$是程序到目前为止已执行的步骤数. (你现在可以忽略此限制: 如果我们想要保存更大的数字, 可以简单地执行虚拟指令；这在后面的章节中会有用)
• 我们允许对数组进行索引访问. 如果foo是标量而Bar是数组, 则Bar[foo]引用由foo的值索引的Bar的位置. (注意这意味着我们不再需要特殊的索引变量i)
• 正如编程语言中常见的情况, 我们假设对于布尔运算(如NAND), 零值整数被视为假, 非零值整数被视为真.
• 除了NAND之外, NAND-RAM还包括所有基本的算术运算: 加、减、乘、(整数)除, 以及比较(等于、大于、小于等).
• NAND-RAM将条件语句if/then作为语言的一部分.
• NAND-RAM包含循环结构, 例如while和do, 作为语言的一部分.

NAND-RAM编程语言的完整描述见附录. 然而, 关于NAND-RAM你需要了解的最重要的事实是你实际上并不需要太多了解NAND-RAM, 因为它在能力上等同于图灵机:

由于NAND-TM程序等价于图灵机, 而NAND-RAM程序等价于RAM机, 定理 8.1表明所有这四种模型彼此之间是等价的.

上述方法并非获得定理 8.1证明的唯一途径, 例如可参见练习8.1.

8.2 具体细节(可选)

我们将不展示定理 8.1的完整形式化证明, 而是聚焦于最重要的部分: 实现索引访问, 以及用一维数组模拟二维数组. 即便如此, 描述这些部分也已经相当繁琐, 这对于任何写过编译器的人都不足为奇. 因此, 你可以随意略读本节. 重点不在于记住所有细节, 而在于明白原则上将一个NAND-RAM程序转换为等价的NAND-TM程序是可能的, 你自己如果想做也能完成.

8.2.1 NAND-TM中的索引访问

在NAND-TM中, 我们只能访问数组在索引变量i位置处的元素, 而NAND-RAM拥有整数值变量, 并能使用它们对数组进行索引访问, 写作Foo[bar]. 为了在NAND-TM中实现索引访问, 我们将使用某种无前缀编码(参见2.5.2节)在数组中编码整数, 然后提供一个过程Setindex(Bar)来将i设置为Bar编码的值. 我们可以通过先执行Setindex(Bar)再执行Foo[i]来模拟Foo[Bar]的效果.

Setindex(Bar)的实现可以通过以下方式完成:

1. 初始化一个数组Atzero, 使得Atzero[$0$]$=1$并且对所有$j>0,$ Atzero[$j$]$=0.$ (这可以在NAND-TM中轻松完成, 因为所有未初始化的变量默认值为零)
2. 通过递减i直到达到Atzero[i]$=1$的点来将i设置为零.
3. 令Temp为一个编码数字$0$的数组.
4. 我们使用GOTO来模拟一个内部循环, 形式如下: 当Temp$\ne$Bar时, 递增Temp.
5. 在循环结束时, i等于由Bar编码的值.

在NAND-TM代码中(使用一些语法糖), 我们可以按如下方式实现上述操作:

# 假设Atzero是一个数组, 满足Atzero[0]=1
# 且对所有j>0, Atzero[j]=0

# 将i设置为0. 
LABEL("zero_idx")
dir0 = zero
dir1 = one
# 对应i <- i-1
GOTO("zero_idx",NOT(Atzero[i]))
...
# 将temp清零
#(下面的代码假设使用一种特定的无前缀编码, 其中10是"结束标记")
Temp[0] = 1
Temp[1] = 0
# 将i设置为Bar, 假设我们知道如何递增和比较
LABEL("increment_temp")
cond = EQUAL(Temp,Bar)
dir0 = one
dir1 = one
# 对应i <- i+1
INC(Temp)
GOTO("increment_temp",cond)
# 如果执行到这里, i就是Bar所编码的数字
...
# 程序的最终指令
MODANDJUMP(dir0,dir1)

8.2.2 NAND-TM中的二维数组

为了实现二维数组, 我们希望将它们嵌入到一个一维数组中. 思路是通过一个一一对应的函数$\text{embed}:\mathbb{N}\times \mathbb{N}\to \mathbb{N},$ 从而将二维数组Two中的位置$(i,j)$嵌入到一维数组One的位置$\text{embed}(i,j)$中.

由于集合$\mathbb{N}\times \mathbb{N}$看上去“远大于“集合$\mathbb{N},$ 先验地来看, 这样的一个双射可能并不明显存在. 然而, 一旦你深入思考, 你就会发现构建它并不算太难. 例如, 你可以让一个孩子用剪刀和胶水将一张10英寸乘10英寸的纸转换成一条1英寸乘100英寸的纸带. 这本质上就是一个从$[10]\times [10]$到$[100]$的双射. 我们可以推广这一点, 得到一个从$[n]\times [n]$到$[n^2]$的双射, 更一般地, 得到一个从$\mathbb{N}\times \mathbb{N}$到$\mathbb{N}$的双射.

具体来说, 下面的$\text{embed}$函数可以做到这一点(见图 8.5): $$\text{embed}(x,y)=\frac{1}{2}(x+y)(x+y+1)+x$$

习题8.3要求你证明$\text{embed}$确实是一个双射, 并且可以由一个NAND-TM程序计算. (后者可以通过简单地遵循小学所学的乘法、加法和除法算法来完成)这意味着我们可以将形式为Two[Foo][Bar] = something(即, 访问二维数组中由一维数组Foo和Bar编码的整数对应的位置)替换为如下形式的代码:

Blah = embed(Foo,Bar)
Setindex(Blah)
Two[i] = something

8.2.3 其他细节

一旦我们有了二维数组和索引访问, 用NAND-TM模拟NAND-RAM就只是在NAND-TM中实现算术运算和比较的标准算法的问题了. 虽然这很繁琐, 但并不困难, 最终的结果表明每个NAND-RAM程序$P$都可以被一个等价的NAND-TM程序$Q$模拟, 从而完成了定理 8.1的证明.

Stack[stackpointer]=foo
stackpointer += one

bar = Stack[stackpointer]
stackpointer -= one

8.3 图灵等价性(讨论)

任何标准编程语言, 如C、Java、Python、Pascal、Fortran, 其操作都与NAND-RAM非常相似. (事实上, 它们最终都可以由具有固定数量寄存器和大型内存阵列的机器来执行)因此, 使用定理 8.1, 我们可以用NAND-TM程序来模拟任何此类编程语言中的程序. 反过来, 在任何上述编程语言中编写一个NAND-TM的解释器是一个相当简单的编程练习. 因此, 我们也可以使用这些编程语言来模拟NAND-TM程序(进而通过定理7.11来模拟图灵机). 这种在计算能力上等同于图灵机/NAND-TM的特性被称为图灵等价(有时也称为图灵完备). 因此, 我们熟悉的所有编程语言都是图灵等价的. ¹

8.3.1 “两全其美“的范式

图灵机与RAM机之间的等价性使我们能够为手头的任务选择最方便的语言:

• 当我们想要证明一个关于所有程序/算法的定理时, 我们可以使用图灵机(或NAND-TM), 因为它们更简单且易于分析. 特别是, 如果我们想证明某个函数无法被计算, 那么我们将使用图灵机.
• 当我们想要证明某个函数可以被计算时, 我们可以使用RAM机器或NAND-RAM, 因为它们更容易编程, 并且更接近于我们习惯的高级编程语言. 事实上, 我们通常会以非正式的方式描述NAND-RAM程序, 并相信读者能够填充细节并将简略的描述转换为精确的程序. (这就像人们通常使用非正式的或“伪代码“的算法描述方式, 并相信他们的受众知道在需要时将这些描述转换为代码一样)

我们对图灵机/NAND-TM和RAM机/NAND-RAM的使用, 与人们在实践中使用高级和低级编程语言的方式非常相似. 当人们想要制造一个执行程序的设备时, 为一种非常简单和“低级“的编程语言来实现是很方便的. 当人们想要描述一个算法时, 使用尽可能高级的形式体系是方便的.

8.3.2 浅谈抽象层次

在任何计算理论课程中的某个时刻, 教师和学生都需要进行那次谈话. 也就是说, 我们需要讨论描述算法时的抽象层次. 在算法课程中, 通常用英语描述算法², 假设读者能够“填充细节“, 并在需要时能够将此类算法转化为实现. 例如, 算法 8.1是广度优先搜索算法的高级描述.

如果我们想提供关于如何在Python或C(或NAND-RAM/NAND-TM)等编程语言中实现广度优先搜索的更多细节, 我们会描述如何用数组实现队列数据结构, 以及同样如何用数组标记顶点. 我们称这种“中间层次“的描述为实现级别(implementation level)或伪代码描述. 最后, 如果我们想精确地描述实现, 我们会给出程序的全部代码(或另一个完全精确的表示形式, 例如元组列表的形式). 我们称之为形式化或低级(low level)描述.

虽然我们开始时是在完全形式化的层面上描述NAND-CIRC、NAND-TM和NAND-RAM程序, 随着本书的深入, 我们将转向实现级别和高级别的描述. 毕竟, 我们的目标不是使用这些模型进行实际计算, 而是分析计算的一般现象. 也就是说, 如果你不理解高级描述如何转化为实际实现, “深入底层“通常是一个极好的练习. 计算机科学家最重要的技能之一就是能够在抽象层次结构中上下移动.

类似的区别也适用于将对象表示为字符串的概念. 有时, 为了精确起见, 我们会给出一个低级规范(low level specification), 确切说明一个对象如何映射到二进制字符串. 例如, 我们可能将$n$个顶点的图的编码描述为长度为$n^2$的二进制字符串, 通过说明我们将顶点集为$[n]$的图$G$映射到字符串$x\in \{0,1{\}}^{n^2},$ 其中$x$的第$n\cdot i+j$个坐标是$1$当且仅当边$\overrightarrow{i;j}$存在于$G$中. 我们也可以使用中间或实现级别的描述, 只需简单说明我们使用邻接矩阵表示法来表示图.

最后, 因为图(以及一般对象)的各种表示之间的转换可以通过NAND-RAM(因此也可以通过NAND-TM)程序完成, 所以在进行高级别讨论时, 我们也会避免关于表示的讨论. 例如, 图连通性是一个可计算函数, 这一事实无论我们是用邻接表、邻接矩阵、边对列表等表示图都是成立的. 因此, 在精确表示无关紧要的情况下, 我们通常会谈论我们的算法将对象$X$(可以是图、向量、程序等)作为输入, 而不指定$X$如何被编码为字符串.

定义“算法“: 到目前为止, 我们一直非正式地使用“算法“这个术语. 然而, 图灵机和一系列等效模型产生了一种精确且形式化地定义算法的方法. 因此, 在本书中, 每当我们提到算法时, 我们指的是它是图灵等效模型(如图灵机、NAND-TM、RAM机等)中的一个实例. 由于所有这些模型的等价性, 在许多情况下, 我们使用哪一个并不重要.

8.3.3 图灵完备性与等价性的形式化定义(可选)

一个计算模型是某种定义程序(由字符串表示)计算(部分)函数的方式. 一个计算模型$\mathcal{M}$是图灵完备的, 如果我们可以将每个图灵机(或等价的NAND-TM程序)$N$映射到$\mathcal{M}$中的一个程序$P,$ 使得$P$计算与$N$相同的函数. 它是图灵等价的, 如果另一个方向也成立(即, 我们可以将$\mathcal{M}$中的每个程序映射到一个计算相同函数的图灵机). 我们可以形式化地定义这个概念如下. (这个形式化定义对于本书的其余部分并不关键, 只要你理解图灵等价的一般概念就可以跳过它；这个概念在文献中有时被称为哥德尔数(Gödel numbering)或可接纳数(admissible numbering))

一些图灵等价模型的例子(其中一些我们已经见过, 一些将在下面讨论)包括:

• 图灵机
• NAND-TM程序
• NAND-RAM程序
• λ演算
• 生命游戏(将程序和输入/输出映射到起始和结束格局)
• 编程语言, 如Python/C/Javascript/OCaml…(允许无限存储)

8.4 元胞自动机

许多物理系统可以被描述为由大量相互作用的基元组件组成. 一种模拟此类系统的方法是使用元胞自动机. 这是一个由大量(甚至无限)细胞组成的系统. 每个细胞只有有限个可能的状态. 在每个时间步, 细胞通过将某个简单规则应用于自身及其邻居的状态来更新到新状态.

元胞自动机的一个典型例子是康威的生命游戏(Conway’s Game of Life). 在此自动机中, 细胞排列在一个无限二维网格中. 每个细胞只有两种状态: “死亡”(我们可以编码为$0$并标识为$\varnothing )$或“存活“(我们可以编码为$1).$ 细胞的下一个状态取决于其先前状态及其8个垂直、水平和对角线邻居的状态(参见图 8.9). 死亡细胞只有在恰好有三个存活邻居时才会变为存活. 存活细胞只有在有两个或三个存活邻居时继续存活. 尽管细胞数量可能无限, 但我们可以通过仅跟踪存活细胞来使用有限长度字符串编码状态. 如果我们在具有有限数量存活细胞的格局中初始化系统, 那么在所有未来步骤中存活细胞的数量将保持有限. 生命游戏的维基百科页面上有一些产生非常有趣演化的格局的美丽图形和动画.

由于生命游戏中的细胞排列在无限二维网格中, 它是二维元胞自动机的一个例子. 我们也可以考虑一维元胞自动机的更简单设置, 其中细胞排列在一条无限直线上, 参见图 8.10. 事实证明, 即使这个简单模型也足以实现图灵完备性. 我们现在将正式定义一维元胞自动机, 然后证明它们的图灵完备性.

有限格局: 如果自动机$r$的格局中只有有限个索引$i_0,\dots ,i_{j-1}$在$\mathbb{Z}$中使得$A(i_j)\ne \varnothing ,$ 则我们称该格局是_有限的_. (即, 对于每个$i\notin i_0,\dots ,i_{j-1},$ 有$A(i)=\varnothing )$这样的格局可以使用一个有限字符串表示, 该字符串编码索引$i_0,\dots ,i_{n-1}$和值$A(i_0),\dots ,A(i_{n-1}).$ 由于$r(\varnothing ,\varnothing ,\varnothing )=\varnothing ,$ 如果$A$是有限格局, 则$NEX{T}_r(A)$也是有限的. 我们只关心在有限格局中初始化的元胞自动机, 因此在其整个演化过程中保持有限格局.

8.4.1 一维元胞自动机的图灵完备性

我们可以编写一个程序(例如使用NAND-RAM)来模拟任何元胞自动机从初始有限格局的演化, 只需存储状态不等于$\varnothing$的细胞值并重复应用规则$r.$ 因此, 元胞自动机可以被图灵机模拟. 更令人惊讶的是, 反过来也成立. 例如, 尽管其规则简单, 我们可以使用生命游戏模拟图灵机(参见图 8.11).

事实上, 即使一维元胞自动机也可以是图灵完备的:

为了使“模拟图灵机“的概念更精确, 我们需要定义图灵机的格局. 我们将在下面的8.4.2节中这样做, 但高层面上, 图灵机的格局是一个字符串, 编码了其在计算中给定步骤的完整状态. 即, 其磁带所有(非空)单元的内容、其当前状态以及磁头位置.

定理 8.2的证明的关键思想是, 在图灵机$M$的计算中的每个点, $M$的磁带中唯一能改变的单元是磁头所在的位置, 并且该单元改变的值是其当前状态和$M$的有限状态的函数. 这一观察使我们能够将图灵机$M$的格局编码为一个元胞自动机$r$的有限格局, 并确保此编码格局在$r$的规则下的一步演化对应于图灵机$M$执行中的一步.

8.4.2 图灵机格局与状态转移函数

为了将上述思想转化为定理 8.2的严格证明(甚至陈述! ), 我们需要精确定义图灵机的格局这一概念. 这个概念在后续章节中对我们也有用.

定义 8.3有点繁琐, 但无论怎么讲格局只是一个字符串, 编码了图灵机在执行中给定点的快照. (用操作系统术语, 它是一个“核心转储“(core dump))这样的快照需要编码以下组件:

1. 当前磁头位置.
2. 大容量存储器的完整内容, 即磁带.
3. “本地寄存器“的内容, 即机器的状态.

我们如何编码格局的精确细节并不重要, 但我们确实想记录以下简单事实:

(为简化记号, 上面我们使用约定: 如果$i$“越界”, 例如$i<0$或$i>|\alpha |,$ 则我们假设${\alpha }_i=(\varnothing ,\cdot ))$我们将引理 8.1的证明留作练习8.7. 证明背后的思想很简单: 如果磁头既不在位置$i,$ 也不在位置$i-1$和$i+1,$ 那么$i$处的下一步格局将与之前相同. 否则, 我们可以从$i$或其邻居的格局中“读取“图灵机的状态和磁头位置的磁带值, 并用其更新$i$处的新状态应该是什么. 完成完整证明并不难, 但这样做是确保你熟悉格局定义的好方法.

完成定理 8.2的证明: 我们现在可以更正式地重述定理 8.2, 并完成其证明:

从定理 8.3的证明中产生的自动机具有大的字母表, 而且其大小依赖于被模拟的机器$M.$ 事实证明, 人们可以获得一个具有固定大小字母表的自动机, 该字母表独立于被模拟的程序, 实际上自动机的字母表可以是最小集合$\{0,1\}$! 图 8.13展示了这样的一个图灵完备的自动机.

8.5 λ演算与函数式编程语言

λ演算是定义可计算函数的另一种方式. 它有Alonzo Church在1930年代提出, 大约与Alan Turing提出图灵机同时. 有趣的是, 尽管图灵机不用于实际计算, λ演算却催生了函数式编程语言, 如Lisp、ML和Haskell, 并间接地促进了许多其他编程语言的发展. 在本节中, 我们将介绍λ演算并展示其能力等价于NAND-TM程序(因此也等价于图灵机). 我们的Github仓库包含一个Jupyter Notebook, 其中有一个λ演算的Python实现, 你可以通过实验来更好地理解这个话题.

λ算子: λ演算的核心是定义“匿名“函数的一种方式. 例如, 有一个函数$f$的定义为 $$f(x)=x\times x$$ 我们可以将其写为 $$\lambda x.x\times x$$ 因此$(\lambda x.x\times x)(7)=49.$ 也就是说, 你可以将$\lambda x.exp(x)$(其中$exp$是某个表达式)视为指定匿名函数$x\mapsto exp(x)$的一种方式. 匿名函数使用$\lambda x.f(x)$、$x\mapsto f(x)$或其他密切相关的表示法, 出现在许多编程语言中. 例如, 在Python中我们可以使用lambda x: x*x来定义平方函数, 而在JavaScript中我们可以使用x => x*x或(x) => x*x. 在Scheme中我们会将其定义为(lambda (x) (* x x)). 显然, 函数的参数名称无关紧要, 因此$\lambda y.y\times y$与$\lambda x.x\times x$相同, 因为两者都对应平方函数.

省略括号: 为了减少表示上的杂乱, 在书写λ演算表达式时我们经常省略函数求值的括号. 因此, 与其将函数$f$应用于输入$x$的结果写为$f(x),$ 我们也可以简单地写为$fx.$ 因此我们可以写$(\lambda x.x\times x)7=49.$ 在本章中, 我们将同时使用$f(x)$和$fx$表示法进行函数应用. 函数求值是结合性的, 并从左到右绑定, 因此$f;g;h$与$(fg)h$相同.

8.5.1 函数的高阶应用

λ演算的一个核心特性是函数都是“一等公民“, 即我们可以将函数作为其他函数的参数. 比如说, 你能猜到下面这个表达式等于什么数字吗?

$$(((\lambda f.(\lambda y.(f(fy))))(\lambda x.x\times x))3)\text{\hspace{1em}(8.1)}$$

让我们一步一步地计算(8.1). 尽管允许匿名函数是λ演算的优势, 但添加名称对于理解复杂表达式非常有帮助. 因此, 我们令$F=\lambda f.(\lambda y.(f(fy)))$与$g=\lambda x.x\times x.$

因此, (8.1)可以写作 $$((Fg)3)$$ 在输入函数$f$时, $F$输出函数$\lambda y.(f(fy)),$ 换而言之, $Ff$是函数$y\mapsto f(f(y)).$ 我们的函数$g$是简单的$g(x)=x^2,$ 因此$(Fg)$是将$y$映射到$(y^2{)}^2=y^4$的函数. 因此$((Fg)3)=3^4=81.$

8.5.2 通过柯里化实现多参数函数

在形如$\lambda x.e$的λ表达式中, 表达式$e$本身也可以包含λ运算符. 比如如下函数 $$\lambda x.(\lambda y.x+y)\text{\hspace{1em}(8.3)}$$ 将$x$映射到函数$y\mapsto x+y.$

特别地, 若我们使用$a$调用函数(8.3)得到某个函数$f,$ 再以$b$调用$f,$ 便可获得值$a+b.$ 可以看出, 对应于$a\mapsto (b\mapsto a+b)$的单参数函数(8.3)亦可视为双参数函数$(a,b)\mapsto a+b.$ 一般地, 我们可以使用λ表达式$\lambda x.(\lambda y.f(x,y))$来模拟双参数函数$(x,y)\mapsto f(x,y)$的效果, 这一技巧被称为柯里化(Currying). 我们将使用$\lambda x,y.e$作为$\lambda x.(\lambda y.e)$的简写形式. 若$f=\lambda x.(\lambda y.e),$ 则$(fa)b$对应于对$fa$进行求值后, 将所得函数作用于$b,$ 从而获得将$e$中$x$出现处替换为$a,$ $y$出现处替换为$b$的结果. 根据结合律, 该结果等价于$(fab),$ 有时我们也写作$f(a,b).$

8.5.3 λ演算的形式化描述

我们现在提供λ演算的形式描述. 我们从包含单个变量的“基本表达式“开始, 例如$x$或$y,$ 并构建更复杂的表达式, 形为$(e{e}^{\prime })$和$\lambda x.e,$ 其中$e,e^{\prime }$是表达式, $x$是变量标识符. 形式上, λ表达式的定义如下:

定义 8.4是一个递归定义, 因为我们在λ表达式的定义中使用了其自身. 这可能起初看起来令人困惑, 但事实上你从小学起就已经知道递归定义. 考虑我们如何定义算术表达式: 它是一个表达式, 要么只是一个数字, 要么具有形式$(e+e^{\prime }),$ $(e-e^{\prime }),$ $(e\times e^{\prime }),$ 或 $(e÷e^{\prime }),$ 其中$e$和$e^{\prime }$是其他算术表达式.

自由变量和绑定变量: λ表达式中的变量可以是自由的(free)或绑定(bound)到一个$\lambda$运算符(在1.4.7节的意义上). 在单变量λ表达式$var$中, 变量$var$是自由的. 在应用表达式$e=(e^{\prime }{e}^{\prime \prime })$中, 自由和绑定变量的集合与底层表达式$e^{\prime }$和$e^{\prime \prime }$的相同. 在抽象表达式$e=\lambda var.(e^{\prime })$中, $e^{\prime }$中$var$的所有自由出现(free occurences)都被绑定到$e$的$\lambda$运算符. 如果你觉得自由和绑定变量的概念令人困惑, 你可以通过为所有变量使用唯一标识符来避免所有这些问题.

优先级和括号: 我们将使用以下规则来允许我们省略一些括号. 函数应用从左向右结合, 因此$fgh$与$(fg)h$相同. 函数应用的优先级高于λ运算符, 因此$\lambda x.fgx$与$\lambda x.((fg)x)$相同. 这类似于我们在算术运算中使用优先级规则来允许我们使用更少的括号, 比如表达式$(7\times 3)+2$可以写成$7\times 3+2.$ 如8.5.2节所述, 我们还使用简写$\lambda x,y.e$表示$\lambda x.(\lambda y.e),$ 以及简写$f(x,y)$表示$(fx)y.$ 这与使用λ表达式模拟多输入函数的“柯里化“转换很好地配合.

λ表达式的等价性: 正如我们在练习 8.1中看到的,规则$(\lambda x.exp)ex{p}^{\prime }$等价于$exp[x\to ex{p}^{\prime }]$使我们能够修改λ表达式并获得更简单的等价形式. 另一个我们可以使用的规则是参数名称无关紧要, 因此$\lambda y.y$与$\lambda z.z$相同. 这些规则一起定义了λ表达式的等价性概念:

如果$exp$是一个形式为$\lambda x.ex{p}^{\prime }$的λ表达式, 那么它自然对应于将任何输入$z$映射到$ex{p}^{\prime }[x\to z]$的函数. 因此, λ演算自然隐含了一个计算模型. 由于在λ演算中, 输入本身可以是函数, 我们需要决定以什么顺序求值一个表达式, 例如

$$(\lambda x.f)(\lambda y.gz)\text{\hspace{1em}(8.4)}$$

对此有两种自然约定:

• 按名调用(Call-by-name, 即“惰性求值“): 我们通过先将右侧表达式$(\lambda y.g;z)$作为输入代入左侧函数来求值(8.4), 得到$f[x\to (\lambda y.g;z)]$然后从此继续.
• 按值调用(Call-by-value, 即“立即求值“): 我们先对右侧进行求值并得到$h=g[y\to z],$ 然后将其代入左侧得到$f[x\to h]$来求值(8.4).

因为λ演算只有纯函数, 没有“副作用“, 所以在许多情况下顺序无关紧要. 事实上, 可以证明如果我们在两种策略中都得到一个确定的不可约表达式(irreducible expression)(例如, 一个数字), 那么它将是同一个. 然而, 为具体起见, 我们将始终使用“按名调用“(即惰性求值)顺序. (编程语言Haskell也做出了相同的选择, 尽管许多其他编程语言使用立即求值)形式上, 使用“按名调用“求值λ表达式的过程由以下过程描述:

8.5.4 λ演算中的无限循环

与图灵机和NAND-TM程序类似, λ演算中的简化过程也可能进入无限循环. 例如, 考虑以下λ表达式

$$\lambda x.xx\lambda x.xx\text{\hspace{1em}(8.5)}$$

若我们尝试通过将左侧函数作用于右侧函数来简化(8.5), 则会得到另一个(8.5)的副本, 因此该过程永不休止. 在某些情况下, 求值顺序会影响表达式是否可被简化, 具体参见习题8.9.

8.6 增强λ演算

我们现在将λ演算作为一种计算模型进行讨论. 我们将从描述一个“增强“版本的λ演算开始, 它包含一些“冗余特性“, 但更易于理解. 我们将首先展示增强λ演算在计算能力上如何等价于图灵机. 然后, 我们将展示如何将“增强λ演算“的所有特性实现为“纯“(即非增强)λ演算之上的“语法糖“. 因此, 纯λ演算在计算能力上等价于图灵机(因此也等价于RAM机器和其他所有图灵等价模型).

增强λ演算包括以下对象和操作:

• 布尔常量和IF函数: 存在λ表达式$0,$ $1$和$\text{IF},$ 满足以下条件: 对于每个λ表达式$e$和$f,$ $\text{IF}1ef=e$且$\text{IF}0ef=f.$ 也就是说, $\text{IF}$是一个函数, 接受三个参数$a,e,f,$ 当$a=1$时输出$e,$ 当$a=0$时输出$f.$
• 二元组: 存在一个λ表达式$\text{PAIR},$ 我们将其视为配对函数. 对于每个λ表达式$e,f,$ $\text{PAIR}ef$是二元对$⟨e,f⟩,$ 其中$e$是其第一个成员, $f$是其第二个成员. 我们还有λ表达式$\text{HEAD}$和$\text{TAIL},$ 分别提取二元组的第一个和第二个成员. 因此, 对于每个λ表达式$e,f,$ $\text{HEAD}(\text{PAIR}ef)=e$且$\text{TAIL}(\text{PAIR}ef)=f.$ (在Lisp中, $\text{PAIR},$ $\text{HEAD}$和$\text{TAIL}$函数传统上称为cons, car和cdr)
• 列表和字符串: 存在λ表达式$\text{NIL},$ 对应空列表, 我们也用 $⟨\perp ⟩$ 表示. 使用$\text{PAIR}$和$\text{NIL},$ 我们可以构造列表. 思路是, 如果$L$是一个$k$元素列表, 形式为$⟨e_1,e_2,\dots ,e_k,\perp ⟩,$ 那么对于每个λ表达式$e_0,$ 我们可以使用表达式$\text{PAIR}{e}_{0}L$获得$k+1$元素列表$⟨e_0,e_1,e_2,\dots ,e_k,\perp ⟩.$ 例如, 对于任意三个λ表达式$e,f,g,$ 以下对应三元素列表$⟨e,f,g,\perp ⟩:$

$$\text{PAIR}e\left(\text{PAIR}f\left(\text{PAIR}g\text{NIL}\right)\right).$$

λ表达式$\text{ISEMPTY}$在$\text{NIL}$上返回$1,$ 在其他任何列表上返回$0.$ 字符串就是由比特组成的列表.

• 列表操作: 增强λ演算还包含列表处理函数$\text{MAP},$ $\text{REDUCE}$和$\text{FILTER}.$ 给定列表$L=⟨x_0,\dots ,x_{n-1},\perp ⟩$和函数$f,$ $\text{MAP}Lf$将$f$应用于列表的每个成员, 得到新列表$L^{\prime }=⟨f(x_0),\dots ,f(x_{n-1}),\perp ⟩.$ 给定列表$L$和输出为$0$或$1$的表达式$f,$ $\text{FILTER}Lf$返回列表$⟨x_i{⟩}_{f{x}_i=1},$ 包含所有$f$输出$1$的$L$的元素. 函数$\text{REDUCE}$对列表应用“组合“操作. 例如, $\text{REDUCE}L+0$将返回列表$L$中所有元素的和. 更一般地, $\text{REDUCE}$接受列表$L,$ 操作$f$(我们视其为接受两个参数)和λ表达式$z$(我们视其为操作$f$的“中性元“, 例如加法为$0,$ 乘法为 $1).$ 输出通过以下方式定义:

$$\text{REDUCE}Lfz=\{\begin{array}{ll}z& L=\text{NIL}\\ f(\text{HEAD}L)(\text{REDUCE}(\text{TAIL}L)fz)& \text{otherwise}\end{array}.$$

关于三个列表操作操作的图示, 请参见图 8.16.

• 递归: 最后, 我们希望能够执行递归函数. 由于在λ演算中函数是匿名的, 我们不能编写形式为$f(x)=blah$ 的定义, 其中$blah$包含对$f$的调用. 相反, 我们使用函数$f,$ 它接受一个额外输入$me$作为参数. 运算符$\text{RECURSE}$将接受这样的函数$f$作为输入, 并返回$f$的“递归版本“, 其中所有对$me$的调用都替换为对此函数的递归调用. 也就是说, 如果我们有一个函数$F,$ 接受两个参数$me$和$x,$ 那么$\text{RECURSE}F$将是函数$f,$ 接受一个参数$x,$ 使得对于每个$x,$ $f(x)=F(f,x).$

8.6.1 增强λ演算中的函数计算

一个增强λ表达式是通过将上述对象与应用和抽象规则组合而得到的. 简化λ表达式的结果是一个与远表达式等价的表达式, 因此如果两个表达式具有相同的简化结果, 则它们是等价的.

8.6.2 增强λ演算的图灵完备性

增强λ演算的基本操作或多或少相当于Lisp或Scheme编程语言. 鉴于这一点, 增强λ演算与图灵机等效或许并不令人惊讶:

8.7 从增强λ演算到纯λ演算

虽然我们所允许的增强型λ演算的“基本“函数集合比大多数Lisp方言提供的要小, 但从NAND-TM的角度来看, 它仍然显得有些“臃肿“. 我们能否用更少的函数来完成工作? 换句话说, 我们能否找到这些基本操作的一个子集, 使得该子集能够实现其余的操作?

事实上, 增强型λ演算的操作集合确实存在一个真子集, 可以用来实现其余所有操作. 这个子集就是空集.也就是说, 我们甚至可以不用$0$和$1,$ 仅使用λ运算符就能实现上述所有操作. 这完全是λ的天下!

定理 8.5背后的思想是, 我们将$0$和$1$本身编码为λ表达式, 并以此为基础进行构建. 这被称为Church编码(Church encoding), 因为它源于邱奇为了证明λ演算可以作为所有计算的基础所做的努力. 我们不会写出定理 8.5的完整形式化证明, 但会概述其中涉及的思想:

• 我们将$0$定义为接受两个输入$x,y$并输出$y$的函数, 将$1$定义为接受两个输入$x,y$并输出$x$的函数. 我们使用柯里化来实现双参数函数的效果, 因此$0=\lambda x.\lambda y.y$且$1=\lambda x.\lambda y.x.$ (这种表示方案是表示false和true的常见惯例, 但也有很多其他同样可行的表示$0$和$1$的替代方案)
• 上述实现使得$\text{IF}$函数的实现变得平凡: $\text{IF}(cond,a,b)$就是$condab,$ 因为$0ab=b$且$1ab=a.$ 我们可以写成$\text{IF}=\lambda x.x$以达到 $\text{IF}(cond,a,b)=(((\text{IF}cond)a)b)=condab$ 的效果.
• 为了编码一个二元组$(x,y),$ 我们将产生一个函数$f_{x,y},$ 该函数在其“内部“包含$x$和$y,$ 并且对于每个函数$g$都满足$f_{x,y}g=gxy.$ 也就是说, $\text{PAIR}=\lambda x,y.(\lambda g.gxy).$ 我们可以通过写$p1$来提取二元组$p$的第一个元素, 通过写$p0$来提取第二个元素, 因此$\text{HEAD}=\lambda p.p1$且$\text{TAIL}=\lambda p.p0.$
• 我们将$\text{NIL}$定义为忽略其输入并始终输出$1$的函数. 即$\text{NIL}=\lambda x.1.$ $\text{ISEMPTY}$函数在给定输入$p$时, 检查如果我们将$p$应用于函数$zero=\lambda x,y.0$(该函数忽略其两个输入并始终输出$0)$时是否得到$1.$ 对于每个形式为$p=\text{PAIR}xy$ 的有效二元组, $pzero=pxy=0,$ 而 $\text{NIL}zero=1.$ 形式化地, $\text{ISEMPTY}=\lambda p.p(\lambda x,y.0).$

8.7.1 列表处理

现在我们面临一个更大的障碍, 即如何在纯λ演算中实现$\text{MAP},$ $\text{FILTER},$ $\text{REDUCE}$和$\text{RECURSE}.$ 事实证明, 我们可以用$\text{REDUCE}$构建$\text{MAP}$和$\text{FILTER},$ 用$\text{RECURSE}$构建$\text{REDUCE}.$ 例如, $\text{MAP}(L,f)$等同于$\text{REDUCE}(L,g,\text{NIL}),$ 其中$g$是对输入$x$和$y$输出$\text{PAIR}(f(x),y)$的操作. (我将其验证留给读者你作为一个(推荐的)练习)

我们可以递归地定义$\text{REDUCE}(L,f,z),$ 通过令$\text{REDUCE}(NIL,f,z)=z,$ 并规定给定一个非空列表$L$(我们可以将其视为一个二元组$(head,rest)),$ $\text{REDUCE}(L,f,z)=f(head,\text{REDUCE}(rest,f,z)).$ 因此, 我们可能会尝试为$\text{REDUCE}$编写一个递归的λ表达式, 如下所示:

$$\text{REDUCE}=\lambda L,f,z.\text{IF}(\text{ISEMPTY}(L),z,f\text{HEAD}(L)\text{REDUCE}(\text{TAIL}(L),f,z))\text{\hspace{1em}(8.8)}$$

这里唯一的问题是λ演算没有递归的概念, 因此这是一个无效的定义. 但当然, 我们可以使用我们的$\text{RECURSE}$运算符来解决这个问题. 我们将把对“$\text{REDUCE}$“的递归调用替换为对作为额外参数给定的函数$me$的调用, 然后将$\text{RECURSE}$应用于此. 因此$\text{REDUCE}=\text{RECURSE}\text{myREDUCE},$ 其中:

$$\text{myREDUCE}=\lambda me,L,f,z.\text{IF}(\text{ISEMPTY}(L),z,f\text{HEAD}(L)me(\text{TAIL}(L),f,z))\text{\hspace{1em}(8.9)}$$

8.7.2 Y组合子: 不需要递归的递归

(8.9)表明为了实现$\text{MAP},$ $\text{FILTER}$与$\text{REDUCE}$我们需要在纯λ演算中实现$\text{RECURSE}$运算符. 这就是我们现在要做的事情.

我们如何在不使用递归的情况下实现递归?我们将用一个简单的例子来说明这一点 - $\text{XOR}$函数. 如练习 8.4所示, 我们可以递归地写出列表的$\text{XOR}$函数如下:

$$\text{XOR}(L)=\{\begin{array}{ll}0& L\text{为空}\\ {\text{XOR}}_2(\text{HEAD}(L),\text{XOR}(\text{TAIL}(L)))& \text{otherwise}\end{array}$$

其中${\text{XOR}}_2:\{0,1{\}}^2\to \{0,1\}$是两个比特上的异或操作. 在Python中, 我们会这样写:

def xor2(a,b): return 1-b if a else b
def head(L): return L[0]
def tail(L): return L[1:]

def xor(L): return xor2(head(L),xor(tail(L))) if L else 0

print(xor([0,1,1,0,0,1]))
# 1

现在, 我们如何消除这个递归调用? 主要思想是, 既然函数可以接受其他函数作为输入, 那么在Python(当然还有λ演算)中, 给函数自身作为输入是完全合法的. 因此, 我们的想法是尝试提出一个非递归函数tempxor, 它接受两个输入: 一个函数和一个列表, 并且使得tempxor(tempxor,L)会输出L的异或值!

我们的第一次尝试可能只是简单地用me替换递归调用. 让我们将这个函数定义为myxor

def myxor(me,L): return xor2(head(L),me(tail(L))) if L else 0

让我们测试一下:

myxor(myxor,[1,0,1])

如果你这样做,解释器会给出以下错误:

TypeError: myxor() missing 1 required positional argument

问题是myxor期望两个输入: 一个函数和一个列表. 而在调用me时, 我们只提供了一个列表. 为了纠正这一点, 我们修改调用, 同时提供函数本身:

def tempxor(me,L): return xor2(head(L),me(me,tail(L))) if L else 0

注意在tempxor的定义中对me(me,..)的调用: 给定一个函数me作为输入, tempxor实际上会以自身作为第一个输入来调用函数me. 如果我们现在测试一下, 会发现实际上得到了正确的结果!

tempxor(tempxor,[1,0,1])
# 0
tempxor(tempxor,[1,0,1,1])
# 1

因此, 我们可以将xor(L)简单地定义为return tempxor(tempxor,L).

上述方法不仅适用于XOR. 给定一个接受输入x的递归函数f, 我们可以获得一个非递归版本, 如下所示:

1. 创建函数myf, 它接受两个输入me和x,并将对f的递归调用替换为对me的调用.
2. 创建函数tempf,它将myf中形式为me(x)的调用转换为形式为me(me,x)的调用.
3. 函数f(x)将被定义为tempf(tempf,x).

以下是我们如何在Python中实现RECURSE运算符的方式. 它将接受一个如上所述的函数myf, 并将其替换为一个函数g, 使得对于每个x, g(x)=myf(g,x).

def RECURSE(myf):
    def tempf(me,x): return myf(lambda y: me(me,y),x)

    return lambda x: tempf(tempf,x)


xor = RECURSE(myxor)

print(xor([0,1,1,0,0,1]))
# 1

print(xor([1,1,0,0,1,1,1,1]))
# 0

从Python到λ演算: 在λ演算中, 一个接受两个输入$me,y$的函数$g$被写作$\lambda me.(\lambda y.g).$ 因此, 函数$y\mapsto me(me,y)$被简单地写作$meme,$ 类似地, 函数$x\mapsto \text{tempf}(\text{tempf},x)$就是$\text{tempf}\text{tempf}$ (你明白为什么吗?) 因此, 上述定义的函数tempf可以写作λ me. myf(me me). 这意味着, 如果我们将RECURSE的输入记为$f,$ 那么$\text{RECURSE}\text{myf}=\text{tempf}\text{tempf},$ 其中$\text{tempf}=\lambda m.f(m;m),$ 或者换句话说

$$\text{RECURSE}=\lambda f.((\lambda m.f(mm))(\lambda m.f(mm)))$$

在线附录包含一个使用Python实现的λ演算. 以下是该附录中递归XOR函数的实现: ³

# XOR of two bits
XOR2 = λ(a,b)(IF(a,IF(b,_0,_1),b))

# Recursive XOR with recursive calls replaced by m parameter
myXOR = λ(m,l)(IF(ISEMPTY(l),_0,XOR2(HEAD(l),m(TAIL(l)))))

# Recurse operator (aka Y combinator)
RECURSE = λf((λm(f(m*m)))(λm(f(m*m))))

# XOR function
XOR = RECURSE(myXOR)

#TESTING:

XOR(PAIR(_1,NIL)) # List [1]
# equals 1

XOR(PAIR(_1,PAIR(_0,PAIR(_1,NIL)))) # List [1,0,1]
# equals 0

8.8 Church-Turing论题(讨论)

我们定义了一个函数是可计算的, 如果它可以通过NAND-TM程序进行计算, 并且我们已经看到, 如果我们将NAND-TM程序替换为Python程序, 图灵机, λ演算, 元胞自动机以及许多其他计算模型, 该定义将保持不变. Church-Turing论题指出, 这是“可计算“函数的唯一合理定义. 与我们之前看到的“物理扩展Church-Turing论题“(PECTT)不同, Church-Turing论题并未做出可以通过实验检验的具体物理预测, 但它确实激励了诸如PECTT之类的预测. 我们可以将Church-Turing论题视为一种定义选择的提倡, 对所有潜在计算设备做出某种预测, 或者提出一些约束自然界的自然法则. 用Scott Aaronson的话来说, “无论它是什么, Church-Turing论题只能被视为极其成功”. 迄今为止, 尚无候选计算设备(包括量子计算机, 以及更不合理的模型, 例如我们之前提到的假设性“封闭时间曲线“计算机)对Church-Turing论题构成严肃挑战. 这些设备可能使某些计算更高效, 但并未改变有限可计算与不可计算之间的界限.(我们在第13.3节讨论的扩展Church-Turing论题规定, 图灵机也捕获了可高效计算内容的极限. 正如其物理版本所言, 量子计算对这一论题构成了主要挑战)

8.8.1 不同的计算模型

我们可以将我们已经看到的模型总结在以下表格中:

在第17章中, 我们将研究_内存受限_计算. 事实证明, 具有常量内存的NAND-TM程序等价于有限自动机(finite automata)模型(有时也会加上“确定性“或“非确定性“的形容词, 该模型也被称为有限状态机(finite state machines)), 它又捕获了正则语言(regular language)的概念(那些可以用正则表达式描述的语言), 这是我们将在第10章中看到的概念.

8.9 习题

if search('110011') {
    replace('110011','00')
} else if search('110111') {
    replace('110111','00')
} else if search('111011') {
    replace('111011','00')
} else if search('111111') {
    replace('1111111','00')
}

8.10 参考文献

Moore和Mertens的杰出著作(Moore, Mertens, 2011)第七章对这部分内容进行了精彩阐述.

RAM模型在研究实用算法的具体复杂度时非常有效, 其理论研究始于Cook和Reckhow(Cook, Reckhow, 1973). 不过需要注意的是, 不同文献和场景中对RAM模型允许的操作集及其成本定义存在差异. 正如Shamir(Shamir, 1979)已指出的, 在定义时需要特别谨慎——尤其是在字长可变的情况下. Savage著作(Savage, 1998)第三章给出了RAM机更形式化的描述, 亦可参阅Hagerup的论文(Hagerup, 1998). 关于不依赖输入规模的RAM算法研究(即transdichotomous RAM model)则由Fredman和Willard(Fredman, Willard, 1993)开创.

目前讨论的计算模型本质上是串行的, 但当今大量计算已转向并行模式——无论是通过多核处理器, 还是通过数据中心或互联网的大规模分布式计算. 虽然并行计算在实践中至关重要, 但对于“可计算与不可计算“的界限问题并未产生本质影响. 毕竟, 若计算任务可由$m$台机器在$t$时间内完成, 那么单台机器只需$mt$时间同样可以完成.

λ演算由Church(Church, 1941)提出. Pierce的专著(Pierce, 2002)是该领域权威教材, 另可参考Barendregt的著作(Barendregt, 1984). “柯里化“以逻辑学家Haskell Curry命名(Haskell编程语言同样得名于他). Curry本人认为这一概念应归功于Moses Schönfinkel, 但出于某种原因, “Schönfinkeling“这一术语始终未能流行.