定义计算

学习目标

• 理解计算可以被精确建模.
• 学习 布尔电路 / 直线程序 的计算模型.
• 电路与直线程序的等价性.
• $\text{AND}$/$\text{OR}$/$\text{NOT}$ 与 $\text{NAND}$ 的等价性.
• 物理世界中的计算实例.

目录

• 3.1 定义计算
• 3.2 使用与($\text{AND}),$ 或($\text{OR}),$ 非($\text{NOT})$进行计算
  • 3.2.1 $\text{AND}$ 和 $\text{OR}$ 的一些性质
  • 3.2.2 扩展例子: 计算异或($\text{XOR})$
  • 3.2.3 非正式地定义“基本运算“和“算法“
• 3.3 布尔电路
  • 3.3.1 布尔电路: 形式化定义
• 3.4 直线程序
  • 3.4.1 AON-CIRC 编程语言规范
  • 3.4.2 证明AON-CIRC程序与布尔电路的等价性
• 3.5 计算设备的物理实现 (插曲)
  • 3.5.1 晶体管
  • 3.5.2 由晶体管到逻辑门
  • 3.5.3 生物计算
  • 3.5.4 元胞自动机和生命游戏(GoL)
  • 3.5.5 神经网络
  • 3.5.6 利用弹珠和管道搭建的计算机
• 3.6 NAND函数
  • 3.6.1 $\text{NAND}$ 电路
  • 3.6.2 更多 $\text{NAND}$ 电路的例子 (选读)
  • 3.6.3 编程语言 NAND-CIRC
• 3.7 上述所有模型的等价性
  • 3.7.1 基于其它门集合的电路
  • 3.7.2 规范 vs. 实现 (再次强调)
• 习题
• 杂记

几千年来, 人类一直在进行计算, 不仅依靠纸笔, 还使用过算盘、计算尺、各种机械装置, 直到现代的电子计算机. 从先验的角度来看, 计算这一概念似乎总是依赖于所使用的具体工具. 例如, 你也许会认为, 在现代笔记本电脑上用 Python 实现的乘法算法, 与用纸笔进行乘法运算时的“最佳“算法会有所不同.

然而, 正如我们在引言中所看到的, 一个在渐近意义上更优的算法, 无论底层技术如何, 最终都会优于较差的算法. 这让我们看到希望: 可以找到一种独立于技术的方式来刻画计算的概念.

本章正是要做这件事. 我们将把“从输入计算输出“定义为一系列基本操作的应用 (见下图) . 借助这一框架, 我们便能精确地表述诸如: “函数 $f$ 可以由模型 $X$ 计算“或“函数 $f$ 可以由模型 $X$ 在 $s$ 步操作内计算完成“这样的命题.

3.1 定义计算

“算法“一词来源于对穆罕默德·伊本·穆萨·花剌子密(Muhammad ibn Musa al-Khwarizmi)名字的拉丁化转写. al-Khwarizmi 是九世纪的一位波斯学者, 他的著作向西方世界介绍了十进位值制数字系统, 以及一次方程与二次方程的解法 (见 下图) . 然而, 以今天的标准来看, al-Khwarizmi 对算法的描述的形式化程度相当不足. 他没有使用如 $x,y$ 这样的变量, 而是采用具体的数字 (如 10 和 39) , 并依赖读者从这些例子中自行类推出一般情况–这与当今儿童学习算法时的教学方式颇为相似.

以下是 al-Khwarizmi 对解形如 $x^2+bx=c$ 方程的算法的描述:

为了本书的目的, 我们需要一种更加精确的方式来描述算法. 幸运 (或者说不幸) 的是, 至少目前, 计算机在从实例中学习方面远远落后于学龄儿童. 因此, 在 20 世纪, 人们提出了用于精确描述算法的形式化语言, 即 编程语言.

下面是用 Python 转写的 al-Khwarizmi 二次方程求解算法:

from math import sqrt
# 使用 Python 的 sqrt 函数来计算平方根

def solve_eq(b, c):
    # 根据 al-Khwarizmi 的方法求解 x^2 + b*x = c
    # al-Khwarizmi 在 b=10, c=39 的例子中演示了这个方法

    val1 = b / 2.0  # "将根的数量减半"
    val2 = val1 * val1  # "将这个数平方"
    val3 = val2 + c  # "将平方结果加到 c 上"
    val4 = sqrt(val3)  # "取和的平方根"
    val5 = val4 - val1  # "从平方根中减去根数量的一半"
    return val5  # "这就是所求的平方根"

# 测试: 求解 x^2 + 10*x = 39
print(solve_eq(10, 39))
# 输出 3.0

我们可以非正式地定义算法如下:

在本章中, 我们将使用 布尔电路 (Boolean Circuits) 模型, 更精确而正式地定义算法. 我们将展示, 布尔电路在计算能力上等价于用“极简“编程语言编写的 直线程序 (straight line programs), 即不包含循环的编程语言. 我们还将看到, 具体选择哪种 基本运算 (elementary operations) 并不重要, 不同的选择都可以得到计算能力等价的模型 (见下图). 然而, 要理解这一点, 我们需要一些时间. 我们将从讨论什么是“基本运算“开始, 并说明如何将算法的描述映射为实际物理过程, 使其在现实世界中从输入生成输出.

3.2 使用与($\text{AND}),$ 或($\text{OR}),$ 非($\text{NOT})$进行计算

算法的表示需要将一个较为复杂的计算分解为一系列更简单的步骤. 这些步骤可以通过多种不同的方式来执行, 包括:

• 在纸上书写符号.
• 改变电线中的电流.
• 蛋白质与 DNA 链结合.
• 集体中的个体对刺激做出反应 (例如, 蜂群中的蜜蜂, 市场中的交易者) .

为了形式化地定义算法, 我们尝试“化繁为简“, 挑出组成算法的“最小单位“, 例如下列一组简单逻辑函数:

• 与函数 $\text{AND}:\{0,1{\}}^2\to \{0,1\}$ 定义为

$$\text{AND}(a,b)=\{\begin{array}{ll}1& a=b=1\\ 0& \text{otherwise}\end{array}$$

• 或函数 $\text{OR}:\{0,1{\}}^2\to \{0,1\}$ 定义为

$$\text{OR}(a,b)=\{\begin{array}{ll}0& a=b=0\\ 1& \text{otherwise}\end{array}$$

• 非函数 $\text{NOT}:\{0,1\}\to \{0,1\}$ 定义为

$$\text{NOT}(a)=\{\begin{array}{ll}0& a=1\\ 1& a=0\end{array}$$

函数 $\text{AND}$、$\text{OR}$ 和 $\text{NOT}$ 是逻辑学以及许多计算机系统中使用的基本逻辑运算符. 在逻辑学中, $\text{AND}(a,b)$ 表示为 $a\wedge b,$ $\text{OR}(a,b)$ 表示为 $a\vee b,$ $\text{NOT}(a)$ 表示为 $\overline{a}$ 或 $\neg a,$ 我们也将采用这种表示法.

每一个函数 $\text{AND},\text{OR},\text{NOT}$ 都以一个或两个单比特作为输入, 并输出一个单比特. 尽管这些运算看起来相当基本, 然而, 计算的威力正来源于将这些简单的运算组合在一起.

def MAJ(X[0],X[1],X[2]):
    firstpair  = AND(X[0],X[1])
    secondpair = AND(X[1],X[2])
    thirdpair  = AND(X[0],X[2])
    temp       = OR(secondpair,thirdpair)
    return OR(firstpair,temp)

3.2.1 $\text{AND}$ 和 $\text{OR}$ 的一些性质

与标准的加法和乘法类似, 函数 $\text{AND}$ 和 $\text{OR}$ 满足交换律: $a\vee b=b\vee a$ 和 $a\wedge b=b\wedge a,$ 以及结合律: $(a\vee b)\vee c=a\vee (b\vee c)$ 和 $(a\wedge b)\wedge c=a\wedge (b\wedge c).$

于是如同加法和乘法的情况, 我们通常可以省略括号, 将 $((a\vee b)\vee c)\vee d$ 写作 $a\vee b\vee c\vee d,$ 对更多项的 $\text{AND}$ 和 $\text{OR}$ 同理.

它们还满足分配律的一种变体:

3.2.2 扩展例子: 计算异或($\text{XOR})$

让我们看看如何用方才的基本运算得到一种新运算. 定义 $\text{XOR}:\{0,1{\}}^2\to \{0,1\}$ 为函数 $\text{XOR}(a,b)=a+b\mathrm{mod}2.$ 也就是说, $\text{XOR}(0,0)=\text{XOR}(1,1)=0,$ $\text{XOR}(1,0)=\text{XOR}(0,1)=1.$

我们指出, 可以仅使用 $\text{AND}$、$\text{OR}$ 和 $\text{NOT}$ 来构造 $\text{XOR}.$

以下算法使用 $\text{AND}$、$\text{OR}$ 和 $\text{NOT}$ 来计算 $\text{XOR}:$

我们也可以用编程语言来描述 算法 3.1. 特别, 以下是 $\text{XOR}$ 函数的 Python 实现:

def AND(a,b): return a*b
def OR(a,b):  return 1-(1-a)*(1-b)
def NOT(a):   return 1-a

def XOR(a,b):
    w1 = AND(a,b)
    w2 = NOT(w1)
    w3 = OR(a,b)
    return AND(w2,w3)

# 一个测试
print([f"XOR({a},{b})={XOR(a,b)}" for a in [0,1] for b in [0,1]])
# ['XOR(0,0)=0', 'XOR(0,1)=1', 'XOR(1,0)=1', 'XOR(1,1)=0']

def XOR3(a,b,c):
    w1 = AND(a,b)
    w2 = NOT(w1)
    w3 = OR(a,b)
    w4 = AND(w2,w3)
    w5 = AND(w4,c)
    w6 = NOT(w5)
    w7 = OR(w4,c)
    return AND(w6,w7)

# 一个小测试
print([f"XOR3({a},{b},{c})={XOR3(a,b,c)}" for a in [0,1] for b in [0,1] for c in [0,1]])
# ['XOR3(0,0,0)=0', 'XOR3(0,0,1)=1', 'XOR3(0,1,0)=1', 'XOR3(0,1,1)=0', 'XOR3(1,0,0)=1', 'XOR3(1,0,1)=0', 'XOR3(1,1,0)=0', 'XOR3(1,1,1)=1']

3.2.3 非正式地定义“基本运算“和“算法“

我们已经看到, 通过组合应用 $\text{AND}$、$\text{OR}$ 和 $\text{NOT}$ 可以得到一些有趣的函数. 这启发我们将 $\text{AND}$、$\text{OR}$ 和 $\text{NOT}$ 视为我们的基本运算, 从而给出如下关于算法的定义:

1. 首先, 这一定义确实过于非正式. 我们既没有精确说明每一步到底做了什么, 也没有明确“将 $x$ 作为输入“究竟是什么意思.

2. 其次, 选择 $\text{AND}$、$\text{OR}$ 或 $\text{NOT}$ 看起来相当任意. 为什么不是 $\text{XOR}$ 和 $\text{MAJ}$？为什么不允许加法和乘法这样的运算？又或者其他逻辑结构, 例如 if/then 或 while？

3. 第三, 我们是否确信该定义真的与实际计算有关？如果有人给出了这种算法的描述, 我们是否真的能够在现实中用它来计算相应的函数？

本书的很大一部分内容将致力于回答上述问题. 我们将看到:

1. 我们可以把算法的定义完全形式化, 从而为“算法 $A$ 计算函数 $f$“这样的表述赋予精确的数学含义.

2. 虽然选择 $\text{AND}$ / $\text{OR}$ / $\text{NOT}$ 看似任意, 我们本可以选择其他函数, 但实际上这种选择影响不大. 我们会看到, 即使改用加法和乘法, 或者几乎任何可以合理视为基本步骤的操作, 我们依然能够得到相同的计算能力.

3. 事实证明, 我们确实可以在现实世界中计算这种基于 $\text{AND}$ / $\text{OR}$ / $\text{NOT}$ 的算法. 首先, 这样的算法定义清晰, 因此人类可以用纸和笔逐步执行. 其次, 这种计算可以通过多种方式机械化. 我们已经看到, 可以编写 Python 程序来对应执行这样的指令序列. 而实际上, 还可以通过被称为晶体管的元件, 用电子信号直接实现 $\text{AND}$、$\text{OR}$ 和 $\text{NOT}$ 等操作. 这正是现代电子计算机的工作方式.

在本章余下的内容以及本书后续部分, 我们将开始回答这些问题. 我们会看到更多简单操作组合出复杂操作的实例, 包括加法、乘法、排序等. 同时, 我们还会讨论如何通过多种技术物理实现 $\text{AND}$、$\text{OR}$ 和 $\text{NOT}$ 等基本操作.

3.3 布尔电路

布尔电路提供了“组合基本运算“的精确定义. 一个布尔电路 (参见下图) 由门和输入组成, 并通过导线连接.

导线传递的信号表示值 $0$ 或 $1,$ 每个门对应 $\text{OR}$、$\text{AND}$ 或 $\text{NOT}$ 运算. 一个 $\text{OR}$ 门有两条输入导线和一条或多条输出导线, 如果这两条输入导线的信号分别为 $a$ 和 $b$ ($a,b\in \{0,1\})$ , 则输出导线上的信号为 $\text{OR}(a,b).$ $\text{AND}$ 和 $\text{NOT}$ 门的定义类似.

输入端只有输出导线. 如果我们将某个输入设为 $a\in \{0,1\},$ 则该值会沿其所有输出导线传播. 我们还将一些门指定为输出门, 其值对应于电路的计算结果. 例如, 上图 给出了一个用于计算 $\text{XOR}$ 函数的电路, 参考 节3.2.2.

对于一个 $n$ 输入的布尔电路 $C,$ 我们在输入端放置 $x\in \{0,1{\}}^n$ 的比特, 然后沿导线传播信号, 直到到达输出端, 从而完成电路的计算, 参见 下图.

3.3.1 布尔电路: 形式化定义

我们之前非正式地将布尔电路定义为通过导线连接 $\text{AND}$、$\text{OR}$ 和 $\text{NOT}$ 门, 从输入生成输出的电路.
然而, 为了能够证明关于计算各种函数的布尔电路存在性或非存在性的定理, 我们需要:

1. 将布尔电路作为数学对象进行形式化定义.
2. 正式定义电路 $C$ 计算函数 $f$ 的含义.

接下来我们将进行这一定义. 我们把布尔电路定义为带标记的有向无环图 (DAG) . 图的顶点对应电路的门和输入端, 图的边对应导线. 电路中从输入或门 $u$ 到门 $v$ 的导线对应顶点间的有向边. 输入顶点没有入边, 而每个门根据其计算的函数具有适当数量的入边 (即 $\text{AND}$ 和 $\text{OR}$ 门有两个入邻居, $\text{NOT}$ 门有一个入邻居) .

正式定义如下 (参见下图) :

如果 $C$ 是一个具有 $n$ 个输入和 $m$ 个输出的电路, 且 $x\in \{0,1{\}}^n,$ 则自然可以计算 $C$ 在输入 $x$ 下的输出:
将输入顶点 $X[0],$ $\dots ,$ $X[n-1]$ 赋值为 $x_0,\dots ,x_{n-1},$ 然后对每个门应用其入邻居的值, 最后输出对应于输出顶点的值.

形式化定义如下:

3.4 直线程序

我们已经看到两种使用 $\text{AND}$、$\text{OR}$ 和 $\text{NOT}$ 来计算函数 $f$ 的方式:

• 布尔电路, 在 定义 3.3 中定义, 通过将 $\text{AND}$、$\text{OR}$ 和 $\text{NOT}$ 门通过导线连接到输入来计算 $f.$

• 我们也可以使用 直线程序 来描述这样的计算, 该程序的每一行形式为 foo = AND(bar,blah)、foo = OR(bar,blah) 和 foo = NOT(bar), 其中 foo、bar 和 blah 是变量名. (称其为 直线程序, 因为它不包含循环或分支 (例如 if/then) 语句. )

为了更精确地描述第二种定义, 我们现在定义一种与布尔电路等价的 编程语言.
我们将这种编程语言称为 AON-CIRC 编程语言 (“AON” 代表 $\text{AND}/\text{OR}/\text{NOT}$；“CIRC” 代表 circuit) .

例如, 以下是一个 AON-CIRC 程序, 对于输入 $x\in \{0,1{\}}^2,$ 输出 $\overline{x_0\wedge x_1}$ (即对 $\text{AND}(x_0,x_1)$ 应用 $\text{NOT}$ 操作) :

temp = AND(X[0],X[1])
Y[0] = NOT(temp)

AON-CIRC 并不是一种实用的编程语言: 它仅用于教学目的, 用来将计算建模为 $\text{AND}$、$\text{OR}$ 和 $\text{NOT}$ 的组合. 然而, 它仍然可以很容易地在计算机上实现.

根据这个例子, 你可能已经能够猜到如何编写程序来计算 (例如) $x_0\wedge \overline{x_1\vee x_2},$ 以及更一般地, 如何将布尔电路翻译为 AON-CIRC 程序. 但是, 由于我们希望对 AON-CIRC 程序证明数学性质, 我们需要精确定义 AON-CIRC 编程语言.

编程语言的精确定义有时可能冗长且枯燥, 例如, C 语言规范 就超过 500 页. 但对于安全可靠的实现至关重要. 幸运的是, AON-CIRC 编程语言足够简单, 我们可以相对轻松地对其进行正式定义.

3.4.1 AON-CIRC 编程语言规范

一个 AON-CIRC 程序是一系列字符串, 我们称之为“行“, 满足以下条件:

• 每一行具有以下形式之一: foo = AND(bar,baz)、foo = OR(bar,baz) 或 foo = NOT(bar), 其中 foo、bar 和 baz 是 变量标识符. (我们遵循常见的 编程语言惯例, 使用 foo、bar、baz 等名称作为通用标识符的示例. )
  行 foo = AND(bar,baz) 对应于将变量 foo 赋值为变量 bar 和 baz 的逻辑 $\text{AND}.$ 类似地, foo = OR(bar,baz) 和 foo = NOT(bar) 分别对应逻辑 $\text{OR}$ 和逻辑 $\text{NOT}$ 操作.

• AON-CIRC 编程语言中的 变量标识符 可以由字母、数字、下划线和方括号的任意组合构成. 有两类特殊变量:

  • 形式为 X[i] 的变量, 其中 $i\in \{0,1,\dots ,n-1\},$ 称为 输入变量.
  • 形式为 Y[j] 的变量, 称为 输出变量.

• 一个有效的 AON-CIRC 程序 $P$ 包含输入变量 X[0], $\dots ,$ X[n-1] 和输出变量 Y[0], $\dots ,$ Y[m-1], 其中 $n,m$ 为自然数. 我们称 $n$ 为程序 $P$ 的 输入数, $m$ 为 输出数.

• 在有效的 AON-CIRC 程序中, 每一行右侧的变量必须是输入变量或在之前的行中已经被赋值的变量.

• 若 $P$ 是一个具有 $n$ 个输入和 $m$ 个输出的有效 AON-CIRC 程序, 则对于每个 $x\in \{0,1{\}}^n,$ 程序 $P$ 在输入 $x$ 上的 输出 是字符串 $y\in \{0,1{\}}^m,$ 定义如下:

  • 将输入变量 X[0], $\dots ,$ X[n-1] 初始化为 $x_0,\dots ,x_{n-1}.$
  • 按顺序逐行执行 $P$ 的操作行, 在每行中将左侧变量赋值为右侧操作的结果.
  • 执行结束后, 令 $y\in \{0,1{\}}^m$ 为输出变量 Y[0], $\dots ,$ Y[m-1] 的值.

• 我们用 $P(x)$ 表示程序 $P$ 在输入 $x$ 上的输出.

• AON-CIRC 程序 $P$ 的 规模 是它包含的行数. (读者可能注意到, 这与我们定义的电路规模–门的数量–是一致的. )

现在我们已经正式定义了 AON-CIRC 程序的规范, 就可以定义 AON-CIRC 程序 $P$ 计算一个函数 $f$ 的含义:

# Compute CMP:{0,1}^4-->{0,1}
# CMP(X)=1 iff 2X[0]+X[1] > 2X[2] + X[3]
temp_1 = NOT(X[2])
temp_2 = AND(X[0],temp_1)
temp_3 = OR(X[0],temp_1)
temp_4 = NOT(X[3])
temp_5 = AND(X[1],temp_4)
temp_6 = AND(temp_5,temp_3)
Y[0] = OR(temp_2,temp_6)

3.4.2 证明AON-CIRC程序与布尔电路的等价性

我们现在正式证明 AON-CIRC 程序和布尔电路具有完全相同的计算能力:

3.5 计算设备的物理实现 (插曲)

计算是一个抽象概念, 它并不等同于其物理实现.
虽然大多数现代计算设备是通过将逻辑门映射到基于半导体的晶体管实现的, 但纵观历史, 人类曾经使用过各种各样的机制来进行计算, 包括机械系统、气体与液体 (称为流体计算) 、生物和化学过程, 甚至是生物体本身 (参见下图或这个视频, 了解螃蟹或黏菌如何被用于计算) .

在本节中, 我们将回顾这些实现方式, 以帮助理解如何能够将布尔电路直接转化为物理世界中的系统, 而无需经过体系结构、操作系统和编译器的完整抽象层. 同时, 这也强调了基于硅的处理器绝不是实现计算的唯一方式.

事实上, 正如我们将在第23章 中看到的, 一个令人兴奋的研究方向是使用不同的介质来进行计算, 从而利用量子力学效应来实现全新的算法类型.

Such a cool way to explain logic gates. pic.twitter.com/6Wgu2ZKFCx

— Lionel Page (\@page_eco) 2019年10月28日

3.5.1 晶体管

晶体管 (transistor) 可以看作是一个具有两个输入和一个输出的电路: 输入称为源极 (source) 和栅极 (gate) , 输出称为漏极 (sink) .
栅极决定了电流是否能够从源极流向漏极.

• 在标准晶体管中, 如果栅极处于“开 (ON) “状态, 则电流可以从源极流向漏极；如果栅极处于“关 (OFF) “状态, 则电流无法流动.
• 在互补晶体管中, 情况正好相反: 栅极“关“时允许电流流动, 而栅极“开“时则不允许.

实现晶体管逻辑的方法有很多. 例如, 可以通过水压与水龙头的开合来模拟晶体管的工作 (见上图) . 这似乎只是个小趣味, 但事实上有一个名为流体计算 (fluidics) 的研究领域, 专门研究如何利用液体或气体实现逻辑运算. 其动机之一是在极端环境 (如太空或战场) 中工作, 因为在这些环境下常规电子设备可能无法存活.

晶体管的标准实现是通过电流. 而最早的实现方式之一是真空管. 顾名思义, 真空管是一个内部抽空的管子, 电子可以自由地从源 (电丝) 流向漏 (金属板) . 但在它们之间有一个“栅极“ (网格) , 通过调节其电压可以阻止电子的流动.

早期真空管大约有灯泡那么大 (外形也很像灯泡) . 到 1950 年代, 它们被晶体管取代. 晶体管利用半导体实现相同的逻辑. 半导体在正常情况下不导电, 但通过掺杂 (doping) 以及施加外部电场, 可以调控其导电性 (即场效应) .

进入 1960 年代后, 计算机开始使用集成电路 (integrated circuits) , 极大提高了晶体管的集成密度. 1965 年, 戈登·摩尔 (Gordon Moore) 预测集成电路中晶体管的数量大约每年会翻一番 (见下图) . 他还推测这将带来“诸如家庭计算机–或至少是接入中央计算机的终端–、汽车的自动控制, 以及个人便携通信设备等奇迹“.

从那时起, 经调整后的“摩尔定律“基本上一直成立, 尽管指数级增长不可能无限持续, 一些物理极限已经逐渐显现.

3.5.2 由晶体管到逻辑门

我们可以使用晶体管来实现各种布尔函数, 例如 $\text{AND}$、$\text{OR}$ 和 $\text{NOT}.$
对于每一个二输入门 $G:\{0,1{\}}^2\to \{0,1\},$ 其实现方式是一个具有两个输入导线 $x,y$ 和一个输出导线 $z$ 的系统. 若我们将高电压视为“$1$“, 低电压视为”$0$“, 那么当且仅当 $G(x,y)=1$ 时, 导线 $z$ 的值为”$1$“ (参见下列逻辑门的晶体管实现 和NAND实现) .

这意味着: 如果存在一个 $\text{AND}/\text{OR}/\text{NOT}$ 电路可以计算函数 $g:\{0,1{\}}^n\to \{0,1{\}}^m,$ 那么我们也可以在物理世界中通过晶体管来计算 $g.$

3.5.3 生物计算

计算也可以基于生物或化学系统. 例如, lac 操纵子 仅在条件 $x\wedge (\neg y)$ 成立时才会产生消化乳糖所需的酶, 其中 $x$ 表示“存在乳糖“, $y$ 表示“存在葡萄糖“.

研究人员已经成功制造出基于 DNA 分子的晶体管, 并由此构建逻辑门 (参见下图) . 诸如 Cello 编程语言 这样的项目, 能够将布尔电路转换为 DNA 序列, 从而在细菌细胞中执行运算 (参见该视频) .

DNA 计算的动机之一是实现更高的并行性或存储密度；另一个动机是创造“智能生物因子“, 这些因子或许能够被注入体内, 自我复制, 并修复或杀死因癌症等疾病损伤的细胞.

当然, 生物系统中的计算不仅限于 DNA: 甚至更大规模的系统, 例如鸟群, 也可以被视为计算过程.

3.5.4 元胞自动机和生命游戏(GoL)

元胞自动机是一种由一系列细胞组成的系统模型, 每个细胞都可以处于有限的状态之一.
在每一步中, 细胞会根据其邻居细胞的状态以及一些简单规则来更新自身状态.

正如我们将在本书后续部分讨论的那样 (参见 cellularautomatasec) , 元胞自动机 (例如康威的“生命游戏“) 可以用来模拟计算门.

3.5.5 神经网络

我们每个人都随身携带的一种计算设备就是我们自己的大脑. 大脑在人类历史上一直发挥作用, 从区分猎物与捕食者, 到进行科学发现和艺术创作, 再到写出精巧的 280 字短消息. 大脑的确切工作机制仍未完全被理解, 但一种常见的数学模型是 (非常庞大的) 神经网络.

神经网络可以看作布尔电路, 只是它并非以 $\text{AND}$ / $\text{OR}$ / $\text{NOT}$ 为基本门, 而是使用其他类型的基本门. 例如, 一种可以使用的基是阈值门.

对于每个整数向量 $w=(w_0,\dots ,w_{k-1})$ 和整数 $t$ (其中一些分量可以为负) , 定义对应的阈值函数 $T_{w,t}:\{0,1{\}}^k\to \{0,1\}$ 为: 当且仅当 ${\sum }_{i=0}^{k-1}{w}_i{x}_i\ge t$ 时, 输入 $x\in \{0,1{\}}^k$ 被映射为 $1.$

例如, 向量 $w=(1,1,1,1,1)$ 与阈值 $t=3$ 所对应的 $T_{w,t},$ 就是 $\{0,1{\}}^5$ 上的多数函数 ${\text{MAJ}}_5.$ 阈值门可以看作对构成人类与动物大脑核心的神经元的一种近似. 粗略来说, 一个神经元有 $k$ 个输入和一个输出, 当这些信号的强度超过某个阈值时, 神经元就会“触发“或“激活“其输出.

许多机器学习算法采用的人工神经网络并非旨在模仿生物学, 而是为了执行某些计算任务, 因此它们并不局限于阈值门或其他生物学启发的门. 通常来说, 神经网络的输入信号被视为实数而非 $0/1$ 值, 并且一个门的输出是通过计算 $f({\sum }_i{w}_i{x}_i)$ 得到的, 其中 $f:\mathbb{R}\to \mathbb{R}$ 是某种激活函数, 例如修正线性单元 (ReLU) 、Sigmoid 或其他函数 (见下图) .

不过, 就我们讨论的范围而言, 上述所有模型在本质上是等价的 (参见 习题 3.13) . 特别是, 我们可以通过二进制表示实数并将对应权重乘以 $2^i$ 的方式, 将实数输入化为二进制输入.

3.5.6 利用弹珠和管道搭建的计算机

我们可以利用许多其他物理介质来实现计算, 而无需任何电子、生物或化学组件. 人们曾经提出许多关于机械计算机的构想, 至少可以追溯到 1670 年代 Gottfried Leibniz 的计算机, 以及 Charles Babbage 1837 年提出的机械“解析引擎“计划.

打个比方, 下图 展示了使用弹珠通过管道来实现 $\text{NAND}$ ($\text{AND}$ 的取反, 参见 3.6节) 门的简单方法. 我们通过一对管道表示逻辑值 $\{0,1\},$ 保证恰好有一颗弹珠在其中一条管道中流动. 将其中一条管道称为“$0$ 管“, 另一条管道称为“$1$ 管“, 弹珠所在管道的身份决定逻辑值.

一个 $\text{NAND}$ 门对应一个机械装置, 具有两对输入管道和一对输出管道, 使得对于每个 $a,b\in \{0,1\},$ 如果两颗弹珠分别沿第一对管道的 $a$ 管和第二对管道的 $b$ 管滚向装置, 那么弹珠将沿输出对中对应 $\text{NAND}(a,b)$ 的管道滚出.

事实上, 市面上还有一个以弹珠为计算基础的教育游戏, 参见下方的Turing Tumble.

3.6 NAND函数

$\text{NAND}$ 函数是另一个非常简单且在定义计算中极为有用的函数.
它是一个将 $\{0,1{\}}^2$ 映射到 $\{0,1\}$ 的函数, 定义为:

$$\text{NAND}(a,b)=\{\begin{array}{ll}0& a=b=1\\ 1& \text{否则}\end{array}.$$

顾名思义, $\text{NAND}$ 是 AND 的取反 (即 $\text{NAND}(a,b)=\text{NOT}(\text{AND}(a,b)))$ , 因此显然可以使用 $\text{AND}$ 和 $\text{NOT}$ 来计算 $\text{NAND}.$
有趣的是, 反过来我们也有:

我们可以使用 $\text{NAND}$ 来计算许多其他函数, 如以下练习所示.

3.6.1 $\text{NAND}$ 电路

我们将 $\text{NAND}$ 电路 定义为所有逻辑门均为 $\text{NAND}$ 运算的电路.
这样的电路同样对应一个有向无环图 (DAG) , 因为所有逻辑门都执行相同的功能 (即 $\text{NAND})$ , 因此甚至无需对它们进行标记, 并且所有逻辑门的入度都恰好为 2.
尽管形式简单, $\text{NAND}$ 电路却具有相当强大的能力.

事实上, 我们可以证明以下定理:

3.6.2 更多 $\text{NAND}$ 电路的例子 (选读)

下面给出一些更复杂的 $\text{NAND}$ 电路示例:

后继数: 考虑如下任务: 输入一个字符串 $x\in \{0,1{\}}^n,$ 它表示一个自然数 $X\in \mathbb{N},$ 我们希望计算 $X+1.$ 换句话说, 我们希望计算函数
$${\text{INC}}_n:\{0,1{\}}^n\to \{0,1{\}}^{n+1}$$
使得对于任意 $x_0,\dots ,x_{n-1},$ 有 ${\text{INC}}_n(x)=y,$ 并且满足
$$\sum _{i=0}^n{y}_i{2}^i=\left(\sum _{i=0}^{n-1}{x}_i{2}^i\right)+1.$$
(为了书写简洁, 在此示例中我们采用最低有效位在前而不是在后的表示方式. )

后继操作可以非正式地描述为: “将 $1$ 加到最低有效位并向高位传递进位”.
更准确地说, 在二进制表示的情形下, 要得到 $x$ 的后继, 我们从最低有效位开始扫描 $x,$ 把所有的 $1$ 翻转为 $0,$ 直到遇到一个等于 $0$ 的比特, 把它翻转为 $1$ 并停止.

因此, 我们可以通过以下步骤来计算 $x_0,\dots ,x_{n-1}$ 的后继:

算法 3.2 精确描述了如何计算后继, 并且可以很容易地转化为执行相同计算的 Python 代码, 但它似乎不能直接生成一个计算该运算的 $\text{NAND}$ 电路.
然而, 我们可以逐行将该算法转换为 $\text{NAND}$ 电路.

例如, 由于对任意 $a$ 都有 $\text{NAND}(a,\text{NOT}(a))=1,$ 我们可以将最初的语句 $c_0=1$ 替换为
$c_0=\text{NAND}(x_0,\text{NAND}(x_0,x_0)).$

我们已经知道如何用 $\text{NAND}$ 实现 $\text{XOR},$ 因此可以用它来实现操作 $y_i\leftarrow \text{XOR}(x_i,c_i).$

类似地, 可以将 “if” 语句写作 $c_{i+1}\leftarrow \text{AND}(c_i,x_i),$ 也就是
$c_{i+1}\leftarrow \text{NAND}(\text{NAND}(c_i,x_i),\text{NAND}(c_i,x_i)).$

最后, 赋值 $y_n=c_n$ 可以写作
$y_n=\text{NAND}(\text{NAND}(c_n,c_n),\text{NAND}(c_n,c_n)).$

结合这些观察, 对于任意 $n\in \mathbb{N},$ 我们就得到了一个计算 ${\text{INC}}_n$ 的 $\text{NAND}$ 电路.
例如, 下图展示了 $n=4$ 时该电路的样子.

从自增到加法

一旦有了自增运算, 我们当然可以通过重复自增来计算加法 (即通过对 $x$ 执行 $y$ 次 $\text{INC}(x)$ 来计算 $x+y)$ . 然而, 这种方法既低效又没有必要.

利用同样的进位跟踪思想, 我们可以实现“中学“加法算法, 并计算函数 ${\text{ADD}}_n:\{0,1{\}}^{2n}\to \{0,1{\}}^{n+1},$ 其在输入 $x\in \{0,1{\}}^{2n}$ 时输出由 $x_0,\dots ,x_{n-1}$ 与 $x_n,\dots ,x_{2n-1}$ 所表示的两个数之和的二进制表示:

同样地, 算法 3.3 可以被转换为 $\text{NAND}$ 电路.
关键的观察是, “if/then” 语句实际上对应于 $c_{i+1}\leftarrow {\text{MAJ}}_3(u_i,v_i,v_i),$ 而我们在 练习 3.5 中已经看到函数 ${\text{MAJ}}_3:\{0,1{\}}^3\to \{0,1\}$ 可以用 $\text{NAND}$ 实现.

3.6.3 编程语言 NAND-CIRC

正如我们为布尔电路所做的那样, 我们可以定义 NAND 电路对应的编程语言.
它甚至比 AON-CIRC 语言更简单, 因为这里只有一种操作.

我们将 NAND-CIRC 编程语言 定义为这样一种编程语言, 其中每行 (除了输入/输出声明外) 具有以下形式:

foo = NAND(bar,blah)

其中 foo, bar 和 blah 指代变量.

u = NAND(X[0],X[1])
v = NAND(X[0],u)
w = NAND(X[1],u)
Y[0] = NAND(v,w)

形式上, 就像我们在 定义 3.5 中对 AON-CIRC 所做的那样, 我们可以以自然的方式定义 NAND-CIRC 程序的计算概念:

和之前一样, 我们可以证明 NAND 电路与 NAND-CIRC 程序是等价的 (见下图).

我们省略 定理 3.4 的证明, 因为其思路与布尔电路与 AON-CIRC 程序等价的证明完全相同 (参见 定理 3.1) .

根据 定理 3.3 和 定理 3.4, 我们知道可以将任意 $s$ 行的 AON-CIRC 程序 $P$ 翻译为一个等价的 NAND-CIRC 程序, 行数最多为 $3s.$
实际上, 这种翻译可以通过将每一行 foo = AND(bar,blah)、foo = OR(bar,blah) 或 foo = NOT(bar) 替换为使用 NAND 的等价 1-3 行来轻松完成.

我们的 GitHub 仓库 提供了“代码证明“: 一个简单的 Python 程序 AON2NAND, 可以将 AON-CIRC 转换为等价的 NAND-CIRC 程序.

3.7 上述所有模型的等价性

如果我们将 定理 3.1、定理 3.3 和 定理 3.4 结合起来, 可得到以下结论:

定理 3.1 是一个更一般结果的特例.
我们可以考虑更一般的计算模型, 其中不仅使用 AND/OR/NOT 或 NAND, 还可以使用其他运算 (参见下文) . 事实证明, 布尔电路在计算能力上与这些模型也是等价的.

所有这些不同的计算定义方式最终导致等价模型, 这表明我们“走在正确的道路上“. 它证明了我们选择 AND/OR/NOT 或 NAND 作为基本操作的看似任意的选择是合理的, 因为这些选择并不影响计算模型的能力. 像 定理 3.5 这样的等价结果意味着我们可以轻松地在布尔电路、NAND 电路、NAND-CIRC 程序等之间进行转换. 在本书后续内容中, 我们将经常利用这一能力, 通常会根据方便选择最合适的表述, 而不会过分纠结. 因此, 我们不会过于担心例如布尔电路与 NAND-CIRC 程序之间的区别.

相比之下, 我们将继续特别注意区分电路/程序与函数 (回忆 functionprogramidea) .
一个函数对应于计算任务的规范, 它本质上不同于程序或电路, 后者对应于任务的实现.

3.7.1 基于其它门集合的电路

$\text{AND}/\text{OR}/\text{NOT}$ 或 $\text{NAND}$ 并没有什么特别之处. 对于任意函数集合 $\mathcal{G}=\{G_0,\dots ,G_{k-1}\},$ 我们可以定义使用 $\mathcal{G}$ 中元素作为门的电路的概念, 以及一个“$\mathcal{G}$ 编程语言“的概念, 其中每一行都将一个变量 foo 赋值为对某个 $G_i\in \mathcal{G}$ 应用于先前定义的变量或输入变量的结果.

具体而言, 我们可以做如下定义:

AON-CIRC 程序对应于 $\{\text{AND},\text{OR},\text{NOT}\}$ 程序, NAND-CIRC 程序对应于仅包含 $\text{NAND}$ 函数的 $\mathcal{F}$ 程序, 但我们也可以定义 $\{\text{IF,ZERO,ONE}\}$ 程序 (见下文) , 或者使用任意其他集合.

我们还可以定义 $\mathcal{F}$ 电路, 它是一个有向图, 其中每个 门 对应于应用某个 $f_i\in \mathcal{F}$ 的操作, 每个门有 $k_i$ 条入边和一条出边. (如果函数 $f_i$ 不是对称的, 即输入顺序会影响结果, 那么我们需要标记每条入边对应函数的哪个参数. )

正如在 定理 3.1 中, 我们可以证明 $\mathcal{F}$ 电路与 $\mathcal{F}$ 程序是等价的.
我们已经看到, 对于 $\mathcal{F}=\{AND,OR,NOT\},$ 生成的电路/程序在计算能力上等价于 NAND-CIRC 编程语言, 因为我们可以用 $\text{AND}$/$\text{OR}$/$\text{NOT}$ 计算 $\text{NAND},$ 反之亦然.

这实际上是一个更一般现象的特例–$\text{NAND}$ 和其他门集的通用性–我们将在本书后续章节中深入探讨.

也存在一些计算能力更受限的集合 $\mathcal{F}.$
例如, 可以证明, 如果我们只使用 $\text{AND}$ 或 $\text{OR}$ 门 (不使用 $\text{NOT})$ , 则无法得到等价的计算模型.
练习中提供了几个通用门集与非通用门集的示例.

3.7.2 规范 vs. 实现 (再次强调)

正如我们在 secimplvsspec 中讨论的, 本书中最重要的区别之一是规范与实现的区分, 即分离“做什么“和“如何做“ (见上图) .
一个 函数 对应于计算任务的规范, 即对于每个特定输入应该产生什么输出.
一个 程序 (或电路, 或其他任何用于指定算法的方式) 对应于实现, 即如何从输入计算所需输出.
也就是说, 程序是一组从输入计算输出的指令.

即便在同一个计算模型内, 也可能有多种不同方式来计算同一个函数. 例如, 计算多数函数的 NAND-CIRC 程序不止一个, 计算加法函数的布尔电路也不止一个, 等等.

混淆规范与实现 (或等价地, 函数与程序) 是一个常见错误, 而编程语言中常将程序部分称为“函数“也在一定程度上助长了这种误解. 然而, 在计算机科学的理论与实践中, 保持这一区别非常重要, 本书尤其重视这一点.

习题