理论教育 哥德尔证明数理逻辑不完备,图灵构造通用计算模型

哥德尔证明数理逻辑不完备,图灵构造通用计算模型

时间:2023-10-22 理论教育 版权反馈
【摘要】:哥德尔通过对所有可能的人工语言单位和形式证明编码证明了形式系统的不完备性;图灵则对所有可能的计算过程编码,从而构造了通用计算模型,并证明存在可以描述却不可计算的问题。对于逻辑学家来说最关注的是与定义复杂度密切相关的可计算性和无法被简单归约到前者的随机性。

哥德尔证明数理逻辑不完备,图灵构造通用计算模型

确实,所有已知的事物都拥有数(have number),因为,任何事物无论如何都不可能在没有数的情况下被理解或认识到。

——菲洛劳斯(Huffman,1993,p.172)

菲洛劳斯(Philolaus of Croton)[1]的断言从未像今天这样令人无以辩驳。虚拟现实(VR)技术的进步让人们相信,人类通过感官知觉所能获得的全部经验材料都能被数字化。通过编码,人们甚至可以用0和1两个符号来书写人类已有的全部知识。如果物理宇宙是有穷的话,就可以用一个自然数编码整个宇宙的全部信息,无论是马里亚纳海沟底部那只单细胞有孔虫(Xenophyophores)的DNA序列,还是129亿光年外类星体ULAS J1120+0641的整个生命周期。对虔诚的自然主义者来说,那一个自然数就是人类全部智力活动的绝对上限。

计算机和互联网产业在今天取得的成功的确让人们感受到数字化的力量。实际上,早在20世纪30年代,哥德尔和图灵的数字化工作就已经预言了今天的图景。哥德尔通过对所有可能的人工语言单位和形式证明编码证明了形式系统的不完备性;图灵则对所有可能的计算过程编码,从而构造了通用计算模型,并证明存在可以描述却不可计算的问题。编码实质上是一种翻译。工程师通过编码,将各种信息翻译为数字语言,从而可以在通用数字计算机上统一处理。而理论工作者关心的是可以应用于任意复杂对象的抽象概念或性质。给定一套编码,可以将论域中的个体对应于一个个自然数,也同时将概念或性质对应为自然数集。这样做的好处是可以更方便地使用自然数上的归纳法来证明关于所有可能个体的全称命题,从而在无法经验地遍历所有个体的情况下就给出概念与概念之间的关系的证明,正如哥德尔和图灵的工作所显示的那样。(www.daowen.com)

数字化的另一个意义是让人们可以用精确的数学语言来谈论“个体与概念”或“概念与概念”这样抽象的哲学论题。个体与概念或抽象与具体之间的界线一直是具有争议的问题。[2]在数字化的语境下,我们可以抽象地将个体等同于自然数,而将关于个体的概念或性质等同于自然数集。与更抽象地模拟概念系统并允许概念不断自我迭代的集合论不同,作为数理逻辑另一个方向的递归论主要关注自然数集的性质,在这里具体与抽象有简单明了的区分(即自然数与自然数集)。例如,我们可以清晰地谈论,何以有时候一些作为概念的自然数集也能被看作具体的:有些自然数集可以通过具体的程序来生成,而每个程序都可以被编码为自然数,因此就可以通过对自然数的枚举来表示对这些自然数集的枚举。

将各种概念抽象为自然数集后当然会丢失很多关于这些概念的属性。不同却等价的编码方式也可以让一个概念对应于不同的自然数集,从而抽象掉它们之间的区别。例如,我们可以把所有计算机程序一一地编码为所有奇数,也可以编码为所有偶数。在一些情况下,奇数集和偶数集似乎并没有什么不同。忽略掉一些区别可以让人更专注于保留下来的其他属性。对于逻辑学家来说最关注的是与定义复杂度密切相关的可计算性和无法被简单归约到前者的随机性。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈