从自然数到计算机

 

“没有一本教材是自包含的。”

( 这篇东西大致上前半是来自 书《陶哲轩实分析》的片段,后半是来自 维基百科,和 MIT公开课 MIT6_00SCS11 lecture 1)

1

同济第六版《高等数学》书的章节安排如下:

  1. 函数与极限
  2. 导数与微分
  3. 微分中值定理与导数的应用
  4. 不定积分
  5. 定积分
  6. 定积分应用
  7. 微分方程
  8. 空间解析几何与向量代数
  9. 多元函数微分法及其应用
  10. 重积分
  11. 曲线曲面积分
  12. 无穷级数

第一章,第一节,作为全书基础,定义了集合,使用了“自然数”这个概念,但是位置被夹在了集合概念段落的中间:“…… 习惯上,全体非负整数及自然数的集合记作 N。 ……”

没有进一步说明什么是自然数。Fuck you.

2 进一步……?

(做过微积分但是感觉心理不踏实,怪怪的,不妨看看实分析。实分析试图说了说什么是自然数,什么是集合。实分析这种东西的存在,至少说明,有人曾经这样分析的思考过数学的这个部分。)(这里的不踏实的感觉竟然就是……第二次数学危机)

实分析(实数的分析,实数序列,实数级数和实值函数的分析)或者旧时的实变函数(以实数为变量的函数),可以作为微积分的理论基础,而微积分则是用来处理函数的那些规则的汇集。

  1. 什么是实数?有没有最大的实数?在0之后,“接下去的”实数是什么?(最小的正实数是什么)你能不能把一个实数分成无限多份?为什么像 2 这样的数有平方根,而 -2 这样的数就没有?如果存在无限多个实数,也有无限多个比例数,那么实数比比例数“更多”这话从何说起?
  2. 怎样取一个实数序列的极限?那些序列有极限而哪些没有?如果你可以制止一个序列跑向无穷,这是否意味着此序列终究会停止变化而收敛?你能把无限多个比例数加在一起而终止于一个非比例数吗?如果你重新排列一个具有无限和的级数的元素,所得到的和依然一样吗?
  3. 什么是函数?说一个函数连续指的是什么?可微是指什么?可积指的是什么?有界指什么?你能把无限多个函数加在一起吗?取函数序列的极限是什么意思?你会微分一个函数的无限级数吗?求积分是什么意思?如果函数 f(x),f(0)=3 而 f(1)=5,那么当 x 在 0 和 1 之间走动时,它必须取到 3 和 5 之间的每个中间值吗? 为什么?

微积分可能已经讲过其中一些问题,但是这些问题对于微积分课程来说大体上只是第二位重要的,微积分强调的是让你实施计算。但是当你已经熟悉这些东西,并且知道如何进行计算,就可以回到理论,并力图真正理解所发生的事情。

3 为什么做分析

了解事情为何起作用,在一定意义上是件乐事。但是一个务实的人可能会争辩说,人们只需要知道对于处理现实生活问题,事情怎样起作用就行了。

在入门课程中接受的微积分训练肯定能初步解决许多物理,化学,生物,经济,计算机科学,金融,工程或者其它行业中的问题,你会使用链式法则,L’Hopital 法则或者分部积分等诸如此类的法则,而可能不太熟悉这些法则为何会起作用,或者不知道对于这些法则是否有什么例外之处。但是如果使用法则的时候不知道这些法则从何而来,对它们的使用有何限制,那么就可能产生麻。

例如,一个直角三角形(0,0),(1,0),(0,1)斜边长是根号2。如果用横竖横竖的“梯子”去近似斜边,当梯子数目N无限增多时,梯子明显的接近斜边,但是总长度是2N/N = 2 不等于 根号2。这是哪里错了?

4 重新思考自然数

与数打交道已经十多年了,本能的会使用代数法则。但是这些法则为什么是对的?为什么 a(b+c) = ab + ac 总是对的?这个法则(分配律)是可以用更为简单原始的也是更为基本的性质来证明的。

复习中学和基础微积分的材料,能看到自然数系是最原始的数系。它被用来构作整数,整数再被用来构作比例数,比例数被用来构作实数,实数被用来构作复数。

所以,要想从最原始处开始,必须考察自然数。我们可以试着考虑以下问题:人们是怎么实际定义了自然数的?(这和如何使用自然数是非常不同的问题,就比如你会用计算机和知道如何造计算机是非常不同的)

考虑这个问题的麻烦在于,你用自然数太久,以至于不必思考就能使用各种假设(比如 a + b 等于 b + a)。所以我们不得不做一个艰巨的任务:暂时忘记所有这些看似理所当然的法则,忘记怎样计数(1过了是什么?),忘记加法乘法,忘记运算律…… 然后从最基础的问题开始,一步一步的重新引入这些概念,在这个过程中,我们就能明白的鉴别出哪些是基础,哪些是我们可以证明并建立的东西。

5 Peano 公理 (皮亚诺公理)定义的自然数

Peano 公理是定义自然数的一个(不是唯一的)标准方法。(1889年, by 意大利人皮亚诺《新方法陈述的算术原理》)

(在这之前的另外一个方法,是先定义有限集合,然后用集合的基数去定义自然数。1874 年,by 德国人康托尔。大意:集合{ 1,2,3} 和 {2,3,4} 不一样,但“基数”相同。什么叫基数相同?如果两个集合元素可以一对一的对应起来,说明它们数目一样多,就叫做基数相同。这方法甚至可以比较无穷集合的大小。在有些数学教材里,有些定理常常用到“可列/可数集”,这个说法就是康托尔创造的,用于指元素可以和自然数集或自然数子集一一对应的集合。康托尔最后疯了)
另外,如果再往更早的时间看过去,就是加法的历史了。 https://en.wikipedia.org/wiki/Addition#Notation

康托尔做集合论 是为了解决微积分基础的不严密问题。(鬼才知道)

皮亚诺做公理化自然数,是 自费马和笛卡尔把几何代数化之后,人们想把逻辑代数化,进而把数学公理化的尝试。(也许吧)

189x ~ 190x 是公理化浪潮时期,许多数学里的对象被公理化。公理化的好处有 “抛弃基本概念的朴素定义——从而避开悖论,拥抱不多不少的我们需要的特性——从而足够数学使用 ”(很像 duck type), “基础公理没问题则整个理论都没问题 ” 和  “知道整个理论的能力边界在哪里 ” 以及 “通过修改 /变换公理 就可以得到 新理论 ” 等。

在皮亚诺之前,人们说,自然数是集合 N := { 0, 1, 2, 3, 4, … } 的元素,就是从 0 开始一直往前数会数到的所有的数,这些数组成自然数集合 N。

皮亚诺知道这个定义(嗯…好吧,这很难说)。但是这还有问题:你怎么知道一直数下去不会出问题?比如循环到 0?你怎么在这基础上定义运算?

如何定义运算似乎比较好理解,乘法是加法的重复,乘以 3 就是连续做 3 次加法。而加法则是向前数或者增多的动作。这个动作似乎没法更基本了。

于是,为了定义自然数,我们使用两个基础概念:数字0,以及增长运算。写成公理形式:

公理1:0 是一个自然数。
公理2:如果 n 是自然数,那么 n++ 也是自然数。(n++表示n增长后得到的数)。

定义1:定义记号 1 是数 0++, 2是数 (0++)++,等等。

但是还有问题。(问题1)

比如有一个数系,它的 65535++ = 0 (计算机里整数二进制可能发生这样的例子)。这样的数系满足公理 1 和 2,但不是我们直观相信的自然数系的样子。

于是我们加上:

公理3: 0 不是任何自然数的后继。即对于每个自然数 n, n++ 都不等于 0。

好现在我们可以证明 4 不等于 0 了:因为 0 是自然数(公理1),所以2,3 都是自然数(重复使用3次公理2)。然后按照定义1和公理3,得到4不等于0。

但是还有问题。(问题2)

这个数系可以在 4 处停止了。就是说 5=4,6=4,7=4 等等。这和公理 1,2,3 都不矛盾。

类似的,5 = 3,这种在尾巴上转回来但是不转到 0 的诡异的数系,也和公理 1,2,3 不矛盾。

于是我们加上:

公理4:不同的自然数必须有不同的后继。就是说如果 n,m 都是自然数,并且 n 不等于 m,那么就有 n++ 不等于 m++。(等价的说,如果 n++ 等于 m++,则必有 n = m)

现在好像保证了所有自然数彼此两两不同了。

但是还有问题。(问题3)

非正式的例子:(混入了我们还没有定义的比例数)N := {0, 0.5, 1, 1.5, 2, 3, 4, …} 像这样有一些“流氓”元素混在里面,这个例子是要说,这个数系满足公理 1,2,3,4,然而我们希望数系“仅”包含可以从 0 以及增长运算得到的数。

但是这个不好描述。幸运的是,有一个朴素的说法:

公理5(数学归纳法原理):设 P(n) 是自然数的任意性质。假设P(0) 为真,又假设 当P(n)真时P(n++)就真,那么P(n)对每个自然数n都是真的。

公理5 更像一个“公理框架”。它产生无限多个公理模板。(在逻辑学里有对这种现象的研究)

公理5 说明,从公理 1,2,3,4,我们可以得到 0,1,2,3,4 … 这些数满足自然数的性质,但是无法得到那些混入的流氓也满足自然数的性质。所以这个集合并不是自然数集。

试着证明一下:设 P(n) 为命题“n不是半个整数”。首先,P(0) 是真的。其次,如果 P(n) 是真的,那么 P(n++) 是真的。// x.5 不是由0 按照公理1,2,3,4 生成的那些数 1,2,3,4 …由公理5,每个自然数都不是半个整数。特别的,0.5 和 1.5 都不是自然数。

公理 1~5 就是 Peano 公理。它们非常可信。

现在我们可以做出假设:假设1: 存在一个数系,称其元素为自然数,公理 1,2,3,4,5 对此数系成立。

现代分析的一个非凡成就是,只从这5个非常原始的公理和集合论中的某些附加的公理出发,就能建立起所有的其它数系,创造函数,并做我们通常做的全部代数和微积分。

注:有趣的结论:每个自然数都是有限的。证明:因为0是有限的,并且如果 n 是有限的,n++ 也是有限的(或者说,n++是n后面那个数,它增加之后还有新的数,n++不是无限),按照公理5,所有自然数都是有限的。这就是说,虽然自然数集合可以趋向无穷,但是每个自然数都是有限值,无限不是自然数。(存在其它数系,容纳“无限的”数,例如,基数,序数,p进数,但是它们不满足归纳法)

注2:到此为止,这个对自然数的定义是公理化的,不是构造性的。不是用其它的东西来构成自然数,而是说了可以用自然数做的事情(增长),以及它们具有的某些性质。数学就是这样干活的(注:参见末尾反对意见),它抽象的处理它的对象,只关注它们的性质,而不是它们代表了什么东西。——所以你可以注意到,皮亚诺的5个公理中有三个未定义的概念“数”,“零”,“直接后继(增长动作)”,它们不被直接定义,而是由公理的描述间接体现他们的概念。(公元前 384 ~ 322 年的亚里士多德对定义的想法类似这个精神,他说定义只不过是给一批文字定个名,又指出必须用先存在于所定义事项的某种东西来表述。他因此批评 “点是没有部分的东西”这一定义,认为“那种东西”这几个字没有说出所指的究竟是什么,除非可能就是指“点”,因此这定义并不合适)他承认未经定义的名词是需要的,因为在一系列的定义里总得有个开头,但是其后的数学家漠视这一需要,直到19世纪末。Update: 这里描述的公理的浮现过程,即貌似时间线上的自然衍生,又是经过反复推敲而存留的洞见,因果关系在此变得模糊,即使换一种物种,即使用不同符号,它们也会推出同义的公理,智慧在此闪耀。在这个意义上,公理是如此的近似真理,因为我们就是真理,我们是自然的一部分。)

注3:历史上实现数的公理化处理,只不过 100 多年的时间。以前对数的理解总是不可避免的与某种外在概念联系,每次数的理论进步(比如从整数到分数,甚至0的出现)都引起大量理论烦恼。

公理化的一个结果是,我们现在可以递归的定义序列。定义 a[0],然后定义一系列从 a[i] 到 a[i+1] 的函数 f[i]。

6 递归的定义

(我知道这很重要,但是我不懂这一段,于是我不知道这很重要 XD)
给出第一个数 a[0],给出某种函数f[n],a[n++] = fn(a[n]),其中 f[n] 是某个从 N 到 N 的函数。使用所有的公理,我们现在可以断定这个过程对每个自然数给出序列元素 a[n] 一个单一的值。

递归定义:设对于每个自然数n,都有某个函数 fn: N -> N 把自然数映成自然数。设 c 是一个自然数,那么可以对每个自然数 n 指定唯一一个自然数 a[n] 使得 a[0] = c 且 a[n++] = fn(a[n])。

注意,通过使用 c 和 自然数列,得到的 a[n] 数列中每个元素都被定义了一次而且仅有一次。

7

到这里为止,简单的回顾了数学分析中皮亚诺公理定义的自然数。

我们可以注意到,“初始元素”(比如第一个自然数),“函数”(比如从1到2的增加动作),“模板”(比如公理5),“递归” 的概念都出现了。

这些概念在计算机编程语言里也出现。(但却有不一样的含义)

注:从最早的生活中的计数得到的自然数,可以进一步定义整数为自然数的差,比例数(有理数)为整数的商(约定不允许除以0,因为如果允许,则可以从四则运算和方程很快推出矛盾,而四则运算和方程是我们每天都要用的,不好抛弃),有了比例数之后,已经可以做大量的数学事项。高中数学代数的大部分事情都可以做的很好。但是,当人们开始处理几何学的子领域,三角学的时候,圆周率 PI,cos(1),根号二这些数都不是比例数。为了要有一个数系适用于刻画几何学,或者简单的适用于测量直线上的长度,我们需要实数系,进一步的,因为要关心切线的斜率或者曲线下的面积——微积分学也需要实数系才能充分发挥功能。

因为比例数无法直接运算表示出实数,所以想用一系列的比例数去接近并最终定义实数,这就是(数列)极限的作用(之一)。

注:自然数集符号,大写的 N 指 natural “自然的”。Quotient “比例的”。Real “真实的”。Zahlen 德文 “数”。Complex “复数”。

注:“这就有点像某个计算机语言的基本数据类型要是不完全的话,用的时候就不得不搞一些技巧(来表示那些本来不好表示的值或者概念)。你会希望语言‘原生就支持’某种数类型,而且会希望允许你自己扩展类型。”

8 真的没问题吗?公理系统

皮亚诺公理定义了自然数,只从这5个非常原始的公理和集合论中的某些附加的公理出发,就能建立起所有的其它数系(整数,实数,复数),创造函数,并做我们通常做的全部代数和微积分。

全部代数和微积分里有着大量的定理,你怎么能知道从这几个公理开始推出它们,不会产生矛盾或者错误?

(呃,真的产生过让人头痛的悖论,比如 1901 年的罗素悖论“所有不包含自己的集合是否构成一个集合”,这是在质疑集合论有问题。在当时,已经有数学家把自然数建立在集合论与逻辑之上,所以集合论与逻辑在当时可以支撑整个数学大厦,是为根基,罗素悖论使得人们觉得这个根基有问题,这是第三次数学危机。每次危机总伴随着机会,新的问题被意识到,并且被处理。)

这个问题在数理逻辑里被研究。

“传统上,逻辑被作为哲学的一个分支来研究,和文法修辞一同被称为古典三学科。自十九世纪中叶,“形式逻辑”已被作为数学基础而被研究,当中经常被称之为符号逻辑。1903年,阿弗烈·诺夫·怀海德伯特兰·罗素写成了《Principia Mathematica》,试图将逻辑形式地建立成数学的基石。不过,除了些基本的以外,当时的系统已不再被使用,大部分都被集合论所取代掉了。当对形式逻辑的研究渐渐地扩张了之后,研究也不再只局限于基础的议题,之后的各个数学领域被合称为数理逻辑。形式逻辑的发展和其在电脑上的应用是计算机科学的基础。—— 维基百科:逻辑 ”

数学上,一个公理系统(或称公理化系统,公理体系,公理化体系)是一个公理的集合,从中一些或全部公理可以一并用来逻辑地导出定理。一个数学理论由一个公理系统和所有它导出的定理组成。一个完整描述出来的公理系统是形式系统的一个特例;但是通常完全形式化的努力仅带来在确定性上递减的收益,并让人更加难以阅读。所以,公理系统的讨论通常只是半形式化的。

1920 年,德国数学家 大卫,希尔伯特提出希尔伯特计划,主要目标,是为全部的数学提供一个安全的理论基础。

这个全部的数学的基础应该包括:

  • 所有数学的形式化。意思是,所有数学应该用一种统一的严格形式化的语言,并且按照一套严格的规则来使用。
  • 完备性。我们必须证明以下命题:在形式化之后,数学里所有的真命题都可以被证明(根据上述规则)。
  • 相容性。我们必须证明:运用这一套形式化和它的规则,不可能推导出矛盾。
  • 保守性。我们需要证明:如果某个关于“实际物”的结论用到了“假想物”(如不可数集合)来证明,那么不用“假想物”的话我们依然可以证明同样的结论。
  • 确定性。应该有一个算法,来确定每一个形式化的命题是真命题还是假命题。

然后,1931年,这个计划失败了。

失败了。
失败了。
失败了。

因为奥地利人 库尔特·哥德尔 证明了 哥德尔不完备定理:

任何相容的形式系統,只要蕴涵皮亚诺算术公理,就可以在其中构造在体系中不能被证明的真命题,因此通过推演不能得到所有真命题(即体系是不完备的)。

任何相容的形式系統,只要蕴涵皮亚诺算术公理,它就不能用于证明它本身的相容性。

“最近两个世纪以来,公理方法的研究越来越有力和充满生机。对数学的新老分枝,包括对熟悉的基数(或“非负整 数”)性质的研究,都提供了一组看上去是适当的公理。 当时的舆论普遍认为,数学思想的每一分枝都能找到一组公理,从其出发就足以系统地推导出在此研究领域中无穷无尽的所有真命题。

哥德尔的论文证明这种假定是站不往脚的。他向数学家们宣布了使人吃惊而又沮丧的结论,即公理方法具有固有的局限性, 即使是非负整数的性质也不可能全部被公理化。”  —— 《哥德尔证明

另:对哥德尔证明的理解,还可以参考 BYVoid 的这篇文章:https://www.byvoid.com/blog/godel-incompleteness-theorems-agnosticism,节选一段如下:
“ 關於它的證明和詳細解釋,我强烈推薦一片文章「康托尔、哥德尔、图灵——永恒的金色对角线」。這個定理有不少誤解,例如:並不是所有的系統都是不完備的,哥德爾不完備性定理的前提是要求它能定義自然數和算術系統,像一階謂詞公理系統、歐氏幾何公理系統都是完備的。還有非形式化的系統也不在這個定理的約束範圍之内,例如經驗、實測。 ”

9 什么是计算?

我们想一想,会发现关于计算的知识大致有两种,声明式的和指令式的。

声明式的:(对 事实 / 定义 的陈述)

25 的平方根是 5.

x 是 y 的平方根,当且仅当 y = x * x。(定义式的。有趣的是,这没有告诉你如何得到结果,但是告诉了你如何验证结果是否正确)

指令式的:

要想求出一个符合IEEE 754标准格式的32位浮点数 x 的平方根(近似)的话,你应该这么做:将其向右进行一次逻辑移位的方式将之取半,并用十六进制“魔术数字”0x5f3759df减之,如此即可得对输入的浮点数的平方根倒数的首次近似值;而后重新将其作为浮点数,以牛顿法反复迭代,以求出更精确的近似值,直至求出符合精确度要求的近似值。

或者你也可以从任意值 g 开始猜,然后如果不够精确,就用 (g + x/g)/2 作为新的近似值 g,因为 g 和 x/g 一个大于确切的平方根,另外一个小于,平均值会接近平方根。(古埃及)

10 哪些东西可以计算?

知道算法,但是人工很难算的东西,就想用机器来算。但是真的算的出来吗?

实际上,哪些东西从根本上其实是算不出来的?哪些东西是因为机器不够快,所以在有限的时间内算不出来的?是否所有的问题都落在这两个分类当中?

从1930 年开始,可计算性理论,或者叫递归理论,起源于对可计算函数以及图灵度(又叫不可解度)的研究,主要考虑下面两个问题:以自然数为基础的函数,“可以计算”到底是什么含义?那些算不出来的函数,按照它们的计算难度,可以分成哪些类?

这既是数理逻辑的分支,也是计算机科学的分支。这个叫做 Theory of Computing (计算理论)的领域里出现了有许多有趣的概念,比如自动机。

1940 到 1950 年代,某些比较简单的机器(今天叫“有限自动机”)被某些人研究。原本用于模拟人脑思考模型,结果发现在其它一些用途上也非常有用。

1950 年代,语言学家 N.Chomsky(乔姆斯基)开始研究形式“语法”。语法虽然不是机器,但是和抽象自动机非常有关系,为今天某些相对重要的软件(比如编译器)的基础做出了贡献。

1960 年代,S. Cook 扩展了图灵对“哪些可以计算,哪些不能计算”的研究 。Cook 区分了“当时可以用机器很快算出的问题”,和 “理论上能用机器算,但是在当时太慢以至于实际上没法算出来的问题”,后者叫做“难解问题”或“NP-hard”。即使当时集成电路技术的进步带来的计算能力的指数增长(“摩尔定律”),也无法有效的改变难解问题难解的事实。

自动机和某些种形式语言的概念,今天被用于设计和建造重要的软件。其它的概念比如图灵机,让我们理解,可以期望从计算机得到什么(机器能力的极限)。我们遇到一个问题,是否可以马上写个程序来解决(当问题不属于难解问题),还是不得不采取一些曲折手段(比如放宽问题求解精度,使用启发式算法等)来缩减问题求解需要的时间。

——《Introduction to Automata Theory, Languages, and Computation》, Hopcroft

11 图灵机是计算(机)模型的一种

在精确定义“可计算函数”之前,数学家常用“可以有效计算”来指可以用纸和笔方法算出来的函数。为了回答“哪些问题可以计算”,就自然会希望先定义“什么是计算”。(这一时期还有“是否可判定”的问题也被考虑。)1930年代,有若干著名的努力,想要形式化的描述“可计算性”。

  • 1933年,哥德尔(就是不完备性定理那个)和 雅克·埃尔布朗,创建了 general recursive functions (广义递归函数)的形式化定义。这类函数包含所有的常数函数,映射(?),以及后继函数(皮亚诺公理里的后继动作),以及由它们复合和递归的函数。
  • 1936年,阿隆佐·邱奇 创建了一个方法来定义函数,此方法叫做 λ-calculus(lambda 计算)。把自然数编码为邱奇数,然后一个自然数上的函数是可计算的,当且仅当在邱奇数上的对应函数可以被lambda 计算中一个“项”(项可以是变量 / 函数 / 函数的应用)表示。
  • 1936年,在了解邱奇的工作前,图灵创建了理论上的机器模型,现在叫做图灵机。可以通过操作一条纸带上的符号进行计算。只要把自然数适当的编码为符号的序列,一个自然数上的函数是可计算的,如果图灵机可以在对应的符号上就算出结果。

其中的图灵机是这样一种假象的数学的计算机器模型:它有一条无限长的纸带,有一组可以用户定义的规则,纸带分为一个一个的格子,图灵机可以读取格子,根据规则,左或右移动到任意格子,然后写入一个符号,总的符号个数也是有限的。

图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程,他把这样的过程看作下列两种简单的动作:

  1. 在纸上写上或擦除某个符号;

  2. 把注意力从纸的一个位置移动到另一个位置;

而在每个阶段,人要决定下一步的动作,依赖于(a)此人当前所关注的纸上某个位置的符号和(b)此人当前思维的状态。

可计算性理论中,Church–Turing thesis(丘奇 – 图灵论文,或者 丘奇 – 图灵猜想) 是关于可计算函数的一个假设。它说,建立在自然数上的一个函数,可以被拥有无限资源的人计算出来,当且仅当它可以被图灵机计算出来。强调的是这两种情况的等价性。

邱奇是图灵的老师,邱奇和图灵证明了,这三种形式化的定义,其实是一致的。

(实际上,图灵不仅让我们知道图灵机这个模型可以做计算,还说明了在他的图灵机模型以外,还存在其它的机器模型,它们也是可以做图灵机能做的所有计算的。)

这个证明使得数学和计算机科学家倾向于相信,“可计算性”这个概念,被这三种相等的过程成功的抓住了。后来还有其它形式化的尝试,加强了这个看法。

另外一方面,邱奇和图灵证明了,这三种形式化的定义,与非形式化的“可有效计算”的定义一致。因此,可有效计算没有一个形式化的定义,虽然它被非常广泛的接受,但是无法形式化的证明。

接下来还有许多工作不是邱奇和图灵所做的,但也命名到这类问题下。包括在我们的物理宇宙中,哪些东西计算机可以做到(物理邱奇-图灵论文);还有哪些东西可以快速的计算(复杂性邱奇-图灵论文)。

图灵后来因为同性恋倾向被定猥亵罪,传说吃了含氰化物的苹果而死。有人曾经问乔布斯:苹果电脑标志上面缺了一口的苹果,是为了向图灵致敬而设计的吗?乔布斯答:不是——但是我的老天,我真希望是。

注:实际上直到今天仍然有人表示疑问为什么流行开来的是图灵机模型,而不是数学家常感觉更加简洁的  λ-calculus 。有人认为 ,是因为图灵机模型在当时更容易让人相信这样的机器可以实际制造出来。而其它的模型则看上去不那么明显。

图灵机有很多变种,但可以证明这些变种的计算能力都是等价的,即它们识别同样的语言类。证明两个计算模型  A和  B的计算能力等价的基本思想是:用 A 和 B 相互模拟,若 A可模拟 B且 B 可模拟 A,显然他们的计算能力等价。(暂时不考虑计算的效率,只考虑计算的理论上“可行性”。)

“机器能思考吗?” 这就是 1950 年,图灵那篇著名的论文《计算机械与智力》开篇提出的问题。 论文里还提出了著名的 “图灵测试”的想法,即如果机器能模拟人并骗过人的判断,就近似证明了机器可以思考。

12 造出计算机

既然已经近似证明,图灵机可以做计算。那么只要能实作(实际造出来),这个机器就可以用来计算。(在这之前,人们早就造过各种各样的机械来做计算,比如莱布尼茨时期的机械式计算机,算盘,算筹之类,应该还有更早的。)

1941 年 Atanasoff 和 Berry 造了固定指令的机器,解方程组,用来计算炮兵用弹道。它大致上没有被当成最早的计算机,因为指令是固定的,不够灵活。

如何灵活一些,让同一个机器可以算不同的算法?

回头看看指令式的算法,它有两个部分:输入的数据,计算步骤的一条条指令。都需要存储起来,这个意义上它们是一样的。

好,制造可以随时修改的存储器来存储它们。同时让机器自己也可以修改存储器内容。

这样机器就变得无限灵活:可以修改指令,程序可以产生程序。

这就是今天计算机的雏形:存储器 + 负责做计算的部分。

1946 的 ENIAC 在美军要求下,由宾夕法尼亚大学设计。函数表,平方根计算器,程序,乘法器,读写器,加法器由不同的人设计。17,468 个真空管,500万个手工焊点(怎么数出来的?)。输入输出是 IBM 的打孔卡片。

13

今天的计算机还是以这些东西为核心。

加法和乘法被做成了高速的电路。存储器被做成了缓存,内存,硬盘。最高层的快,容量小,最下层的慢,容量大。

计算机的外存类似纸张,程序类似写在纸上的文字,计算机的内存类似人脑的临时记忆,计算机的芯片类似人脑的逻辑思考能力。

计算机的各个部件受OS操作系统管理,OS把外存上的记录,加载进内存,以程序算法对其描述的问题进行”思考”(演算)。
人则是通过五官把世界加载进自己的脑子和身体,用逻辑和非逻辑的方法对问题进行思考。

用程序语言和数学语言不太一样,程序语言被计算机演算,数学语言被人脑思考。越贴近机器的编程语言,比如 C / 汇编,越接近机器的运作方式,越远离机器的编程语言,比如 Javascript / Lisp 越接近各自时期的数学语言。

一个计算机程序,大致是 3个 部分(关注点在机器):

  • 指令集(机器能做的基本计算动作,比如加法或乘法。人类很早就能做的部分。)
  • 流控制(对基本动作的控制,做计算的先后次序,逻辑跳转等)
  • 如何结合以上两者

还有另一种划分方法:一个计算机程序,大致分为 2 个部分(关注点在计算):

  1. 算法(即具体怎么算?)
  2. 数据结构 (计算的输入 / 中间步骤 / 结果 … 这些东西 记录成什么样子?)

写程序用的编程语言,有支持/反对你考虑/使用上面这些部分的。

另外一篇相关:http://mindhacks.cn/2006/10/15/cantor-godel-turing-an-eternal-golden-diagonal/  

MIT 对此话题 https://ocw.mit.edu/high-school/humanities-and-social-sciences/godel-escher-bach/

19世纪末期,logic, psychology and linguistics 还未分领域,直到 https://plato.stanford.edu/entries/montague-semantics/

歌德尔的证明流程相关 :http://pan.baidu.com/s/1dFJoHg9

哥德尔证明相关:Douglas Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979.

计算理论,形式语言,自动机部分相关 Introduction to Automata Theory, Languages, and Computation, Hopcroft, Motwani, Ullman, 3ed

别人讲的相关故事《函数式编程的早期历史》https://zhuanlan.zhihu.com/p/24648375

公理化和数学危机相关 《第三次数学危机》https://pan.baidu.com/s/1hsqiJDq

相反的,对称的意见 https://www.douban.com/group/topic/18540318/ Michael Atiyah:二十世纪的数学

相关 https://en.wikipedia.org/wiki/Timeline_of_computing

相关 《古今数学思想》

update:相关  https://textbooks.opensuny.org/how-we-got-from-there-to-here-a-story-of-real-analysis/ ,作者的一个观点是:要到达一个数学子领域,历史上有许多殊途同归的路径。

相关《数学:确定性的丧失》

另,《陶哲轩实分析》附录A 的数理逻辑简介蛮好。

Advertisements