我准备交替地发布《我为什么选择计算机科学》系列,强调计算机领域的特性和有意思之处(劝进);以及《从0开始的计算机科学》,强调一些基础知识(劝退)。

注意“基础”的意思不是“简单”,而是基本。这也是我劝退的手段。如果你能够理解这些基础知识,那么你学习计算机应该没有什么问题。

这次我们将讨论补码、字符串以及一些非常有趣的,应该了解的内容。

状态与编码

在本章中,我希望能够带给新生对于计算机的一些最基本的要素的认知。我们从创造者的角度来看待计算机的一些最基本要素。 当然在这个过程中我们使用的是“上帝视角”,即当今我们已经对计算理论和物理学等等有了非常深刻的认识后,我们怎样从0开始构建计算系统。

假如你是第一个创造计算机的人

IMAGE

你可能并不会想到太多,也许只是想要计算一些东西。

但是你野心十足 – 你希望了解什么是“计算”,或者计算中有没有“世界的根源”。

无处不在的计算

如果你想要开平方根,一种原则上的做法是,将一个物体按照一定高度自由落体(比如一个硬币),测量时间。由于有:

所以你可以对 $\frac{2h}g$ 开根号。

这样的例子非常非常多,只要你愿意去构造,你总可以发现似乎可以用某些物理过程来解决你想要计算的东西。

IMAGE

但是,我想说的不仅仅是这个。我们却忽略了一件极其重要而本质的事情:为什么我们可以用高度 $h$ 来计算?

有三个其实显而易见但是极其重要的原因:

  • 高度可以有若干不同的值,所以我们可以用它来描述我们想要开根号的数
  • 我们可以轻易地设置不同的高度
  • 自由落体中高度的变化满足我们给定的公式

这些原因是本质的,我们可以换个说法:

  • 高度可以表示计算的内容
  • 高度可以被控制
  • 存在满足我们计算需求的物理机制(或曰演化方程)

但是,高度特殊吗?难道只有高度可以表示计算的内容?实际并不如此。相反的,我们发现,几乎所有的物理实在都可以用来作为计算的内容本身。更加激进的 Stephen Wolfram (Mathematica软件和Wolfram语言的创立者,元胞自动机领域先驱) 等人认为宇宙的本质就是计算(有兴趣可以阅读他的 A new kind of science [1])。

超弦理论的创始人之一 Leonard Susskind 也对计算和黑洞视界问题有深入的讨论 [2],近些年来理论物理界似乎开始了一场以计算的理念(比如全息理论,计算复杂度等)开始研究物理本质的浪潮。

状态

状态,是对系统的一种描述。

如果一个理论对一个对系统状态的描述是完备的,那么系统的一个状态决定了唯一的系统。

一个非常典型的系统是物理学系统。经典力学成就在于,只要给出一个系统的完整的初始状态,那么我就可以预测之后所有的行为[3]。而量子力学的状态描述中含有概率的成分(波尔等人认为这种概率是本质的,是完全的状态),因此长期被爱因斯坦等人诟病,认为这不是一个“完备的状态”[4],进而认为量子力学不完备。

IMAGE

状态的重要意义在于,不同的状态一定代表不同的物理属性;反之不同的物理属性也一定代表不同的状态。之前我们关于高度 $h$ 的例子中,高度 $h$ 就是某种状态。

于是,

IMAGE

Eureka! 我们得到的启发是,

  • 状态可以表示计算的内容,计算的内容就是计算机的状态
  • 需要找一个易于被控制的状态
  • 需要确认存在满足我们计算需求的物理机制(或曰演化方程)

也就是,计算一定是状态的变化;而可控的状态变化一定是某种计算。

如果我们使用经典力学中的状态作为计算机的基础状态,那么这台计算机就是经典计算机;如果我们使用量子力学中的状态作为计算机的基础状态,那么这台计算机就是量子计算机。

同样的,基于状态的载体,又可以是电子计算机,生物计算机,化学计算机,机械计算机 [5]

从连续到离散

经典物理中很多状态是连续的实数,比如电压,位置(讽刺的是,量子力学下却有相当多离散的状态取值)。

由于现实中对状态的控制无论如何都存在这样的情况:

  • 状态的取值范围一定是有限的。过大的距离,过大的电压对任何时代的技术都是不利的
  • 对状态控制的容错区间越大,越不容易出错

IMAGE

这两个情况一组合,必然的结果是,稳定的状态是离散的。

比如电压在 0.0-1.2V 之间,那么我们把 0.4V 及以下的电压视为新的状态 zero,而 0.8V及以上的状态视为新的状态 one。而中间的地带是“缓冲区”,在这个地带的电压可能会产生未定义的,不符合逻辑的行为,虽然原则上0.5V左右实际运算中行为可能还是类似 zero,但是由于不能有绝对的保证,我们仍然认为这是逻辑上无效的状态。

IMAGE

物理状态到逻辑状态

你可能好奇为什么我们不直接使用 01,而是使用 zeroone

原因在于,现在 zeroone 只不过是一种物理上面的状态,代表电压的不同取值范围。我们需要给它们规定逻辑上的状态。

我们规定物理上的状态 zero 是逻辑上的状态 0, 物理上的状态 one 是逻辑上的状态 1

这步看似冗余,但是却是必须的,因为从此之后我们不必再关心物理状态到底是什么,这步开始,物理的状态和逻辑的状态变成了两个不同的层级:逻辑状态基于物理状态,但是对于逻辑状态的操作和描述不必涉及到物理状态。

之后你会发现,这是计算机设计中非常重要的思路,也就是抽象和分层。

这时候的 01 仅仅是逻辑层面的,也不代表数字 0 和 1。我们将包含 01 两个状态的物理属性称为一个位或者比特(bit)。也就是一个位有两个状态, 01

由bit作为基本状态构件(并用来计算)的计算机称为二进制计算机。

非常早期的计算机采用过 10 进制,比如 ENIAC(世界第一台计算机)。下面就是它的背板,可以看到左下角每10个电子管组成一列,构成一个10状态的元件。

IMAGE

状态到编码

状态独立与状态组合

我们的世界(特别是经典物理)的物理量有着这样一种不算平凡的特性:它们之间可以是独立的,无关的[6],一个电路的电压不会影响到另外一个[7]。这样就意味着,我们可以组合多个代表状态的物理量来构成更大的状态:

比如两个 bit 的组合表示 00,01,10,11 4 种状态。我们不难得到,$k$ 个bit 可以表示 $2^k$ 个状态。因此 bit 组合是非常有效的增加状态的个数的手段。

编码问题

编码是信息从一种形式或格式转换为另一种形式的过程。在这里就是给逻辑上的状态以具体的意义(比如把数字对应到某个状态上去),比如数值,布尔值等等。这个完全取决于编码标准,不要把逻辑上的 0 1 直接当做数字。

比如在C语言的逻辑运算中,0 的编码意义是假,1的意义是真。

在程序执行的返回值中,0 的编码意义是成功,1的意义是存在异常或者其他问题。

当然对一个 bit 进行编码是无聊的,我们更加注重对多个位的情况下进行编码的问题,这个时候更有“编”的味道。

对组合状态的编码

编码在更多程度上指的是,对含有多个位的组合状态进行编码,这个时候会非常巧妙。

将状态编码到数字

进制与无符号整数

无符号整数,即没有负数的整数,是我们最最常用的一种数。因而计算机有必要规定一套状态到无符号整数的编码规则。但是一个必要的预备知识是进制。

才开始学习计算机的同学可能对进制的概念不是非常熟悉。 我们最熟悉的进制是10进制,但是历史上被人类使用过的进制却有很多,比如“半斤八两”说明中国古代某些地区熟悉16进制;而角度和时间明显是60进制的(1小时=60分钟,1分钟=60秒,1度=60分,1分=60秒);12进制在多个国家历史中也有提到。

既然古人对进制都如此了解,那么你也没有理由不会。

IMAGE

进制的概念,实质上是一种强调越高位越重要的编序规则。最典型的例子是我们的传统指针时钟。每60秒才相当于1分钟,而每60分钟相当于1小时;通过这种方法,我们不遗漏地将每个小时中的任何一秒对应到时钟的唯一一个状态中。

IMAGE

习惯上,在二进制中,每一个数位用符号0,1表示。8进制用0-7表示,而16进制用0-9,a,b,c,d,e,f表示。南京等具有超长交通信号灯等候时间的城市,在信号灯数字的十位大量采用了16进制类似的编码(比如等待108秒交通信号灯会显示A8)。

无符号数是一种编码形式,即状态只对应非负的整数。

状态到无符号数的编码和解码

此处我们默认都是无符号数。

那么如何将代表k进制数的一个p位状态解码到这个数本身呢?

首先我们要给各个位一个编号,个位(习惯上最右位)地位最低,编号为0;高的位依次增加编号。这样各个位可以组成一个有序的状态序列。

根据各个位的重要程度,一个简单的方式是:

比如一个二进制的状态序列,解码构成为,$1,0,1,0,1,0=2^5+2^3+2^1=42$

而编码的过程相反的,我们用累积除法来实现阶乘的逆操作(阶乘实际上累积乘法)。

上面解码的过程还可以视为 $1,0,1,0,1,0=(2\times(2\times(2\times(2\times((2\times1)+0)+1)+0)+1)+0=42$

于是累积除法的方案就非常明显了:

从下往上就是结果。其他进制的做法类似只不过不是2而已。

k进制加法满足满k进1的特点。乘法和除法的执行过程和十进制一致。

无符号数的位数及容量,溢出问题

由于状态是离散的,位数有限,所以能表达的数字的数量也有限。

但是,计算总是允许我们一直增加数字的大小。我们可以想象总有某次计算可能会产生一定位数的状态无法表示的数字。这种情形很形象地称为 溢出

IMAGE

定理:对于有限长的状态,无论采用何种编码方式,溢出在加法等运算中必然发生。

证明:有限长的状态能编码的数字的个数一定有限,设为K。我们从0开始不断地+1s(误),对于任意一个K,总是可以存在一个累加的次数K+1,此时已经产生K个不同的数;由于抽屉原理(状态的个数相当于抽屉数),至少有两个数处于同一个状态;这与每一个状态对应一个数矛盾。

因此必然存在状态无法表示的数,也就是溢出。

$\square$

对于无符号数的按进制的编码方式,溢出可以分为向上和向下两种(简称“上溢”和“下溢”)。比如 k 个 bit 组成的状态正好能够表示 $0\sim2^k-1$间的所有整数,此时产生负数就是下溢,而超过 $2^k-1$ 就是上溢。

等等,我们还没有讲减法和负数呢。

带溢出加法

如果无符号数加法产生的溢出我们不认为是错误,而是简单的 “扔掉” 超过表示范围的数位(这是非常普遍的做法),那么我们就产生了“同余加法“[8]。

比如一个3个bit表示的数,表示范围是0~7。7+1=8,溢出,除去最高位就是0。用同余式表示就是 $7+1\equiv0~(\text{mod}~8)$。实际上一个由k个bit组成的状态表示的无符号数,在允许溢出时,其加法总是等价于

由同余的性质我们可以知道,带溢出加法满足交换律、结合律等等良好的数学性质。这也是为什么我们简单的扔掉最高位的原因–其背后蕴含的性质一点都不简单。

优雅的补码-统一减法和负数

这里我们要规定减法和负数的处理和编码方式。

在讨论之前,我们先看看,数学上合理的整数和加减法有哪些性质:

  1. 存在一个称为0的数,并且对于任何整数a,a+0 = a
  2. 加法满足交换律、结合律
  3. -a是a的负数,当且仅当 a+(-a) = 0
  4. 减法a-b定义为a+(-b)
  5. 一个数的负数是唯一的
  6. -(-a) = a
  7. -0 = 0
  8. a=b,则 a+c=b+c

性质4说明我们只需要负数的编码即可,而不需要真正的减法操作。一个合理的数学系统中加负数和减法应该是一致的。

然后我们以带溢出加法为基础,试图结合上述数学性质构造出”负数“的编码。带溢出加法显然满足性质1,2,8;性质4仅仅是定义,性质6可以由性质8和性质3推出,性质7可以由性质1和性质6推出;

对于性质5:

证:假设存在B和C均是A的负数,则有

则由交换律和结合律和性质1

$\square$

因此我们只需要按照性质3进行寻找。

我们构造性的按照性质3寻找一个数的负数,那么按照性质5得到的数一定是定义中的负数。

首先引入“反码”的概念。反码的概念非常简单:把每个数的二进制状态中的0变成1,1变成0(在电路中称为“反相”)。一个数和自己的反码的和是什么?

$10010+01101=11111$,显然是全部为1的数。

如果状态的bit数为k,那么必然有(A的反码记为~A):

也就是

按照性质3,

这也就是说,我们并不需要做减法,而是只要做加法和计算反码。并且如果你有群论的知识,可以看出带溢出的加减法实质上构成一个群。而引出带溢出乘法后,可以构成一个环。

上面我们得到了构造编码负数的方式。但是我们还没有定义怎么样的数是负数,而只是一个数是另一个数的负数。为了简单起见,我们规定最高位为“符号位”,符号位为1的是负数,不为1的数值就是它在无符号数里面的数值。加上前面反码+1的计算方式,我们可以确定唯一的有符号数编码方案。这种编码形式称为补码。

补码几乎是各类计算机体系中对有符号整数的唯一编码形式。

也许你能够从下面的图中(以3-bit的状态编码为例)发现一些非凡的对称性。

IMAGE

补码的典型特征在于,负数要比正数多一个。

常见的有符号和无符号整数形式

以当代绝大多数计算机体系的标准而言[9],常见的整数形式有(它们往往被硬件直接支持)

字符型(char)、字节型(byte)

  • 状态位数 8 bit
  • 无符号数值范围 0~255
  • 有符号数值范围 -128~127

短整型(short)

  • 状态位数 16 bit
  • 无符号数值范围 0~65535
  • 有符号数值范围 -32768~32767

整数型,整型(int)

  • 状态位数 32 bit
  • 无符号数值范围 0~4294967296
  • 有符号数值范围 -2147483648~2147483647

长整型(long)

  • 状态位数 64 bit
  • 无符号数值范围 0~18446744073709551616
  • 有符号数值范围 -9223372036854775808~9223372036854775807

一般有实际意义的整数都在它们的范围之内。如果确实遇到还不够的情况,可以通过编程的手段模拟任意长的整数。

PS:Python等语言自带任意长的整数支持,不区分short, long和int等,因此才有“Life is short, I use python”这种双关语。

杂谈:格雷码(grey code)

将状态对应到无符号数的方法可不止利用进制的概念这一种。

grey code就是另外一种,截然不同的方式。

二进制状态组合与广义立方体

你可能无意中发现,k维中的广义立方体,其顶点数是 $2^k$ 个。这并不是一个巧合,实际上你可以把一个k-bit二进制组的所有状态编码到一个k维的立方体上。

方法很简单,就是把每个二进制状态变成顶点的坐标。这样你可以证明相邻的边都是两两垂直的,因而是一个广义立方体。

IMAGE

现在我从0状态出发,沿着立方体的边行走(也就是每次只改变一个bit!),每个顶点只走一次,是否可以走遍所有的状态然后回来?答案是肯定的。

这幅图是三维立方体的平面投影图(包括所有的边)。边连着的两个顶点是只相差1位的两个二进制编码。

IMAGE

其中蓝色实线边就是符合条件的一种路径。(不知道你有没有从这个高度对称的图中找到规律?实际上策略是如果可以沿着圆的边上走到达下一个顶点,就沿着边走;不能就跳到上下对称的地方;在中线就跳到左右对称的地方。可以证明这样对任意维度的立方体都是成立的。)

如果我们在0的时候算第0步,那么走的顶点顺序对应的顶点状态,就是该序号的编码。这就是grey码。

grey 码相邻数字改动只用变动1位,因此操作更加简单且不容易出错,被用于各种需要抗错的场景中。另外考虑这个问题:如果有电路实验需要你尝试所有的开关组合,显然按照grey码的方式操作次数最少。

将状态编码到实数

这部分较为复杂,我不想仔细讲。这里编码标准为 IEEE 754。

将状态编码到文本

串的概念

由于整数常常有其特定的使用范围,所以一般用定长的bit表示。但是很多东西,比如文本,音频这些,长度变化非常大。所以我们不能再用定长的方法来看待。

虽然不定长,但是这些状态往往有“基元”,比如对于文本来说就是字符。于是我们将这些基元连接起来组成的不定长的编码称为xx串,比如文本对应了字符串。

最简单的串是二进制串,即每个 bit 作为一个“基元”。

ASCII

ASCII 是 American Standard Code for Information Interchange 的缩写。现在成为最通用的字符编码标准之一。

ASCII TABLE

ASCII使用7位bit组成的状态表示一个字符,所以一共能表示128个字符。它们的编码都有若干规律,比如数字和字母的编码顺序和我们通常认为的顺序是一致的。数字从十六进制0x30开始,大小写字母间相差0x20 (习惯上我们用0x前缀表示16进制数字)。

但是,ASCII编码的状态存储却是用的 8-bit(这也是为什么8-bit状态表示的数又称为字符型char的原因)。为什么要浪费一个位(ASCII只要7位)?这个在后面我们会提到。

除了显示字符外(可以看到的,具有形态的),ASCII中剩下的都是某种意义上的“控制字符”,它们和当时的打字机和数据传输有关。

趣谈:ASCII控制字符和打印机,以及windows下代码不换行问题

早期可没有像现在一样的键盘而是打字机,如果你看过《辛德勒名单》,可能会对那个时候的打字机有印象。打字机是现代键盘的重要来源(包括QWERTY排列(甚至有些打字机可能略有不同))。打字机是早期计算机唯一的廉价文本输出设备,这也导致ASCII编码和打字机非常相关。

IMAGE

打字机主要由打字头移动并在打字头对应地方印下字母的设备。如果说普通字符让打印机打印该字符,控制字符的主要意义在于控制打字头的行为。

打字机是覆写模式,因为打在纸上面的东西不能移动。而屏幕被广泛作为输出终端后,显然插入模式(我们日常编辑文档用的,允许在中间加入字符并移动后面所有字符到新的位置)更加方便,于是很多打字机的“控制键”在移植到键盘上的时候,其意义发生了改变,但是我们仍然可以从当时的ASCII码中看到这些端倪:

IMAGE

打字机的淘汰造成了很多历史问题,最严重的是回车和换行的合并。现在插入模式下,回车换行这个组合操作大大多于单独的操作。于是问题在于软件如何处理原来的ASCII码?

windows觉得应该保持原来的意思,即你编辑文本换行的时候,windows会帮你输入“回车+换行”,也就是 0x0D0A。而unix系列的操作系统觉得多余,于是就用“换行0x0A”代指回车换行;而Mac系列只采用了“回车0x0D”。

IMAGE

这样带来的问题是,如果你在windows下面使用一个“耿直”的编辑器(比如万恶的记事本)打开其他平台下的文本(比如代码)的时候,就会出现换行丢失的情况。

IMAGE

当然一个好的编辑器不会这么傻。之后我们在其他文章中会讨论编辑器的问题。

编码汉字

ASCII 很麻烦的地方在于无法表示英文字符以外的字符,因此表示汉字需要有自己的规定。

今后你很可能会遇到各种在编程或者软件使用中遇到因为使用中文导致的编码问题(程序崩溃,配置不成功,文件乱码等等)。这是由于汉字非常复杂和混乱的编码方案造成的。由于这些麻烦是实在的,因此我希望你们能够了解一下这些编码。

汉字的编码方案主要有5种:GB2312,GBK, GB13000, GB18030,和Unicode形式。目前这5种可能混用,造成各种潜在问题。我们推荐如果可能,都采用 Unicode 方案。

GB 2312

或称 GB 2312–80 是中华人民共和国国家标准简体中文字符集,全称《信息交换用汉字编码字符集·基本集》,又称GB0,由中国国家标准总局发布,1981年5月1日实施。GB 2312编码通行于中国大陆;新加坡等地也采用此编码。中国大陆几乎所有的中文系统和国际化的软件都支持GB 2312。

GB 2312标准共收录6763个汉字,其中一级汉字3755个,二级汉字3008个;同时收录了包括拉丁字母、希腊字母、日文平假名及片假名字母、俄语西里尔字母在内的682个字符。

GBK

显然GB 2312只覆盖了常用的汉字而已,并且对汉字音标、汉字部首以及一些图形符号支持很差。于是后来推出了兼容GB2312的GBK。

汉字内码扩展规范,称GBK,全名为《汉字内码扩展规范(GBK)》1.0版,由中华人民共和国全国信息技术标准化技术委员会1995年12月1日制订,国家技术监督局标准化司和电子工业部科技与质量监督司1995年12月15日联合以《技术标函[1995]229号》文件的形式公布。 GBK共收录21886个汉字和图形符号,其中汉字(包括部首和构件)21003个,图形符号883个。

GBK的K为汉语拼音Kuo Zhan(扩展)中“扩”字的声母。英文全称Chinese Internal Code Extension Specification。

GB 13000

然而过了若干年人们发现了原来编码的重要问题,其中之一是和国际标准不接轨,并且可能会和别的国家的字符编码,或者将要制定的新的编码冲突。为了和国际标准(下面讲的Unicode)接轨,制定了GB 13000。由于是个过渡版本,使用的并不多。

GB 13000,中华人民共和国国家标准的国家标准代码之一,全称 GB 13000.1-93《信息技术 通用多八位编码字符集(UCS)第一部分:体系结构与基本多文种平面》

GB 18030

GB 18030,全称:“国家标准GB 18030-2005《信息技术 中文编码字符集》”,是中华人民共和国现时最新的变长度多字节字符集。对GB 2312-1980完全向后兼容,与GBK基本向后兼容;支持GB 13000(Unicode)的所有码位;共收录汉字70,244个。

它是GB 13000的拓展,并兼容更新的Unicode标准。

Unicode

看了上面那么多种汉字编码方案,你可能会感到头晕。实际上这个问题也困扰很多国家很长时间(比如各个国家的编码冲突,或者符号被多次定义),绝对不止中国。

于是后来大家约定了一个世界统一的文字编码标准,称为 Unicode(万国码,国际码,统一码,单一码)。GB 13000 和 GB 18030 都考虑到了和 Unicode 的兼容。

Unicode只是一种标准(约定各个国家的编码区间等等),而不是一种编码机制。Unicode的实现方式称为Unicode转换格式(Unicode Transformation Format,简称为UTF)。

GB18030就是一种更注重汉字的UTF,收录了非常冷僻的一些汉字。现在比较通用的UTF是UTF-8,它支持几乎所有你曾经见过的和想得到的汉字,我相对推荐将其作为默认的编码方案。

字符串

好了。。。好了。。。既然字符有了标准之后,我们要考虑怎样表示文本了。文本可以表示为字符的串,也就是字符串。字符串最重要的一点在于如何定义它的终止。

NUL-终止字符串

还记得ASCII表中的第一个符号是NUL(0x0)吗?为了易于表示它,我们强行给它一个形式 \0

NUL-终止字符串遇到 \0 就代表结束,这是C语言等常用的形式。

比如下图中字符串的长度实际上为5,因为\0后的东西虽然是实际的状态,但是却不计入串之中,而\0本身不带任何含义,所以是5。

IMAGE

从这里可以看出串编码实质是对状态的子空间的选择。

结构体字符串

NUL-终止字符串巨大缺点在于,不允许在串中间使用 \0,否则会被截断。它另外一个缺点是长度不能被直接得到,在你看到\0前你无法实现估计一个未知字符串的长度。

于是我们可以考虑把长度的数字编码作为开头和后面的内容构成“结构”,用来表示字符串的长度和范围。

IMAGE

这是现代很多编程语言采用的形式,尤其是使用OOP的(面向对象编程)。

杂谈:我们从来没有真正表示过无限

我们在数学中似乎经常用到无限不循环小数(比如$\pi$)、无限大、任意一个、全体这些“无限”的概念。这些让我们担心是否计算机的离散的状态表示无法“完全描述”这些东西。

实际上不是。因为我们至少知道有一种方式可以用离散而有限的字符串表示我们能够想得到的对象,包括人类迄今为止所有的论文和书籍。

这是称为 LaTeX 的排版系统。我们来看几个例子:

  • 黎曼猜想的等价表述(素数分布猜想)

LaTeX 表示: \left|\pi (x)-\int _{0}^{x}{\frac {\mathrm {d} t}{\ln(t)}}\right|<{\frac {1}{8\pi }}{\sqrt {x}}\,\ln(x),\ \ {\text{for all }}x\geq 2657

  • 爱因斯坦广义相对论场方程的张量形式 (非量子力学的动力学方程)

LaTeX 表示: G_{\mu\nu}\equiv R_{\mu\nu}-{\textstyle 1\over 2}R\,g_{\mu\nu}={8\pi G\over c^{4}}T_{\mu\nu}

  • 广义含时薛定谔方程的算符形式(非相对论的量子力学方程)

LaTeX 表示: \hat H\Psi=i\hbar\frac{\partial}{\partial t}\Psi

总结

我们干了什么?

我们在抽象。抽象是计算机科学中非常非常普遍的手段。

下面的图清楚地表示了这一点(红色虚线框内是我们这次重点讨论的内容)。计算显然依赖于物理行为,但是在物理行为上描述计算并不是最有效的办法。

IMAGE

我们考虑稳定性以便进行逻辑上的抽象,于是我们在逻辑状态的层面上讨论。而要考虑数字、字符串等,我们又需要到编码表示的层面上讨论,因为此时才可以用上我们的数学。

抽象的代价

抽象是为了换一种易于分析的角度看问题,它丢弃了一些底层的因素,因此要求底层这些因素确实可以丢弃。

比如逻辑状态的抽象,依赖于物理状态的稳定。像太空等环境中,宇宙射线会破坏这种稳定性,因此我们需要采用特定的手段(特制的芯片,外围防护,低频电路)来维护我们的稳定性,这样上面的逻辑状态的抽象才能被保证,计算机才能“正常运行”。

其实计算机从来没有“不正常”的情况,哪怕被雷劈了也是按照物理规律忠实地烧坏里面的硬件,而我们所称的“不正常”,实质上是一种对我们的“抽象”破坏,比如破坏元件的高压并不在我们的抽象范围内。

什么时候才能把计算机造给我看?

这次是为了之后的内容铺平道路。

IMAGE

之后我们需要讲解两个非常非常关键的概念,一个是现代计算机的数学模型–图灵机(偏计算理论),而另外一个是体系结构模型–冯诺依曼体系结构(偏计算实现)。这两个东西为当代计算机的发展起到了奠基的作用。

等这些弄清楚后,你再摘取最上层的程序,会轻松很多,豁然开朗。它会给你带来不一样的认识。

写后感

哇,画图真累。查了很多资料。

Reference & Note

[1] Wolfram, S. (2002). A new kind of science (Vol. 5). Champaign: Wolfram media.

[2] Susskind, L. (2016). Computational complexity and black hole horizons. Fortschritte der Physik, 64(1), 24-43.

[3] 可能有人会提到动力学混沌的问题。但是这并不是物理学系统本身的问题,而是病态的演化环境会带来病态的解。很多时候增加精度确实可以部分解决问题。一个典型的例子是气象动力学,虽然“蝴蝶效应”说一只蝴蝶能引起一阵飓风,但是不可否认的是随着现在计算能力的提升,观测精度的增加,天气预报的准确率越来越高,预测也越来越实时(预测每个小时而不是每一天的天气不是什么问题)。

[4] 为了使得状态完备,他们在状态中加入“隐变量”(hidden varible,不可直接观测的变量)。如今局域实在隐变量理论已经被实验证否,而非局域的一些隐变量理论仍然无法设计实验证明(就像说“有一只感觉不到的龙一样”),只是另外一种世界观而已。

[5] 例如英国科学家查尔斯·巴贝奇研发的差分机(Difference engine)。这是一段很传奇的故事,巴贝奇耗尽心血试图制造这种远超时代技术能力的机器,最终下场非常惨。但是这台机器毫无疑问有着现代计算机的影子,尽管当时他只是为了计算差分,解决当时各类数学计算中错误百出的情况。

[6] 如果你对这种状态的独立性感兴趣,一个关键的概念称为“自由度”(degree of freedom)。

[7] 但是量子计算机要实现状态独立是非常困难的事情(但绝对不是原则上不可实现),很多量子体系下靠的近的元件之间很难不发生一些反应,而且它们还会和环境互相作用,很快发生所谓退相干效应。这是目前存在的主要问题之一。

[8] 同余是指两个算式在除以某个数k的情况下,余数相等。通常写成 $A\equiv B~(\text{mod}~ k)$的形式。

[9] 历史上由于硬件等的改进,一度十分混乱。这里给出的是绝大多数语言规定中标准的数值范围,他们和硬件和系统环境无关。