type
Post
status
Published
date
Jun 5, 2019
slug
summary
（注：本文乃本学期学习各门课程之后，尤其是学习“离散数学”的各个领域后，对于数学抽象性和计算机的思考，写给同龄的同学。好像自己这种垃圾也不配把自己写出来的东西称作“科普文”，那就暂且称为费曼学习法的产物吧。）
【风格 历史性质 讲到希尔伯特“我们终将知道 我们必将知道”
霍金在他的理论物理科普书《...
tags
category
技术分享
icon
password
（注：本文乃本学期学习各门课程之后，尤其是学习“离散数学”的各个领域后，对于数学抽象性和计算机的思考，写给同龄的同学。好像自己这种垃圾也不配把自己写出来的东西称作“科普文”，那就暂且称为费曼学习法的产物吧。）
【风格 历史性质 讲到希尔伯特“我们终将知道 我们必将知道”
霍金在他的理论物理科普书《大设计》中介绍过一个很有意思的“生命游戏”——用0和1的二维格子图像和一些规则，能够创造出一个“宇宙”。
这个“游戏”其实是数学家康威设计的一个细胞自动机，它基于离散的数学系统的构造、作用和关系。简单来讲，康威用简单的代码设计了一个能够产生“复杂生命现象”的系统，这个系统只有三条基础规则：
- 每个格子（像素）值为0或1。若一个格子周围有3个格子为1，则这个格子为1。
- 如果一个格子周围有2个格子为1，则该格子的值不变。
- 其他情况下，该格子的值为0。
令人惊讶的是，形状和秩序能从杂乱的“0-1”编码中产生出来。依靠如此简单的几条规则，这个程序竟然能生成“细胞”、“滑翔机”、“滑翔机枪”、“葡萄藤”等动态复杂“生命”结构，它们甚至还可以繁殖、自我复制和衍生后代。
很久以前第一次在这本书上看到细胞自动机的时候，我便沉醉于其精妙的构想。逐渐地，这样的问题扎根于我的脑海——所有现实世界中的具体问题、科学原理，都可以用数学的模型和运算来解决吗？
而这些表面上看来纷繁复杂的现象，最终是否都可以归结到最简单的几条规则？
一 物理模型
早在遥远的古希腊时代，毕达哥拉斯便提出了“万物皆数”的概念。
xx世纪是决定论(determinism)盛行的时候。在当时，牛顿定律的提出和实验科学的发展，
这一理论又由拉普拉斯发展完善，他认为：
我们可以把宇宙现在的状态视为其过去的果以及未来的因。假若一位智者会知道在某一时刻所有促使自然运动的力和所有组构自然的物体的位置，假若他也能够对这些数据进行分析，则在宇宙里，从最大的物体到最小的粒子，它们的运动都包含在一条简单公式里。对于这位智者来说，没有任何事物会是含糊的，并且未来只会像过去般出现在他眼前。
19世纪后，近代的量子力学诠释使得拉普拉斯的决定论观点受到质疑。
英国粒子物理学家、神学家约翰·波金霍尔指出，由于电子位置的不确定性，即使在相互作用仅考虑牛顿力学的情况下，试图计算一个气态氧分子（O2）在与其他分子碰撞50次（约0.1ns以内）后的位置也是无效的。[[2]](https://zh.wikipedia.org/wiki/%E6%8B%89%E6%99%AE%E6%8B%89%E6%96%AF%E5%A6%96#cite_note-2)
【【【【【薛定谔方程描述的是，在没被观察时，组成世界的粒子在空间某处出现的可能性随时间的变化，其绝对值的平方对应着粒子在该处出现的概率密度（probability density）。在量子力学中，粒子的波动性被称为“几率波”或“概率波”，描述它的函数被称为“波函数”。几率波是关于“可能性”的数学，绝不是我们所熟知的、僵硬确定的“东西”。我们可以把它想象成一团“数字的烟”，它在空中的分布并非均匀，所以在不同的地方有不同的浓度；而且它在“飘动”，所以在空间中各点的浓度是随时间变化的。薛定谔方程就是描述在空间中某点，“烟”的浓度随时间变化的方程。
量子物理学家们给这个变化过程取了个玄幻而赋有动感的名字，叫做“塌缩”（“collapse”）。没有观察，就没有塌缩，也就没有被观察到的粒子态，所以不仅“观察”对于实验不可或缺，而且实验结果根本就是“观察”所导致的——你所看到的是因为你在看。量子物理学家玻尔总结得很好：“任何一种基本量子现象只在其被记录（观测）之后才是一种现象”，“而在观察发生之前，没有任何物理量是客观实在的”。
以玻尔为首的科学家们认为，没被观察时，世界只是一大堆“数字的烟”（几率波或可能性），时间、空间、物质、能量浸没其中，每个观察者用“观察”创造了自己眼中的现实。德国物理学家海森堡说得一针见血：“原子或基本粒子本身不是真实的，它们组成了一个潜在或可能性的世界，而不是一个实物或事实的世界。” 玻尔也说：“所有我们称之为‘真实’的东西是由我们不能称其为‘真实’的东西组成的。”（他十分明白这有多违背常识和直觉，“如果量子力学没从根本上让你震惊，那你就还没弄懂它。”） 】】】】】
世界又陷入了不确定性。
我们先离开对于宇宙与物理模型的探索，来聊一聊纯粹的抽象——数学。
二 同构，抽象与算法
刚开始接触离散数学中命题、谓词、集合、关系、图这些概念的时候，我产生了一个疑问：这些枯燥的概念能够解决什么具体的问题？又不能解决什么问题？
我认为在数学的学习中，寻找不同问题的共性以及对于各种具体结构的“抽象”是非常重要的一种思想。这也是数学这门学科最大的意义之一。
学到代数系统这章的时候，提到了两个概念：同构和同态。
只要一个线性变换 T:V → W 是可逆的，那么这个线性变换就称之为同构（英語：isomorphism)。若两个数学结构之间存在同构映射，那么这两个结构叫做“是同构的”。如果忽略同构对象的属性或操作的具体定义，单从结构上讲，同构的对象是完全等价的。
（概念解释，精确定义与通俗解释）
【举个例子，在加法中的xxxx，和幂的乘法，这两个系统是同构的。】
我们可以通过同构来解决问题。
自己当时有一种恍然大悟的感觉。如果把精确的“同构”概念延伸到生活中的方方面面，。（只考虑共性，xxx）有很多类似的精妙例子，比如《费恩曼物理学讲义》里讲到过用电路问题研究力学。
恰好在那段时间看到物理所的一篇推文，讲的是数学家们是如何玩扫雷的。
遇到未知的雷区时，扫雷的高级玩家会通过假设、反证法等推理规则来判断地雷的具体位置，但这还不够厉害。我们其实还可以用更加量化的数学方法——布尔代数进行计算和分析。
而这样我们就可以把扫雷的推理问题转化为布尔代数的运算问题：与运算，或运算，非运算，异或运算等。比如两个相邻的格子，周围都是1，那么可以把其中一个格子视作输入的x，另一个格子视作输出的y，则有y=┑x……结合命题逻辑推理的知识，这可是能把问题简化不只一个层次。
更进一步，扫雷中的一些雷区图案可以视作传递信号的导线，另一些图案则可视作逻辑门——与门、或门、非门。将这些基本的电路元件组合起来，相互连接，利用电路的模型便可以解决复杂的扫雷问题。
应用本学期课程第五章代数系统的知识，扫雷游戏、逻辑门、计算机系统，在多层抽象之后其实是一致的。也可以说，它们的某些性质可以视作是同构的。
我们来看看终极玩家——英国的某位数学家是怎么做的。他用扫雷游戏中的逻辑规律构建了一系列电子元件，用电子电路模拟雷区。然后将给定的雷区图案交由计算机来判断是否可解。
算法课最后一节学习的是第一个被证明是NPC问题的问题：布尔可满足问题（SAT）：在已知逻辑电路输出结果的情况下，能否确定每个输入的值。
而扫雷问题在一些时候等同于SAT问题。由于它是一个NP完全问题（注：P是多项式时间可解，NP是多项式时间可验证，NPC用人话说就是比所有 NP 问题都要难的 NP 问题）由此看来，当扫雷问题足够复杂时，不要说得出解了，就连验证解都是一件难事。
学离散和算法课的时候，我最大的收获，就是理解了一种思维方式：如何将现实生活中的种种具体问题如何转化为能够为计算机所实现的数学问题。而这种创造是最令人兴奋的。
三 语言
我们要谈的另外一个话题是数学和语言，虽然听起来可能风马牛不相及。这在人工智能的自然语言理解领域中应用广泛。用计算来研究语言，这是一个很棒的跨学科思路。通过“可量化”的计算，用数学工具以公理化的方法描述并解决一些人们在以前只能用语言来解决的问题。
在此之前需要介绍形式语言和形式系统的概念。
形式语言是没有任何语义内容的人工语言。
我们日常生活中的“语言”，由语法和语义组成。研究形式语言只注重语法，而不在意语义是否正确。比如“猪能在天上飞”，它是满足语法的，但是语义不正确，但它是合格的。
形式语言非常重要，它是当代计算机科学的基础，由其发展而来的“自动机理论”（开头所说的细胞自动机是其中的一种）是编译原理的基础，构成了计算机的数学模型。
形式语言 + 描述推理规则或转换规则的集合，便构成了形式系统。可以理解为一种解决一类问题的抽象结构。比如我们在离散第1章学的命题逻辑，经过命题演算进行公理化，就能建立一种形式系统——命题演算系统。
一个形式系统可能是为了描述真实现象或科学问题而设计的。比如，形式系统中的公理如果变成数学中的基础公理，那么它就可以用于解决数学问题。我们在数学中所熟悉的欧几里得平面几何、集合论、布尔代数，都是形式系统。
当然，独立于现实世界，形式系统也是有意义的，即使它纯粹抽象地制定出来，只是为了研究其自身。例如，《哥德尔、埃舍尔、巴赫》这本书里谈论过一个如何在“WJU系统中生成WU的问题”，这是一个很好的描述形式系统如何生成定理的例子。书中的p-q系统虽然可以描述加法运算以及其他具体问题，但这种抽象结构具有独立于一切具体现实之外的意义。
形式系统不仅能解决计算机科学的问题，还可以解决数学问题。它甚至还可以解决一些文科问题，比如哲学。严格的学院派的哲学是建立在严密的推理基础上的。而当推理过于复杂时，再聪明的头脑也无法胜任了。但如果采用形式语言和形式系统，便能快速得出结果。人工智能中的专家系统，最初便是基于这样的原理制造出来的。
【以上谈的是基于规则的自然语言理解，而在基于大数据和统计的自然语言理解领域，人们采用隐马尔可夫模型，将问题抽象成一个篱笆图，再用维特比算法来求解诸如拼音输入法和语音识别之类的问题。这里又用到了图论和最小路径的知识。同样的思想方法不仅可以用于语言，还可以用于图像处理、信息处理等，因为它们之间具有的共性，经过抽象之后，可以用同一个模型来进行研究。】——【这段比较无关吧 先不放】
我们也可以说，形式语言让我们把语言扩大到了一个广义的范畴，图像是语言，数学是语言，音乐也是语言，表情和动作也是语言。世界万物，只要有组织地组合在一起，便是语言。而计算模型和形式语言很相似，形式语言和计算模型可以研究任何问题——这是高层的抽象。
再讲到法律。。
城市规划也能算语言问题吗？可以放进去吗？
让我们回到在文章开头提到的“生命游戏”。有人会说：“这不就是个游戏吗？有什么用？”
事实上，细胞自动机只是一个抽象模型，它能解决的具体现实中的问题非常非常多。比如可以用于研究形式语言。比如可以用于设计大规模集成电路。它还可以用于研究计算机科学中的问题。当自动机中的“滑翔机”结构被射向一个活方格组成的2*2方块时，如果滑翔机径直靠近静止方块，方块要么向着它移动要么背离它。按照这种方式，方块就能模拟计算机的记忆。事实上现代计算机的所有基本函数，诸如与门与非门都能用滑翔机建立。类比电信号运用于物理计算机，滑翔机的流束也能用来发送和处理信息。
各种计算模型，在某些性质上，是不是也可以看作是“同构”的？
那么，我们自然而然地产生了一个问题：所有问题都是可计算的吗？
四 可计算性
一位顶尖的物理学家惠勒提出了现代版的“万物皆数”，叫做“万物源于比特”（“It from bit”）。
比特（bit）是二进制数字中的位，也是信息量单位。惠勒认为，世界源于信息，是信息的表达；物理世界中的物质都有非物质的根源和解释。“换句话说，任何东西——每个粒子、每个力场、甚至时空连续体本身，其功能、其意义、其存在，全都是从测量装置对“是/否”问题、二元选择、比特所给出的答案中产生出来的——即使在某些情况下是间接产生的。”
后来的量子物理学家们对这想法进行了深化，认为“万物源于量子比特”：空间是量子比特的“海洋”，基本粒子是量子比特的“波动涡旋”，基本粒子的性质和规律起源于“量子比特海”中量子比特的组织结构（即量子比特的序）。
【在这里再举几个例子，算法岗位里的，比如城市规划】
著名的丘奇-图灵论题在几百年来也一直引发着人们的争论：所有计算或算法都可以由一台图灵机来执行吗？又或者可以说，逻辑和数学中的有效机械方法都可由图灵机来表示吗？
而图灵机之中的所有问题都可解吗？并不是。有一些问题是不可解的，比如停机问题——判断任意一个程序是否会在有限的时间之内结束运行的问题，就是不可解的。它存在自指的矛盾，就像悖论一般。
又如同哥德尔在其不完备性原理中论证的：真实不一定可证明的。一个系统内必将包含不可证实又不可证伪的问题。
【数学模型可以解决逻辑问题，但是解决不了非逻辑问题】
也许最后可以归结到维特根斯坦的那句话：
“对无法言说的，我们保持沉默”
【【【而所有可计算的问题，都能拥有一个简单而优美的模型吗？】】】
我们回到霍金的《大设计》，以全书篇末的这一段话结尾：
“真正的奇迹也许在于，逻辑的抽象思考达成了一个能够预言和描述我们看到的令人惊异的千姿百态的浩瀚宇宙的唯一理论，如果该理论被观测证实，它就将是以往3000多年来智力探索的成功终结——那么我们就可以说我们找到了那个伟大设计。”