lvchenjun的个人博客分享 http://blog.sciencenet.cn/u/lvchenjun

博文

数学猜想:超穷数和计算复杂性

已有 755 次阅读 2019-6-24 07:04 |系统分类:科研笔记

还是从图灵的博士论文谈起。1936年图灵给出机械计算的严格定义后,就开始思考机器如何突破哥德尔不完备性定理的问题。从1936年到1938年,图灵来到普林斯顿,在丘奇的指导下,完成了博士论文《以序数为基础的逻辑系统》,他提出了一个简洁的解决方案:任何一个数学公式A都可以表示成一串数字符号,这串数字符号的长度可以用一个序数α来表示,对应的,A就可以用逻辑系统L_α来判定;利用康托的超穷序数,可以形成不断递增的序数ω,2ω,等等,相应的,就有不断递增的逻辑系统L_ω,L_2ω,等等,后一个系统都比前一个系统更完备,即可判定的数学公式更多。图灵证明了:如果公式A在L_ω中不可判定,那么总可以构造一个更完备的逻辑系统L_2ω,来判定它。这种证明思想是非常直观的,对机器认识论也具有很大的启发性。

 

在计算机中,一个信息都可以表示成一个数字符号0或1的长串,这就是一个编码,其长度可以用一个超穷序数α来表示,α就表示这个信息的复杂度。显然,越复杂的信息,其编码的长度α就越大。这里,我们先要讲清楚两个问题:

 

第一,          实数集和复数集都比自然数集的长度要大,也就是复杂度更大,所以,如果要计算定义在这些集合上的函数复杂度时,当然就需要用到比自然数集的长度ω更大的超穷序数α,这是自然的;

 

第二,          任何计算机只能处理有穷数,也就是说,它不可能真的有一条无穷长的带子,所以,我们必须还要把一个超穷序数α处理成一个自然数n的迭代函数,这样它才可以真的用于计算。

 

 

所以,我们提出一个数学猜想:可以用超穷序数来表示一个数学公式的计算复杂性,这个超穷序数还能表示成一个可计算的自然数迭代函数。这样一来,就等于是建立了一个通用学习机的超穷数模型。

 

按照康托的超穷数理论,超穷序数的增长有两种方式,一种是序数增加但基数不变,譬如序数从ω^2增长到ω^3,它是按基数ω的指数ω^n来增长的,我们就称之为“指数复杂性”,这种情况,集合的元素数目是不变的,迭代函数都在同一个集合ω中取值;另一种是序数增加、基数也增加,譬如序数从ω_1增长到ω_2,这种情况,集合的元素数目也在增加,也就是说,迭代函数在集合ω_1中取值就变成了在集合ω_2中取值,但可以规定:

 

u∈ω_i g(u) =: ∀u_1,u_2, …, u_i∈ω g^i(u_1,u_2, …, u_i,u_i+1),i≥1

 

也就是说,我们可以把一个在集合ω_i中取值的单元函数g,等价转换成一个在集合ω中取值的i维空间函数g^i,所以,如果在集合ω_1中取值,就相当于一个二维空间<(x,y)|x,y∈ω>,在ω_2中取值,就相当于一个三维空间<(x,y,z)|x,y,z∈ω>,它是按维数来增长的,我们就称之为“维数复杂性”。

 

所以,计算复杂性可分为“指数复杂性”和“维数复杂性”两种类型,这对我们理解机器的内部结构是关键性的概念。一个计算系统的复杂性按照指数和维数来递增,都可以形成分层结构,但这两者的计算行为是不一样的,我们来做一个简单的描述:

 

在指数复杂性的计算系统中,其上下层存储状态集的基数是相等的,所以,它的反向传播也是确定性的,只要一步一步去搜寻,必然就会找到匹配的结果。我们打个比方来说,譬如一个密码系统,如果密码的编号就在系统的存储集中,我们只要一步一步去搜寻,总能找到匹配的结果。像AlphaGo就是这样的计算系统,机器总能找到最优的算法,这其实就是线性的概率分布空间。我们猜想:在指数复杂性的计算系统中,“N⁄NP问题”是成立的。因为,我们最后总能找到密码,也就是说,机器总能写出一个正确的程序。

 

但在维数复杂性的计算系统中,其上下层存储状态集的基数是不相等的,所以,它的反向传播也是不确定性的,我们一步一步去搜寻,最后不一定能找到匹配的结果。譬如,一个密码系统,如果密码的编号不在系统的存储集中,一步一步去搜寻,最后也不一定就能找到匹配的结果。此时,其反向传播就是高维空间向低维空间的投影映射,这就是非线性的概率分布空间。我们猜想:在维数复杂性的计算系统中,“N⁄NP问题”是不成立的。因为,我们最后不一定能找到密码,也就是说,机器不一定能写出一个正确的程序。

 

这就是我们对计算复杂性的两种直觉思考,当然它还需要做进一步的严格数学定义。两种计算复杂性,其实也就是两种不同的计算行为。图灵机可以处理指数复杂性问题,但维数复杂性就不行了,我们必须去探索新的计算模式。通用学习机也好,GAI也好,都需要突破图灵机,这就是关键之所在。对计算的理解,对数学基础的理解,现在人们的思考已远远超越了图灵和哥德尔的时代,新世纪的数学曙光业已照耀在地平线之上。




http://blog.sciencenet.cn/blog-3282433-1186538.html

上一篇:关于连续统假设的否定性证明(修订稿)
下一篇:两种科普的概念:刍议新时代的科学精神

1 王安良

该博文允许注册用户评论 请点击登录 评论 (5 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2020-1-26 06:37

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部