中國農業歷史與文化

    当前位置:主页 > 农家者流 >

    当前栏目:农家者流

    请问人工智能还是图灵机吗再问量子计算机还是图灵机吗

    2019-12-31 14:43:20

    1。图灵机是个数学模型,它是定义了什么是算法(或者机械步骤);事实上“算法”这个概念,一直以来缺乏严格的数学定义,图灵机的出现,就给了算法一个定义。当然,在图灵机之前,大家还尝试过很多其他对算法的定义,比如递归函数,Lambda演算,Post机,细胞自动机(GameofLife)等。但后来证明这些模型统统都和图灵机等价,因此他们定义了同一个算法的概念(PS:我还写过一篇论文证明了算盘和图灵机也等价)。于是人们提出了所谓的Church-TuringThesis:即所有人类直觉上能行可计算(effectivelycomputable)的函数类,等价于图灵机可计算函数类。但这始终是一个thesis,没办法证明,因为讲不清什么是“effectivelycomputable”。2。试图超越图灵机的模型也有人搞过,但大部分都失败了。有些看上去好像成果了,比如所谓的Hypercomputation(具体可参见wikipedia词条),但仔细分析一下发现都有漏洞:要么是需要无穷的计算资源(比如时间、空间、能量、物质等),要么是假设时间空间是连续的(但现代物理告诉我们时间空间其实是离散的),要么是理论上可行实际上不存在的,所以都然并卵。话说有段时间我也搞出N个试图超越turingmachine的模型,可惜都以失败告终。3。量子计算机,其理论模型依然没有超越图灵机。1985年Deutsch就提出了量子图灵机模型,事实上是概率图灵机的变种,还是和经典图灵机等价(是指计算能力相等,但是计算效率并不等价)。后来1993年姚期智证明了量子图灵机和量子电路等价,得到了两者之间在计算复杂性上和经典情况类似的结论。4。事实上,任何有限输入、有限输出、有限规则可定义的计算模型,都无法超越图灵机。图灵机的极限,就在于有限和无限之间。5。至于机器学习,人工智能,他们只是某类特殊的算法,或者说只是一大类运行在图灵机上的程序罢了。谈不上什么超越图灵机,根本没有可比性。6。刚才提到过,图灵机的极限其实在于有限的输入、有限的输出、有限的控制规则。如果涉及到无限,问题就变的图灵不可计算了,比如停机问题。利用这个思路,很容易证明存在图灵不可计算函数:由于图灵机的规则总是有限的,所以任何一台图灵机可看作是其规则的一个有限长度串(一段程序),这样的有限字符集中的有限长度字符串的集合的大小和自然数集合相同(其秩是aleph_0);而所有输入为自然数输出也为自然数的函数(称为数论函数)的集合的大小和实数集合大小相同(其秩是aleph_1),所以必然有这样的一个函数不存在任何图灵机可以计算它,否则图灵机集合和数论函数集合大小相同;但我们知道自然数集合和实数集合大小是不同的(康托对角线删除法),矛盾。事实上,图灵停机问题不可计算的证明,用到的也是康托对角线删除法。7。因此,图灵机的极限就在于其输入、输出、规则的有限性。如果允许图灵机可以有无限的输入,以及无限的输出,那么问题就变的有趣了:是否可以通过这种方式超越图灵机?注意到无限的规则是不可能的,否则我们也没办法描述这个东西。8。在我看来,机器学习其实可以看作是某种有无限输入(训练数据)和无限输出的图灵机,理论上这样的图灵机是否可以超越经典图灵机?但这个问题不是这么简单,因为机器学习的过程中是允许出错的,这个出错概率如何定义,如何保证最终出错概率可以收敛有界,这都是需要仔细考虑的问题。这个问题我已经考虑了挺久的了,目前还没有太好的结论。当然,这并不表明现有的机器学习、人工神经网络之类的可以超越图灵机,因为它们实际上还是有限输入有限输出有限规则的算法。9。另一个有趣的问题是,如果把大自然看作一个计算机,任何物理系统都可以用来做计算:只需要把问题的输入编码到系统的初态,让系统按照物理规律做自然演化,然后把系统的末态解码为计算的输出结果。从这个角度看,任何物理系统的演化都是一个计算过程。10。事实上物理系统作为计算过程的思想早已有之,比如我们知道电容的充电放电函数是个积分函数,早起的模拟电路中,就使用电容来做积分器计算积分。现在的电子计算机,本质上也是个物理系统,我们在键盘上的输入,最终都转化为电信号输入系统让系统进行演化,系统演化的结果,再转换为电信号输出到屏幕上……所以电子计算机也没有脱出这个范畴。11。那么,一个有趣的问题就是,按照现在的物理学理论,物理系统是否有超越图灵机的计算能力?这个问题我也仔细调研过,答案是有的。理论上,任何物理系统都可以用系统的哈密顿量描述,而哈密顿量是个酉矩阵,其集合的秩是aleph_1,和实数集合等势,这就已经超越所有图灵机的集合大小了,所以一定存在超越图灵机的物理系统。事实上,上个世纪五十年代,有个苏联数学家就构造出一个波动方程,该方程本身可计算,但其导函数处处不可计算。这说明理论上我们可以构造出一个物理系统,让其演化出的结果可以计算一个图灵机不可计算函数。12。当然,除了关注物理系统和图灵机的可计算性之间的比较,更有意义的其实是关注其计算效率之间的比较,即计算复杂度的问题。关于这个问题,目前已经证明量子图灵机在某些特定问题上(主要是一类带oracle问题)远比经典图灵机更高效,甚至达到指数级加速。但目前缺乏足够证据证明其在非oracle的实际问题上也能达到指数级加速。但已经证明的是,对于任意无结构搜索问题,量子图灵机比经典图灵机至少可以有平方级加速(即经典的需要O(N)次运算,量子则只需要O(sqrt(N))次运算),具体可参见著名的Grover搜索算法。13。最后补充一下:所谓的量子图灵机是利用整个宇宙做计算,这是基于量子力学的多宇宙解释的一个推论。如果多宇宙解释是正确的,量子图灵机做计算的过程,其实是随机“猜”结果;当然运气不好就猜错了,但是运气足够好你会发现它猜对了,这只是因为你恰好处于它猜对结果所处的那个平行宇宙分支之中;在其他的平行宇宙,你的运气不好它没有猜对结果。当然,多宇宙的解释我是不太赞同的,我认为宇宙不该这么复杂。

    上一篇:如果存在电子游戏行业的下一次雅达利冲击最可能以什么为导火索
    下一篇:青岛科技大学与济南大学哪个好呀

联系信箱

Copyright © 2013中国科学院自然科学史研究所 All Rights Reserved

地址:北京市海淀区中关村东路55号 邮编:100190京ICP备05046608号
网站地图