从卡农到递归可枚举

基本上每天不停花了差不多两个月的时间，大致看了两遍终于可以认为基本吸收了 GEB 大部分的观点。刚看的时候写了第一篇关于同构的博文，结果还是 too young too simple。「同构」的确是 GEB 的元主题，它连接了数学、音乐、艺术和文学¹等。但其实这本书还存在所谓的「元元主题」，因为作者想通过「同构」之间的「同构」，即这些同构的共同点，引出他所谓的「怪圈」概念，用来解释意识的产生。

今天暂时不来讲这个元元主题，而只讲一个元主题：一个在音乐、绘画和数学之间的同构。具体来说，我们来谈谈「对偶」这个概念：

• 音乐里面可以说是主旋律和伴奏之间的关系；
• 绘画里面就是图形和衬底之间的关系；
• 数学里面可以有一个集合及其补集之间的关系。

所谓同构，就是说这三种关系存在一种共同点。

卡农

这本书真可怕。由于有主题、元主题和元元主题间的交织，你能获得不同层次上的知识和见解。为了理解同构，你必须首先对其连结的主题有充分的了解，比如说卡农。尽管小时候还学过大提琴，也有一些喜欢的曲子，却一直没有从「学科」的角度去「轻研究」过音乐：各种类型、风格、作曲、旋律分析等等。借助这本书的机会，终于可以说至少知道「卡农」和「赋格」到底是个什么东西。

「卡农」这个词到不是第一次见到，不过以前见到的时候通常指的是下面这首曲子：D 大调卡农与吉格 (Pachelbel’s Canon)。下面你可以尝试听听 Jeffrey C. Hall 在 Wikimedia Commons 上通过 CC BY-SA 3.0 协议共享的电子合成版本。

这本书真可怕。通过卡农和巴赫的主题，又把我岔到了最喜爱的动画作品：新世纪福音战士。EVA 里面也有很多古典音乐，特别就是巴赫的作品。上面的卡农也可以在新世纪福音战士 97 年 Tokyo 现场交响音乐会 54:30 秒处听到。无论是书籍还是影视音频，有些作品可能是可以陪伴一生的。

对于我这种耳朵不太敏感（或者没有训练过敏感度）的人来说，只有看乐谱才能一窥上面这首曲子——或者一般的「卡农」——的精彩之处。当然如果看了上面给出的 EVA 的交响乐视频就更直观了。这首曲子有 4 个声部（视频里面有 5 个，算是一个对原版的小改动）：3 台小提琴对应前 3 个声部，1 台大提琴定一个基础的周期短的循环旋律。这算是一个典型的复调音乐：存在多个重要性相当的声部。有些曲子可能就一个对应主旋律的声部，其他声部就只是伴奏。但这首曲子的 3 个小提琴声部轮流充当了旋律与和声的作用。事实上更特别的是：

这 3 个声部分别间隔八拍先后演奏几乎同一条旋律！

这个就是「卡农」——作为一种音乐曲式——最重要的特点。在有歌词的情况下卡农就变成了轮唱，多个声部先后唱出同一首旋律，小时候班级合唱的时候就经历过。有意思的是中文版里面为了介绍卡农和轮唱举到了保卫黄河的例子，而英文原版则提到 Frère Jacques，其实就是两只老虎的法语原版……

如果定义 \(f_1(t)\) 为第 1 把小提琴所演奏的旋律、\(T\) 代表八拍对应的时间，那么第 2 和第 3 声部就是

\[f_2(t)=f_1(t-T)\,,\qquad f_3(t)=f_2(t-T)=f_1(t-2T)\]

即它们仅仅是时间上的一个平移。这就构成了一个很简单的同构，这三条声部事实上传递的是同样的信息。但令人称奇是它们所产生的和声又是那么的优美。很明显借助 GEB 的另一个同构，这首音乐需要「整体论」（即作为整体）和「简化论」（即从整体所构成的各个部分的角度）同时分析。在这里例子中，主旋律和伴奏之间就存在一种和谐的平衡。

Escher

从这本书知道了荷兰画家 Escher 的一些很有意思的作品。他擅长设计出一些「悖论」的情景，构造了作者所提到的绘图中的「怪圈」。不过正如一开始提到的，这里想介绍他一些体现图形和衬底之间的关系的作品。由于版权问题，这里不能之间放出我想给出的图片，不过可以去下面它的官方网站查看：

• 平面填充 Plane Filling II, 1957；
• 天鹅 Swan (No. 96), 1955 和 鱼 Fish (No. 107), 1960。

一般来说，当你作画时，很自然地把绘图整体分成了两部分：

1. 用画笔画到的地方作为图形；
2. 没有被画到的部分作为衬底。

很简单的例子，下面是我博士论文中一副示意图。如果把黑框里面的所有部分看作是绘图的话，那么所有非白色的部分就是我「主动」所画的图形，而留白的部分就是「被动」所产生的衬底。

一般来说，在一副绘图作品中，是你「主动」所形成的图形传递了你想传递的信息，而「衬底」一般甚至不传递信息（比如上面这幅图）。不过在看了 Escher 的平面填充 Plane Filling II, 1957 之后，就会发现他的这幅画中的图形（黑色部分）和衬底（留「白」部分）都是「主体」，都传递了彼此相当的信息。留白的部分不再是被动产生的，而是一开始绘画时就构思好的，这就之前的音乐产生了同构：在一般音乐里面，伴奏也是「被动」的，因为一般先「主动」创造主旋律，再去添加次要的伴奏。而之前卡农的例子中主旋律和伴奏都是在当初创作的主体，已经没有「主要」和「次要」之分，各个声部（不管是图形或是衬底）都发挥了同等的作用。

在卡农的例子中，各个部分之间事实上彼此产生了内同构：旋律没有变化，只是时间上进行了平移。这一点同样可以在 Escher 的天鹅 Swan (No. 96), 1955 和鱼 Fish (No. 107), 1960 中见到：图形和衬底都传递了相同的信息，只是有一个空间上的平移、旋转。

递归可枚举

在看到了音乐和绘画之间的同构之后，再来看看一个数学中类似的概念。尽管一直对计算机感兴趣，工作大部分时间也都是在编程，但毕竟学术专业不是研究计算理论，所以可能下面的介绍没有带着很透彻的理解。

这里要提到的就是数学中集合及其补集的对偶关系。建立在 ZFC 公理体系上的数学²中只存在一种东西：集合。数字 1 是集合，自然数整体是集合，函数也是集合。由于这里不涉及集合的严密定义，所以把「集合」理解成一般你所理解集合的意思就好：一群东西所组成的整体。我们这里主要考虑在自然数整体所构成的集合 \(\mathbb{N}\) 中所发生的事情，于是就可以引入「补集」的概念。假设 \(S\subset\mathbb{N}\) 是一个由一些自然数构成的集合（所以它是 \(\mathbb{N}\) 中的子集，写作 \(S\subset\mathbb{N}\)），那么它的补集就是

\[\overline{S}=\{\,x\in\mathbb{N}\,|\,x\notin S\,\}\]

换句话说，就是那些不属于 \(S\) 的自然数所组成的集合。如果 \(S\) 是奇数集合 \(\{\,1, 3, 5, \ldots\,\}\) ，那么其补集 \(\overline{S}=\{\,0, 2, 4, \ldots\,\}\) 就是所有偶数所组成的集合（加上个零）。如果 \(S\) 是素数（在大于 1 的自然数中，除了1和该数自身外，无法被其他自然数整除的数）集合，那么其补集就是所有合数组成的集合，即合数可以由两个比它小的自然数的乘积所获得。

为了解决一些实际问题，我们有时候需要计算出一个集合（比如找到符合某个条件的自然数）。这里的计算应该理解成通过一系列实际的步骤（即一个计算机算法）来「主动」生成组成这个集合的所有自然数。举个例子，设 \(\mathbb{P}\) 为前面说到的素数集合，我们想寻求那些能由两个素数的和（加法）所表示的自然数。假设 \(P(i)\) 给出从小到大排序中第 \(i\) 个素数（比如 \(P(1)=2\), \(P(2)=3\), \(P(3)=5\)，由于加法符合交换律，计算过 \(P(i)+P(j)\) 就不需要计算 \(P(j)+P(i)\)，所以我们只需要找那些满足

\[n=P(i)+P(j)\,,\qquad 1\leq i\leq j\]

的数 \(n\)。给定满足上面条件的 \(i\) 和 \(j\) 组成的“二维”串 \((i,j)\)，我们可以对其进行“降维打击“，让它对应到一个一维序列 \(k\) 中，如下图。

	\(j=1\)	\(j=2\)	\(j=3\)	\(j=4\)
\(i=1\)	\(k=1\)	\(k=2\)	\(k=4\)	\(k=7\)
\(i=2\)		\(k=3\)	\(k=5\)	\(k=8\)
\(i=3\)			\(k=6\)	\(k=9\)
\(i=4\)				\(k=10\)

于是，给定一个 \(k\geq 1\)，我们可以找到唯一对应的 \((i,j)=\rho(k)\) 序列，然后计算 \(P(i)+P(j)\)。

# 计算能由两个素数的和所表示的自然数集合 S
k = 1  # 处理 k=1 的情况
S = set()  # S 一开始是空集
while True:  # 一直循环
    i, j = rho(k)  # 找到对应 k 的 (i,j)
    S.add( P(i) + P(j) )  # 计算 P(i)+P(j) 将结果放进 S
    k = k + 1  # 接下来处理 k+1 的情况 循环

通过上面这个算法，我们「主动」地生成了一个集合 \(S\)，就像之前我们主动地画出了图形一样。现在的问题就是集合 \(S\) 的补集是什么？我们同样可以用一个算法将其计算出来么？用上面 Escher 绘画作品的语言来说，它的衬底（补集）是不是也是图形（可有效生成）？

我们可以先尝试看看 \(S\) 中到底有哪些自然数：

1. 先看看上面表格第一行，即对应 \(i=1\) 所产生的数。由于第一个素数 \(P(1)=2\) 是唯一的偶数素数，所以除了 \(P(1)+P(1)=4\) 是偶数之外，当 \(j>i\) 的时候其他 \(P(1)+P(j)=2+P(j)\) 都是奇数（偶数加奇数是奇数）。这样一来第一行的数很好判断，如果是偶数那么只能是 4，如果是奇数，减去 2 必须是个素数；
2. 然后看看其他情况下所产生的数。由于排除了 \(P(1)=2\) 的情况，所以这里由 \(2\leq i\leq j\) 产生的 \(P(i)+P(j)\) 肯定都是偶数（因为奇数加奇数是偶数）。问题是我们不知道到底哪些偶数能被两个素数相加获得……除非……我们证明了哥德巴赫猜想：

任一大于 2 的偶数，都可表示成两个质数之和。

1. 所以，在上面猜想真的成立的情况下，那么 \(S\) 就是所有大于 2 的偶数以及所有形如 \(2+p,\,p\in\mathbb{P}\) 的数所组成的集合。其补集很好获得，也很容易用计算机程序生成。
2. 但由于目前这个猜想还没有证明，我们不知道是不是存在哪些偶数，它们不能被两个素数相加所获得。由于无法理解 \(S\) 在自然数集合中的具体「刻画」，所以其补集也无法用程序生成。在这种情况下我们就说 \(S\) 是一个非递归的递归可枚举集合。它「递归可枚举」，是因为存在一个算法生成它，但由于我们对它理解（还）不透，它的补集不能被生成，所以它「非递归」。别问我这个学力学的为什么计算理论这么定义这两个形容词……

那现在可以问，是否有哪些算法生成的集合，其补集也能被算法（当然是另外一个）获得呢？用它们的语言，是否存在递归集合呢？

答案当然是是的，素数集合或者奇数集合就是很好的例子。这两者就可以用很简单的算法生成，它们的补集——合数集合和偶数集合——同样如此。相比之前的例子，关键在于我们对这些递归集合有一个很好的「刻画」：即任意给我一个自然数，我可以有效地判断它属于 \(S\) 还是属于其补集 \(\overline{S}\)。这样一来，事实上我们在生成 \(S\) 的同时也生成了其补集 \(\overline{S}\)，两者提供了相同的信息。

对于非递归的递归可枚举集合，我们只能对那些真的在 \(S\) 中的自然数做出判断。在生成的集合里面一个个找，找到就说明在 \(S\) 中。问题是 \(S\) 是无穷的，如果这个数其实不在 \(S\) 中，那判断程序永远都不会停止，我们不知道所以也只能等。

同构的建立

回到之前的类比，我们现在可以把一般音乐、绘图和数学里面的本质相同的现象稍微总结下。

一般音乐	一般绘图	一般算法	产生方式	作用
主旋律	图形	集合 \(S\)	主动	传递主要信息
伴奏	衬底	补集 \(S\)	被动	不传递信息或传递部分次要信息

但对于前面讲到的卡农、Escher 和素数，我们获得了一种「正」与「负」之间的平衡。

卡农	天鹅	素数、奇数	产生方式	作用
主旋律	图形	集合 \(S\)	主动	传递同等重要的信息
“伴奏”	“衬底”	补集 \(S\)	（半）主动	传递同等重要的信息

对于奇数集合，有一个更强的「同构」：他的补集偶数集合可以看作是它自己的一个集合平移，于是对应到卡农中的声部时间平移和天鹅中图形和衬底之间的空间平移。

1. 今天看完了最后一个对话，结果发现最后的最后即又轮回开始…… ↩

2. 数学事实上有很多公理体系，不过这些体系之间大致也应该是「同构的」…… ↩