• 计算与表示
  • 学习目标
  • 2.1 定义表示
    • 2.1.1 表示自然数
    • 2.1.2 表示的意义(讨论)
  • 2.2 自然数以外对象的表示
    • 2.2.1 表示带有负数的全体整数
    • 2.2.2 补码表示(选读)
    • 2.2.3 有理数及字符串表示对
  • 2.3 实数的表示
  • 2.4 Cantor定理, 可数集, 以及实数的字符串表示
    • 2.4.1 推论: 布尔函数全体不可数.
    • 2.4.2 可数性的等价条件
  • 2.5 数字以外元素的表示
    • 2.5.1 有限表示
    • 2.5.2 前缀无关编码
    • 2.5.3 构造前缀无关表示
    • 2.5.4 “基于Python的证明” (选读)
    • 2.5.5 字母和文本的表示
    • 2.5.6 向量, 矩阵及图片的表示
    • 2.5.7 图的表示
    • 2.5.8 列表和嵌套列表的表示
    • 2.5.9 一些注释
  • 2.6 将计算任务定义为数学函数
    • 2.6.1 注意区分 函数 和 程序!
  • 2.7 习题
  • 2.8 参考书目

计算与表示

学习目标

• 区分规范与实现, 亦即区分数学函数与算法/程序.
• 将对象表示为字符串(通常由 0 和 1 构成).
• 常见对象(如自然数、向量、列表与图)的表示实例.
• 前缀无关编码.
• Cantor定理: 实数无法被有限长字符串精确表示.

从初步的角度看, 计算 是一个将 输入 映射为 输出 的过程.

在谈论计算时, 一个关键点是要区分两个问题: 需要完成的任务是什么(即规范), 以及 如何去实现这一任务(即实现方式). 例如, 正如我们已经看到的, 计算两个整数的乘积这一任务, 并不只有唯一的一种实现方式.

在本章中, 我们将聚焦于 “是什么” 部分, 即如何定义计算任务. 而这首先要求我们明确定义 输入与输出. 要囊括所有可能的输入和输出似乎颇具挑战性, 因为如今计算已经被应用在各种各样的对象上, 不仅是数字, 还可以是文本, 图像, 视频, 例如社交网络的连接图, MRI 扫描结果, 基因组数据, 甚至是其它程序.

我们将尝试把所有这些对象表示为 由 0 和 1 组成的字符串, 也就是诸如 $0011101,$ $1011,$ 或任意有限个 $0$ 与 $1$ 组成的序列. (当然, 这样的选择只是出于方便, 0 和 1 并非 “神圣” 而不可替代: 我们完全可以用任何其他有限集合的符号来表示.)

如今, 我们已经对数字化的表示习以为常, 因而并不会对这种编码的存在感到惊讶, 但这实际上是一个深刻的结果, 并带来了许多重要的影响. 许多动物也能够表达某种恐惧或欲望, 但人类独特之处在于 语言: 我们使用有限的一组基本符号来描述潜在无限范围的体验. 语言使得信息能够跨越时间与空间进行传递, 并让社会能够涵盖大量的人群, 随时间积累出共享的知识体系.

在过去的几十年里, 我们见证了一场关于数字化表示与传递的革命: 我们现在几乎可以完美地捕捉视觉与听觉的体验, 并几乎瞬间将其传播给无限的受众. 更重要的是, 一旦信息以数字形式存在, 我们便能够对其进行 计算, 并从中获取以往无法触及的数据洞见. 这场革命的核心, 是一个简单却深刻的观察: 我们能够用有限的一组符号 (事实上仅需两个符号 0 和 1) 来表示无穷多样的对象.

在后续的章节中, 我们通常会默认这种表示方法的存在, 因此会使用诸如 “程序 $P$ 以 $x$ 为输入” 这样的表述, 即便 $x$ 可能是一个数字、向量、图, 或者其他任意对象. 不过我们真正的意思是, $P$ 的输入实际上是 $x$ 的 二进制字符串表示. 在本章中, 我们会更深入地探讨如何构造这样的表示方法.

2.1 定义表示

每当我们在计算机中存储数字、图像、声音、数据库或其他对象时, 实际上存储在计算机内存中的只是这些对象的 表示.
此外, “表示” 的概念并不限于电子计算机, 当我们写下文字或画一幅图时, 我们同样是在将思想或体验 表示 为符号序列 (这些符号也完全可以是由 0 和 1 构成的字符串), 甚至我们的脑中也并非储存真实的感官输入, 而是仅仅存储它们的 表示.

为了在计算中使用数字、图像、图或其他对象作为输入, 我们需要精确定义如何将这些对象表示为二进制字符串.
一个 表示方案 (representation scheme) 就是将对象 $x$ 映射到一个二进制字符串 $E(x)\in \{0,1{\}}^{\ast }$ 的方法, 例如, 自然数的一个表示方案就是一个函数 $E:\mathbb{N}\to \{0,1{\}}^{\ast }.$
当然, 我们不能把所有的数字都表示成相同的字符串 (比如 “$0011$”), 一个最基本的要求是, 如果两个数 $x$ 和 $x^{\prime }$ 不同, 那么它们必须被表示为不同的字符串, 换句话说, 我们要求编码函数 $E$ 是 一一对应 的 (one-to-one).

2.1.1 表示自然数

现在我们来展示如何将自然数表示为二进制字符串.
多年来, 人们已经尝试了各种方式来表示数字, 包括绳结计数, 雅玛数字, 罗马数字, 我们熟悉的十进制, 以及许多其它方法. 我们当然可以使用其中任意一种将一个数字表示为字符串 (参见 图 2.3), 然而, 出于计算上的方便, 我们采用 二进制基 作为默认的自然数字符串表示法.

例如, 我们将数字 6 表示为字符串 $110,$ 因为 $1\cdot 2^2+1\cdot 2^1+0\cdot 2^0=6.$

类似地, 我们将数字 35 表示为字符串 $y=100011,$ 它满足 ${\sum }_{i=0}^5{y}_i\cdot 2^{|y|-i-1}=35.$

更多示例见下表.

表格: 使用二进制基表示数字. 左列包含自然数在十进制下的表示, 右列包含相同数字在二进制下的表示.

如果 $n$ 是偶数, 那么 $n$ 的二进制表示的最低有效位为 $0;$ 如果 $n$ 是奇数, 那么该位为 $1.$
就像数字 $\lfloor n/10\rfloor$ 对应于“去掉“最低有效的十进制位 (例如, $\lfloor 457/10\rfloor =\lfloor 45.7\rfloor =45),$ 数字 $\lfloor n/2\rfloor$ 对应于“去掉“最低有效的 二进制 位.

因此, 二进制表示可以形式化定义为以下函数 $NtS:\mathbb{N}\to \{0,1{\}}^{\ast }$ ($NtS$ 表示 “natural numbers to strings”):

$$NtS(n)=\{\begin{array}{ll}0& n=0\\ 1& n=1\\ NtS(\lfloor n/2\rfloor )parity(n)& n>1\end{array}\text{\hspace{1em}(2.1)}$$

其中, $parity:\mathbb{N}\to \{0,1\}$ 是函数, 定义为: 如果 $n$ 为偶数, 则 $parity(n)=0;$ 如果 $n$ 为奇数, 则 $parity(n)=1.$
像往常一样, 对于字符串 $x,y\in \{0,1{\}}^{\ast },$ $xy$ 表示字符串 $x$ 与 $y$ 的连接.

函数 $NtS$ 是 递归定义 的: 对于每个 $n>1,$ 我们通过较小的数字 $\lfloor n/2\rfloor$ 的表示来定义 $rep(n).$
同样, 也可以用非递归方式定义 $NtS,$ 参见 习题 2.2.

在本书的大部分内容中, 将数字表示为二进制字符串的具体选择并不重要: 我们只需要知道这样的表示是存在的.
事实上, 对于许多用途, 我们甚至可以使用更简单的表示方法, 将自然数 $n$ 映射为长度为 $n$ 的全零字符串 $0^n.$

def NtS(n):# 自然数(Natural number) to 字符串(String)
    if n > 1:
        return NtS(n // 2) + str(n % 2)
    else:
        return str(n % 2)

print(NtS(236))
# 11101100

print(NtS(19))
# 10011

def StN(x):# 字符串 to 自然数
    k = len(x)-1
    return sum(int(x[i])*(2**(k-i)) for i in range(k+1))

print(StN(NtS(236)))
# 236

2.1.2 表示的意义(讨论)

初学时, 我们自然会认为 $236$ 是“实际“的数字, 而 $11101100$ 只是它的表示.
然而, 对于中世纪的大多数欧洲人来说, CCXXXVI 才是“实际“的数字, 而 $236$(如果他们甚至听说过的话)则是奇怪的印度-阿拉伯位置记数法表示. ¹ 或许未来当我们的 AI 机器人统治者出现时, 它们可能会认为 $11101100$ 才是“实际“的数字, 而 $236$ 只是它们在向人类下达命令时需要使用的表示方法.

那么, 什么才是“实际“的数字呢? 这是数学哲学家们自古以来一直思考的问题.
柏拉图认为, 数学对象存在于某种理想的存在领域中 (在某种程度上比我们通过感官感知的世界更“真实“, 因为后者不过是理想领域的影子).
在柏拉图的视角中, 符号 $236$ 仅仅是某个理想对象的记号, 为了向 已故音乐家 致敬, 我们可以称之为 “通常由 $236$ 表示的数字”.

而奥地利哲学家路德维希·维特根斯坦则认为, 数学对象根本不存在, 唯一存在的只有构成 $236$、$11101100$ 或 CCXXXVI 的实际纸上符号.
在维特根斯坦看来, 数学仅仅是对没有固有意义的符号进行形式操作.
你可以将“实际“的数字理解为(有些递归地)“$236$、$11101100$ 和 CCXXXVI 以及所有旨在表示同一对象的过去和未来的表示方式共同指向的那个东西”.

阅读本书时, 你可以自由选择自己的数学哲学, 只要你能区分数学对象本身与表示它们的各种具体方式, 无论是墨迹斑点、屏幕上的像素、零和一, 还是任何其他形式.

2.2 自然数以外对象的表示

我们已经看到, 自然数可以表示为二进制字符串. 而现在我们将展示, 这对于其他类型的对象也同样适用, 包括(可能为负的)整数、有理数、向量、列表、图以及许多其他对象.

在很多情况下, 为一条数据选择“合适的“字符串表示是非常复杂的任务, 寻找“最佳“表示(例如, 最紧凑, 保真度最高, 最易操作、鲁棒性强(抗干扰能力强), 信息量最大等)一直都是研究的热点.

但目前, 我们先专注于展示一些简单的表示方法, 用于将各种对象作为计算的输入和输出.

2.2.1 表示带有负数的全体整数

既然我们可以将自然数表示为字符串, 我们也可以基于此表示 整数 的全集 (即集合 $\mathbb{Z}=\{\dots ,-3,-2,-1,0,+1,+2,+3,\dots \}$ 的成员), 只需增加一位用于表示符号.

为了表示一个(可能为负的)数字 $m,$ 我们在自然数 $|m|$ 的表示前加上一个比特 $\sigma ,$ 若 $m\ge 0$ 则 $\sigma =0,$ 若 $m<0$ 则 $\sigma =1.$

形式上, 我们将函数 $ZtS:\mathbb{Z}\to \{0,1{\}}^{\ast }$ 定义如下:

$$ZtS(m)=\{\begin{array}{ll}0NtS(m)& m\ge 0\\ 1NtS(-m)& m<0\end{array}$$

其中, $NtS$ 的定义如 (2.1) 所示.

虽然表示的编码函数必须是一一对应的, 但不必是 满射.
例如, 在上述表示法中, 没有任何数字被表示为空字符串, 但这仍然是有效的表示方法, 因为每个整数都能被唯一地表示为某个字符串.

给定一个字符串 $y\in \{0,1{\}}^{\ast },$ 我们如何判断它“应该“表示一个(非负的)自然数还是一个(可能为负的)整数?
更进一步, 即便我们知道 $y$ “应该“是一个整数, 我们又如何知道它使用的是哪种表示方案?
事实上, 除非上下文提供该信息, 否则我们不一定知道. (在编程语言中, 编译器或解释器会根据变量的 类型 决定对应变量的比特序列的表示方法.)

我们可以将同一个字符串 $y$ 视作表示自然数、整数、一段文本、一幅图像, 或者一个绿色的小妖精.
每当我们说类似 “令 $n$ 为字符串 $y$ 表示的数字” 这样的句子时, 我们假设固定某种规范表示方案, 比如上文所示的那些.
具体选择哪种表示方案通常无关紧要, 只需要确保在使用时保持一致即可.

2.2.2 补码表示(选读)

第2.2.1节 中使用特定的“符号位“来表示整数的方法被称为 有符号数表示法 (Signed Magnitude Representation), 曾在一些早期计算机中使用.
然而, 二进制补码表示 在实际中更为常见.

整数 $k$ 在集合 $\{-2^n,-2^n+1,\dots ,2^n-1\}$ 的 二进制补码表示 是长度为 $n+1$ 的字符串 $Zt{S}_n(k),$ 定义如下:

$$Zt{S}_n(k)=\{\begin{array}{ll}Nt{S}_{n+1}(k)& 0\le k\le 2^n-1\\ Nt{S}_{n+1}(2^{n+1}+k)& -2^n\le k\le -1\end{array},$$

其中, $Nt{S}_{\ell }(m)$ 表示数字 $m\in \{0,\dots ,2^{\ell }\}$ 的标准二进制表示, 作为长度为 $\ell$ 的字符串, 并根据需要用前导零填充.
例如, 如果 $n=3,$ 则 $Zt{S}_3(1)=Nt{S}_4(1)=0001,$ $Zt{S}_3(2)=Nt{S}_4(2)=0010,$ $Zt{S}_3(-1)=Nt{S}_4(16-1)=1111,$ 而 $Zt{S}_3(-8)=Nt{S}_4(16-8)=1000.$
如果 $k$ 是大于或等于 $-2^n$ 的负数, 那么 $2^{n+1}+k$ 是一个位于 $2^n$ 和 $2^{n+1}-1$ 之间的数字.
因此, 该数字 $k$ 的二进制补码表示是长度为 $n+1$ 的字符串, 其首位为 $1.$

换句话说, 我们将一个可能为负的数字 $k\in \{-2^n,\dots ,2^n-1\}$ 表示为非负数 $k\mathrm{mod}{2}^{n+1}$ (参见 图 2.4).
这意味着, 如果两个可能为负的数字 $k$ 和 $k^{\prime }$ 不太大 (即 $k+k^{\prime }\in \{-2^n,\dots ,2^n-1\}),$ 那么我们可以通过将 $k$ 和 $k^{\prime }$ 的表示当作非负整数来进行模 $2^{n+1}$ 加法, 从而得到 $k+k^{\prime }$ 的表示.
二进制补码表示的这一特性是其主要优势, 因为根据微处理器的架构, 它们通常可以非常高效地执行模 $2^w$ 的算术运算(对于某些 $w$ 值, 如 32 或 64).

许多系统将检查值是否过大留给程序员, 无论数字大小如何, 系统都会执行这种模运算.
因此, 在某些系统中, 两个大的正数相加可能得到一个 负数 (例如, 将 $2^n-100$ 与 $2^n-200$ 相加可能得到 $-300,$ 因为 $(2^{n+1}-300)\mathrm{mod}{2}^{n+1}=-300,$ 参见 图 2.4).

2.2.3 有理数及字符串表示对

我们可以通过表示两个数字 $a$ 和 $b$ 来表示分数形式的有理数 $a/b.$
然而, 仅仅将 $a$ 和 $b$ 的表示简单连接起来是行不通的.
例如, 数字 $4$ 的二进制表示是 $100,$ 数字 $43$ 的二进制表示是 $101011,$ 但将它们简单连接得到的字符串 $100101011$ 也可以看作是 $18$ 的表示 $10010$ 与 $11$ 的表示 $1011$ 的连接.
因此, 如果使用这种简单连接方式, 我们将无法判断字符串 $100101011$ 是表示 $4/43$ 还是 $18/11.$

我们通过给 字符串对 提供通用表示来解决这个问题.
如果使用纸笔, 我们只需使用一个分隔符号如 $\Vert ,$ 将表示数字 $10$ 和 $110001$ 的一对数字表示为长度为 9 的字符串 “$10\Vert 110001$”.
换句话说, 存在一个一一对应的映射 $F,$ 将 字符串对 $x,y\in \{0,1{\}}^{\ast }$ 映射为一个在字母表 $\Sigma =\{0,1,\Vert \}$ 上的单个字符串 $z$ (即 $z\in {\Sigma }^{\ast }).$
使用分隔符类似于英语中使用空格和标点来分隔单词.
通过增加少量冗余, 我们可以在数字领域实现同样的效果.
我们可以将三元素集合 $\Sigma$ 映射到三元素集合 $\{00,11,01\}\subset \{0,1{\}}^2$ 并保持一一对应, 从而将长度为 $n$ 的字符串 $z\in {\Sigma }^{\ast }$ 编码为长度为 $2n$ 的字符串 $w\in \{0,1{\}}^{\ast }.$

我们对有理数的最终表示通过以下步骤组合得到:

1. 将一个(可能为负的)有理数表示为一对整数 $a,b,$ 使得 $r=a/b.$
2. 将整数表示为二进制字符串.
3. 将步骤 1 和 2 结合, 得到有理数作为字符串对的表示.
4. 将 $\{0,1\}$ 上的字符串对表示为 $\Sigma =\{0,1,\Vert \}$ 上的单个字符串.
5. 将 $\Sigma$ 上的字符串表示为更长的 $\{0,1\}$ 字符串.

同样的思想可以用来表示字符串三元组、四元组, 甚至更多, 作为单个字符串.
实际上, 这是一个非常通用的原则的实例, 我们会在计算机科学的理论与实践中反复使用它(例如, 在面向对象编程中):

重复同样的思想, 一旦我们可以表示类型为 $T$ 的对象, 我们也可以表示这些对象的 列表的列表, 甚至是列表的列表的列表, 如此类推.
当我们讨论 第2.5.2节 中的 前缀无关编码 (prefix free encoding) 时, 我们会再次回到这一点.

2.3 实数的表示

实数集 $\mathbb{R}$ 包含所有正数、负数、分数, 以及像 $\pi$ 或 $e$ 这样的 无理数.
每个实数都可以用有理数近似, 因此我们可以用一个接近 $x$ 的有理数 $a/b$ 来表示实数 $x.$
例如, 我们可以用 $22/7$ 来表示 $\pi ,$ 误差约为 $10^{-3}.$ 若希望误差更小(例如约 $10^{-4}),$ 可以使用 $311/99,$ 以此类推.

实数通过近似有理数来表示是一个可行的表示方案.

然而, 在计算机应用中, 通常更常用 浮点表示法 (参见 图 2.5) 来表示实数.
在浮点表示法中, 我们用一对 $(b,e)$ 表示 $x\in \mathbb{R},$ 其中 $b$ 和 $e$ 是某些规定长度的(可能为正或负的)整数, 并且 $b\times 2^e$ 最接近 $x.$
浮点表示是 科学计数法 的二进制版本, 即将一个数字 $y\in \mathbb{R}$ 表示为 $b\times 10^e$ 的近似.
称之为“浮点“是因为可以将 $b$ 看作指定一串二进制数字, $e$ 描述这串数字中“二进制小数点“的位置.

正是浮点表示的使用, 导致许多编程系统中, 表达式 0.1+0.2 的输出为 0.30000000000000004 而不是 0.3.
更多信息可见: 这里, 这里, 这里.

读者可能会(合理地)担心, 浮点表示法(或有理数表示法)只能 近似 表示实数.
在许多(但不是全部)计算应用中, 可以将精度调得足够高, 以至于不会影响最终结果.

但有时我们仍需要谨慎. 事实上, 浮点数错误有时可能造成严重后果.
例如, 浮点舍入误差曾导致美国爱国者导弹未能拦截伊拉克飞毛腿导弹, 造成 28 人死亡 (详细报道), 以及在计算 英国养老金发放金额 时出现过的 1 亿英镑的错误.

2.4 Cantor定理, 可数集, 以及实数的字符串表示

鉴于浮点数对实数的近似问题, 一个自然的问题是: 是否可以将实数 精确地 表示为字符串.
不幸的是, 下述定理表明这是不可能的:

可数集. 我们说一个集合 $S$ 是 可数的, 如果存在一个满射 $C:\mathbb{N}\to S,$ 或者换句话说, 我们可以将 $S$ 写成序列
$C(0),C(1),C(2),\dots .$
由于二进制表示给出了从 $\{0,1{\}}^{\ast }$ 到 $\mathbb{N}$ 的满射, 并且两个满射的复合仍然是满射, 集合 $S$ 是可数的当且仅当存在从 $\{0,1{\}}^{\ast }$ 到 $S$ 的满射. 利用函数的基本性质(见 第1.4.3节), 一个集合可数当且仅当存在从 $S$ 到 $\{0,1{\}}^{\ast }$ 的一一函数.

因此, 我们可以将 定理 2.1 重述如下:

定理 2.2 由 Georg Cantor 于 1874 年证明.
这一结果(以及相关结论)震惊了当时的数学家. 通过证明不存在从 $\mathbb{R}$ 到 $\{0,1{\}}^{\ast }$(或 $\mathbb{N})$的一一映射, Cantor 展示了这两个无限集合有“不同的无限形式“, 并且实数集 $\mathbb{R}$ 在某种意义上比无限集合 $\{0,1{\}}^{\ast }$ “更大”.
“无限的层次“这一概念当时让数学家和哲学家深感困惑. 哲学家 Ludwig Wittgenstein(前面提到过)称 Cantor 的结果为“完全的胡扯“且“可笑”, 其他人甚至认为更糟: Leopold Kronecker 称 Cantor 是“腐蚀青年的人“, 而 Henri Poincaré 说 Cantor 的思想“应从数学中彻底剔除“. 不过事实证明 Cantor 看得更远. 如今 Cantor 的工作已被普遍接受为集合论和数学基础的基石.
正如 David Hilbert 在 1925 年所说, “无人能将我们从 Cantor 为我们创造的天堂中驱逐出去”.
也正如我们稍后将在本书中看到的, Cantor 的思想在计算理论中也起着重要作用.

我们已经讨论了 定理 2.1 的重要性, 让我们来看看它的证明. 这将分两步进行:

1. 定义一个无限集合 $\mathcal{X},$ 对于它证明不可数更加容易(即证明不存在从 $\mathcal{X}$ 到 $\{0,1{\}}^{\ast }$ 的一一函数更容易).
2. 证明存在一个一一函数 $G$ 将 $\mathcal{X}$ 映射到 $\mathbb{R}.$

利用反证法, 这两条事实结合起来可以推出 定理 2.1.
具体来说, 如果假设(为了反证)存在某个一一函数 $F$ 将 $\mathbb{R}$ 映射到 $\{0,1{\}}^{\ast },$
那么通过将 $F$ 与步骤 2 中的函数 $G$ 复合得到的函数 $x\mapsto F(G(x))$ 就是从 $\mathcal{X}$ 到 $\{0,1{\}}^{\ast }$ 的一一函数,
这与步骤 1 中的结论矛盾!

为了将这个想法完整地转化为 定理 2.1 的证明, 我们需要:

• 定义集合 $\mathcal{X}.$
• 证明不存在从 $\mathcal{X}$ 到 $\{0,1{\}}^{\ast }$ 的一一函数.
• 证明存在从 $\mathcal{X}$ 到 $\mathbb{R}$ 的一一函数.

接下来我们将精确地做到这些:
我们将定义集合 $\{0,1{\}}^{\infty },$ 它将扮演 $\mathcal{X}$ 的角色,
然后陈述并证明两个引理, 说明该集合满足我们所需的两个性质.

简单来说, $\{0,1{\}}^{\infty }$ 是一个 函数的集合, 并且一个函数 $f$ 属于 $\{0,1{\}}^{\infty }$ 当且仅当它的定义域是 $\mathbb{N}$ 而值域是 $\{0,1\}.$
我们可以将 $\{0,1{\}}^{\infty }$ 理解为所有无限长 比特序列 的集合, 因为函数 $f:\mathbb{N}\to \{0,1\}$ 正好一一对应于无限序列 $(f(0),f(1),f(2),\dots ).$

下面两个引理说明, $\{0,1{\}}^{\infty }$ 可以作为 $\mathcal{X}$ 来证明 定理 2.1:

如上所示, 引理 2.1 和 引理 2.2 结合起来即可推出 定理 2.1.
为了更正式地重复这一论证, 为了反证, 假设存在一一函数 $RtS:\mathbb{R}\to \{0,1{\}}^{\ast }.$
由 引理 2.2, 存在一一函数 $FtR:\{0,1{\}}^{\infty }\to \mathbb{R}.$
因此, 根据假设, 由于两个一一函数的复合仍是一一函数(见 习题 2.12),
函数 $FtS:\{0,1{\}}^{\infty }\to \{0,1{\}}^{\ast }$ 定义为 $FtS(f)=RtS(FtR(f))$ 将是一一函数,
这与 引理 2.1 矛盾.
参见 图 2.7 获取该论证的图示说明.

现在只剩下证明这两个引理. 我们先从证明 引理 2.1 开始, 这实际上是 定理 2.1 的核心部分.

热身运动: “Cantor定理青春版”. 引理 2.1 的证明相当微妙. 一种获得对该证明的直觉的方法是考虑以下有限版本的陈述: “不存在一个满射函数 $f:\{0,\dots ,99\}\to \{0,1{\}}^{100}$”. 当然我们知道这是正确的, 因为集合 $\{0,1{\}}^{100}$ 比集合 $[100]$ 更大, 但让我们来看一个不太直接的证明: 对于任意 $f:\{0,\dots ,99\}\to \{0,1{\}}^{100},$ 我们可以定义字符串 $\overline{d}\in \{0,1{\}}^{100}$ 如下: $\overline{d}=(1-f(0{)}_0,1-f(1{)}_1,\dots ,1-f(99{)}_{99}).$ 如果 $f$ 是满射, 那么必然存在某个 $n\in [100]$ 使得 $f(n)=\overline{d},$ 但我们声称不存在这样的 $n.$ 实际上, 如果存在这样的 $n,$ 那么 $\overline{d}$ 的第 $n$ 个分量应当等于 $f(n{)}_n,$ 但根据定义这个分量等于 $1-f(n{)}_n.$ 另见此陈述的 “proof by code”.

为了完成 定理 2.1 的证明, 我们需要证明 引理 2.2.
这个证明虽然需要一些微积分基础, 但使用了的地方都比较直接易懂.
不过如果你之前处理实数列极限的经验不多, 那么下面的证明还是可能会有些难以理解.
当然, 这部分并非 Cantor 论证的核心, 此类极限对于本书后续内容也不重要, 因此你完全可以选择相信 引理 2.2 并跳过这些繁琐的证明.

2.4.1 推论: 布尔函数全体不可数.

Cantor 定理得出如下推论, 我们将在本书中多次使用: 所有 布尔函数(将 $\{0,1{\}}^{\ast }$ 映射到 $\{0,1\}$ 的函数)构成的集合是不可数的.

这是 引理 2.1 的直接推论, 因为我们可以用二进制表示构造一个从 $\{0,1{\}}^{\infty }$ 到 $ALL$ 的一一映射. 因此, $\{0,1{\}}^{\infty }$ 的不可数性意味着 $ALL$ 的不可数性.

2.4.2 可数性的等价条件

上述结果建立了多种等价的方式来表述集合可数的事实.
具体来说, 以下陈述都是等价的:

1. 集合 $S$ 是可数的
2. 存在一个从 $\mathbb{N}$ 到 $S$ 的满射
3. 存在一个从 $\{0,1{\}}^{\ast }$ 到 $S$ 的满射
4. 存在一个从 $S$ 到 $\mathbb{N}$ 的一一映射
5. 存在一个从 $S$ 到 $\{0,1{\}}^{\ast }$ 的一一映射
6. 存在一个从某个可数集合 $T$ 到 $S$ 的满射
7. 存在一个从 $S$ 到某个可数集合 $T$ 的一一映射

2.5 数字以外元素的表示

当然, 数字并不是我们唯一可以表示为二进制字符串的对象.
用于表示某个集合 $\mathcal{O}$ 中对象的 表示方案 由一个将 $\mathcal{O}$ 中对象映射为字符串的 编码 函数和一个将字符串解码回 $\mathcal{O}$ 中对象的 解码 函数组成.
形式化地, 我们作如下定义:

注意, 对每个 $o\in \mathcal{O}$ 都有 $D(E(o))=o$ 的条件意味着 $D$ 是 满射(你能看出为什么吗? ).
事实上, 构造一个表示方案时, 我们只需要找到一个 编码 函数.
也就是说, 每个一一的编码函数都有对应的解码函数, 如下引理所示:

2.5.1 有限表示

如果 $\mathcal{O}$ 是 有限 的, 那么我们可以将 $\mathcal{O}$ 中的每个对象表示为长度至多为某个数 $n$ 的字符串.
那么 $n$ 的取值是多少呢?
我们记 $\{0,1{\}}^{\le n}$ 为长度至多为 $n$ 的字符串集合 $\{x\in \{0,1{\}}^{\ast }:|x|\le n\}.$
集合 $\{0,1{\}}^{\le n}$ 的大小等于

$$|\{0,1{\}}^0|+|\{0,1{\}}^1|+|\{0,1{\}}^2|+\cdots +|\{0,1{\}}^n|=\sum _{i=0}^n{2}^i=2^{n+1}-1.$$

这使用 等比数列 的标准求和公式即可得到.

为了将 $\mathcal{O}$ 中的对象表示为长度至多为 $n$ 的字符串, 我们需要构造一个从 $\mathcal{O}$ 到 $\{0,1{\}}^{\le n}$ 的一一映射. 而当且仅当 $|\mathcal{O}|\le 2^{n+1}-1,$ 我们才能做到这一点, 如以下引理所示:

对于任意两个非空有限集合 $S,T,$ 当且仅当 $|S|\le |T|$ 时, 存在一个一一映射 $E:S\to T.$

设 $k=|S|$ 且 $m=|T|,$ 并将 $S$ 和 $T$ 的元素分别写为 $S=\{s_0,s_1,\dots ,s_{k-1}\}$ 和 $T=\{t_0,t_1,\dots ,t_{m-1}\}.$
我们需要证明, 存在一个一一映射 $E:S\to T$ 当且仅当 $k\le m.$

对“当“方向, 如果 $k\le m,$ 我们可以简单地定义 $E(s_i)=t_i$ 对每个 $i\in [k].$
显然, 对于 $i\ne j,$ 有 $t_i=E(s_i)\ne E(s_j)=t_j,$ 因此该函数是一一映射.

对“仅当“方向, 假设 $k>m$ 且 $E:S\to T$ 是某个函数. 那么 $E$ 不可能是一一映射.
事实上, 对 $i=0,1,\dots ,m-1,$ 我们“标记“ $T$ 中的元素 $t_j=E(s_i).$
如果 $t_j$ 已经被标记过, 那么我们就找到了两个映射到同一元素 $t_j$ 的 $S$ 中的对象.
否则, 由于 $T$ 有 $m$ 个元素, 当我们标记到 $i=m-1$ 时, $T$ 中的所有对象都已被标记.
因此, 在这种情况下, $E(s_m)$ 必须映射到一个已经被标记过的元素.
(这一观察有时被称为“鸽巢原理“: 假设有 $m$ 个巢和 $k>m$ 只鸽子, 则必有两只鸽子在同一个巢中.)

2.5.2 前缀无关编码

在展示有理数的表示方案时, 我们使用了一个“技巧“: 将字母表 $\{0,1,\Vert \}$ 编码, 以便将字符串元组表示为单个字符串.
这是 前缀无关编码 的一个特例.

前缀无关编码的思想如下, 如果我们的表示具有如下性质: 表示对象 $o$ 的字符串 $x$ 不是表示不同对象 $o^{\prime }$ 的字符串 $y$ 的 前缀 (即初始子串), 那么我们可以仅通过将列表中所有成员的表示串联起来, 来表示一个对象列表.
例如, 因为在英文中每个句子都以标点符号结束, 如句号, 感叹号或问号, 没有句子可以成为另一个句子的前缀, 因此我们可以仅通过将句子一个接一个地串联来表示一个句子列表. (英文中存在一些复杂情况, 例如缩写中的句点 (如 “e.g.”)或句子引号包含标点, 但高层次上前缀自由表示句子的原理仍然成立.)

事实上, 我们可以将 每一个 表示转换为前缀无关形式.
这为 重要提示 2.1 提供了依据, 并允许我们将类型 $T$ 对象的表示方案转换为类型 $T$ 对象 列表 的表示方案.
通过重复同样的技术, 我们还可以表示类型 $T$ 对象的列表的列表, 以此类推.

但首先, 让我们正式定义前缀无关性:

回忆一下, 对于每个集合 $\mathcal{O},$ 集合 ${\mathcal{O}}^{\ast }$ 包含所有有限长度的元组(即 列表)的 $\mathcal{O}$ 中元素.
下述定理表明, 如果 $E$ 是 $\mathcal{O}$ 的前缀自由编码, 则通过串联编码, 我们可以得到 ${\mathcal{O}}^{\ast }$ 的一个有效的(一一)表示:

定理 2.4 可能有点难以理解, 但一旦你理解了它的含义, 实际上证明起来相当直接.
因此, 我强烈建议你在此处停下来, 确保你理解了该定理的陈述. 你也应该尝试自己证明它, 然后再继续阅读.

证明的思路很简单.
例如, 假设我们想从表示 $x=\overline{E}(o_0,o_1,o_2)=E(o_0)E(o_1)E(o_2)$ 中解码三元组 $(o_0,o_1,o_2).$
我们首先找到 $x$ 的第一个前缀 $x_0,$ 它是某个对象的表示.
然后解码该对象, 从 $x$ 中去掉 $x_0$ 得到新的字符串 $x^{\prime },$ 再继续找到 $x^{\prime }$ 的第一个前缀 $x_1,$ 以此类推(参见 习题 2.9).
$E$ 的前缀自由性质保证了 $x_0$ 实际上就是 $E(o_0),$ $x_1$ 是 $E(o_1),$ 依此类推.

2.5.3 构造前缀无关表示

有一些自然的表示是前缀无关的.
例如, 每个 固定输出长度 的表示(即一一函数 $E:\mathcal{O}\to \{0,1{\}}^n)$自动是前缀无关的, 因为只有当 $x$ 和 $x^{\prime }$ 相等时, 长度相同的 $x^{\prime }$ 才可能有 $x$ 作为前缀.

此外, 我们用来表示有理数的方法也可以用来证明如下结论:

为了完整起见, 我们将在下方给出证明. 不过你可以在这里停下来, 尝试用我们表示有理数时使用的相同技巧自己证明它.

引理 2.4 的证明并不是将任意表示转换为前缀无关形式的唯一方法, 也不一定是最优方法.
习题 2.10 就要求你构造一个更高效的前缀无关转换, 满足 $|\overline{E}(o)|\le |E(o)|+O(\log |E(o)|).$

2.5.4 “基于Python的证明” (选读)

定理 2.4 和 引理 2.4 的证明是 构造性的, 意味着它们给出了:

• 将任意对象 $O$ 的表示的编码和解码函数转换为前缀无关的编码和解码函数的方法, 以及
• 将单个对象的前缀无关编码和解码扩展到 对象列表 的编码和解码的方法(通过串联实现).

具体来说, 我们可以将任意一对 Python 函数 encode 和 decode 转换为函数 pfencode 和 pfdecode, 对应于前缀无关的编码和解码. 同样, 给定单个对象的 pfencode 和 pfdecode, 我们可以将它们扩展到列表的编码. 下面展示了如何对上文定义的 NtS 和 StN 函数进行这种处理.

我们从 引理 2.4 的“Python 证明“开始: 一种将任意表示转换为 前缀无关 表示的方法. 下面的函数 prefixfree 接受一对编码和解码函数作为输入, 并返回一个三元组函数, 其中包含 前缀无关 的编码和解码函数, 以及一个检查字符串是否为对象有效编码的函数.

# 接受 encode 和 decode 函数, 分别将对象映射为比特列表以及反向映射, 
# 并返回 pfencode 和 pfdecode 函数, 
# 以前缀无关的方式将对象映射为比特列表以及反向映射. 
# 同时返回一个 pfvalid 函数, 用于判断一个比特列表是否为有效编码

def prefixfree(encode, decode):
    def pfencode(o):
        L = encode(o)
        return [L[i//2] for i in range(2*len(L))]+[0,1]
    def pfdecode(L):
        return decode([L[j] for j in range(0,len(L)-2,2)])
    def pfvalid(L):
        return (len(L) % 2 == 0 ) and all(L[2*i]==L[2*i+1] for i in range((len(L)-2)//2)) and L[-2:]==[0,1]

    return pfencode, pfdecode, pfvalid

pfNtS, pfStN , pfvalidN = prefixfree(NtS,StN)

NtS(234)
# 11101010
pfNtS(234)
# 111111001100110001
pfStN(pfNtS(234))
# 234
pfvalidM(pfNtS(234))
# true

注意, 上述 Python 函数 prefixfree 接受两个 Python 函数 作为输入, 并输出三个 Python 函数作为结果. (无歧义的情况下, 我们会使用 “Python 函数” 或 “子程序” 这个术语来区分 Python 程序片段和数学意义上的函数.)
在本书中, 你不需要掌握 Python, 但你需要熟悉函数作为独立的数学对象的概念, 可以被用作其他函数的输入或输出.

下面我们给出 定理 2.4 的 “Python 证明”. 具体来说, 我们展示一个函数 represlists, 它接受一个前缀无关表示方案作为输入 (通过编码、解码和有效性检测函数实现), 并输出一个用于表示该类对象 列表 的表示方案. 如果我们希望使这个表示也是前缀无关的, 那么可以再将其放入上面的 prefixfree 函数中.

def represlists(pfencode,pfdecode,pfvalid):
    """
    接受函数 pfencode, pfdecode 和 pfvalid,  
    并返回函数 encodelists, decodelists,  
    它们可以分别对该类对象的 **列表** 进行编码和解码.   
    """

    def encodelist(L):
        """Gets list of objects, encodes it as list of bits"""
        return "".join([pfencode(obj) for obj in L])

    def decodelist(S):
        """Gets lists of bits, returns lists of objects"""
        i=0; j=1 ; res = []
        while j<=len(S):
            if pfvalid(S[i:j]):
                res += [pfdecode(S[i:j])]
                i=j
            j+= 1
        return res

    return encodelist,decodelist


LtS , StL = represlists(pfNtS,pfStN,pfvalidN)

LtS([234,12,5])
# 111111001100110001111100000111001101
StL(LtS([234,12,5]))
# [234, 12, 5]

2.5.5 字母和文本的表示

我们可以用一个字符串来表示一个字母或符号, 然后如果这种表示是前缀无关的, 我们就可以通过简单地连接每个符号的表示来表示一个符号序列.
其中一种表示是 ASCII, 它用 7 位的字符串表示 128 个字母和符号.
由于 ASCII 表示是固定长度的, 它自动是前缀无关的 (你能看出原因吗?).
Unicode 是一种将 (在撰写本文时) 约 128,000 个符号表示为介于 0 和 1,114,111 之间的数字的表示方法 (称为 code points).
对于这些 code points 有几种前缀无关的表示方法, 一种流行的方法是 UTF-8, 它将每个 code point 编码为长度在 8 到 32 之间的字符串.

int      2    : 00000010 00000000 00000000 00000000
int      4    : 00000100 00000000 00000000 00000000
int      513  : 00000001 00000010 00000000 00000000
long     513  : 00000001 00000010 00000000 00000000 00000000 00000000 00000000 00000000
int      -1   : 11111111 11111111 11111111 11111111
int      -2   : 11111110 11111111 11111111 11111111
string   Hello: 01001000 01100101 01101100 01101100 01101111 00000000
string   abcd : 01100001 01100010 01100011 01100100 00000000
float    33.0 : 00000000 00000000 00000100 01000010
float    66.0 : 00000000 00000000 10000100 01000010
float    132.0: 00000000 00000000 00000100 01000011
double   132.0: 00000000 00000000 00000000 00000000 00000000 10000000 01100000 01000000

2.5.6 向量, 矩阵及图片的表示

一旦我们可以表示数字和数字列表, 我们就可以表示 向量(本质上就是数字的列表).
同样, 我们可以表示列表的列表, 因此特别地, 可以表示 矩阵.
为了表示一张图像, 我们可以通过一个长度为3的数字列表表示每个像素的颜色, 分别对应红色、绿色和蓝色的强度.
(我们可以只使用三种原色, 因为 大多数 人类视网膜中只有三种类型的视锥细胞; 而如果要表示 螳螂虾 可见的颜色, 我们需要 16 种原色.)
因此, 一张包含 $n$ 个像素的图像可以表示为一个包含 $n$ 个长度为三的列表的列表.
视频可以表示为图像的列表.
当然, 这些表示方法相当浪费, 对于图像和视频通常使用 更 紧凑 的表示方法, 虽然本书不会涉及这些内容.

2.5.7 图的表示

一个 图 在 $n$ 个顶点上可以表示为一个 $n\times n$ 的 邻接矩阵, 其第 $(i,j)$ 个元素为 1 当且仅当边 $(i,j)$ 存在, 否则为 0.
也就是说, 我们可以将一个 $n$ 顶点的有向图 $G=(V,E)$ 表示为一个字符串 $A\in \{0,1{\}}^{n^2},$ 使得 $A_{i,j}=1$ 当且仅当边 $\overrightarrow{ij}\in E.$
我们可以通过将每条无向边 $\{i,j\}$ 替换为两条有向边 $\overrightarrow{ij}$ 和 $\overleftarrow{ij}$ 来将无向图转换为有向图.

另一种图的表示方法是 邻接表 表示. 也就是说, 我们将图的顶点集合 $V$ 与集合 $[n]$ 对应, 其中 $n=|V|,$ 并将图 $G=(V,E)$ 表示为 $n$ 个列表组成的列表, 其中第 $i$ 个列表包含顶点 $i$ 的出邻居.
对于某些应用, 这些表示方法之间的差异可能很大, 虽然对于我们而言通常无关紧要.

2.5.8 列表和嵌套列表的表示

如果我们有一种方法将集合 $\mathcal{O}$ 中的对象表示为二进制字符串, 那么我们可以通过应用前缀无关变换来表示这些对象的列表.
此外, 我们可以使用类似上述的技巧来处理 嵌套 列表.
其思想是, 如果我们有某种表示 $E:\mathcal{O}\to \{0,1{\}}^{\ast },$ 那么我们可以使用五元素字母表 $\Sigma =\{$ 0,1,[ , ] , , $\}$ 上的字符串来表示来自 $\mathcal{O}$ 的嵌套列表.

例如, 如果 $o_1$ 表示为 0011, $o_2$ 表示为 10011, $o_3$ 表示为 00111, 那么我们可以将嵌套列表 $(o_1,(o_2,o_3))$ 表示为字母表 $\Sigma$ 上的字符串 "[0011,[10011,00111]]".

通过将 $\Sigma$ 的每个元素本身编码为三位二进制字符串,
我们可以将任意对象集合 $\mathcal{O}$ 的表示转换为一种表示, 使得可以表示这些对象的(潜在嵌套)列表.

2.5.9 一些注释

我们通常会将一个对象与其字符串表示等同起来.
例如, 如果 $F:\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$ 是某个将字符串映射到字符串的函数, 且 $n$ 是一个整数, 我们可能会说 “$F(n)+1$ 是质数”, 这意味着如果我们将 $n$ 表示为字符串 $x,$ 那么由字符串 $F(x)$ 表示的整数 $m$ 满足 $m+1$ 是质数.
(你可以看到, 这种将对象与其表示等同的约定可以为我们节省大量繁琐的形式化表达.)

同样地, 如果 $x,y$ 是某些对象, 且 $F$ 是一个以字符串为输入的函数, 那么 $F(x,y)$ 表示将 $F$ 应用于有序对 $(x,y)$ 的表示的结果.
我们对任意 $k$ 元组对象使用相同的符号表示函数的调用.

这种将对象与其字符串表示等同的约定, 是我们人类一直在使用的.
例如, 当人们说 “$17$ 是质数” 时, 他们真正的意思是, 十进制表示为字符串 “17” 的整数是质数.

2.6 将计算任务定义为数学函数

抽象地讲, 计算过程 是一种将输入(二进制字符串)转换为输出(二进制字符串)的过程.
这种从输入到输出的变换可以通过现代计算机、遵循指令的人、某些自然系统的演化或其他任何手段完成.

在后续章节中, 我们将转向对计算过程的数学定义, 但正如上文所讨论的, 目前我们关注 计算任务. 也就是说, 我们关注的是 规范 而非 实现.
同样地, 在抽象层面上, 一个计算任务可以指定输出需要满足的任意输入输出关系.
然而, 在本书的大部分内容中, 我们将专注于最简单、最常见的任务: 计算函数.

下面是一些例子:

• 给定两个整数 $x,y$ 的表示, 计算它们的乘积 $x\times y.$ 使用上面的表示方法, 这对应于从 $\{0,1{\}}^{\ast }$ 到 $\{0,1{\}}^{\ast }$ 的函数计算. 我们已经看到, 解决这个计算任务的方法不止一种, 事实上, 我们仍然不知道该问题的最优算法.
• 给定一个整数 $z>1$ 的表示, 计算其 因式分解; 即, 找出质数列表 $p_1\le \cdots \le p_k$ 使得 $z=p_1\cdots p_k.$ 这同样对应于从 $\{0,1{\}}^{\ast }$ 到 $\{0,1{\}}^{\ast }$ 的函数计算. 对于该问题的复杂性, 我们的认知差距甚至更大.
• 给定图 $G$ 的表示和两个顶点 $s$ 与 $t,$ 计算 $G$ 中从 $s$ 到 $t$ 的最短路径长度, 或者计算从 $s$ 到 $t$ 的 最长路径(不重复顶点)的长度. 这两个任务都对应于从 $\{0,1{\}}^{\ast }$ 到 $\{0,1{\}}^{\ast }$ 的函数计算, 但它们的计算难度却差别极大.
• 给定一个 Python 程序的代码, 判断是否存在输入会使程序进入无限循环. 该任务对应于从 $\{0,1{\}}^{\ast }$ 到 $\{0,1\}$ 的 部分函数 计算, 因为并非每个字符串都对应语法有效的 Python 程序. 我们会看到, 我们 确实 理解该问题的计算状态(见下文的状态机), 但答案相当令人惊讶.
• 给定图像 $I$ 的表示, 判断 $I$ 是猫的照片还是狗的照片. 这对应于从 $\{0,1{\}}^{\ast }$ 到 $\{0,1\}$ 的某个(部分)函数的计算.

计算任务的一个重要特例是计算 布尔函数, 其输出为单比特 $\{0,1\}.$
计算这类函数对应于回答 是/否 问题, 因此该任务也被称为 判定问题.
给定任意函数 $F:\{0,1{\}}^{\ast }\to \{0,1\}$ 和 $x\in \{0,1{\}}^{\ast },$ 计算 $F(x)$ 的任务对应于判定 $x$ 是否属于集合 $L,$ 其中 $L=\{x:F(x)=1\}$ 被称为与函数 $F$ 对应的 语言.(语言这个术语源于计算理论与诺姆·乔姆斯基发展的形式语言学之间的历史联系.)
因此, 许多文献将这类计算任务称为 判定一个语言.