您好、欢迎来到现金彩票网!
当前位置:2019年正版全年资料 > 通用图灵机 >

量子计算机能够模拟人脑吗?

发布时间:2019-06-16 13:51 来源:未知 编辑:admin

  =====================================================

  关于“模拟”一词的定义,个人认为是指等价关系。也就是说人脑能做的事情量子计算机也能做到。人脑无法完成的事情,量子计算机无所谓能否做到。如果模拟单指量子计算机逼近人脑所做的事情,似乎意义不大。任何机器都可以在某种程度上完成这项任务。所以,基于这样的理解,题目就等价于“量子计算机是否可以实现真正的AI”,也就是说量子计算机是否可以等价或超越人脑。

  关于形式语言是自然语言的真子集,@费阿牛。虽然个人认为这是想当然正确的,但既然有人提出那就待我探清虚实之后再做更新。乔姆斯基应该做过陈述,当然这个陈述也很有可能是无法证明的。因为本身自然语言是无法良定义的。

  2. 自然语言随着时间的推移会产生新的合法语句。(例如20年前人不知道google,10年前不 知道tweet)

  假设任何的自然语言都可以被形式化,那么随着时间的推移,总会有的合法语句加入自然语 言。新加入的语句不会由现有语法生成,(如果可以被生成就是已经合法语句,而不需要再加 入了),并且这样的语句数量无限(阿列夫0)。既然新语句于现有语法独立(类似于一条真 的陈述于现有公理系统相互独立),而且若要被包含于形式语言,那只能将其加入字母表或者 语法集(这一过程类似于第一不完备定理)。但这和上述形式语言的定义矛盾。于是得证自然 语言无法被形式化。

  关于停机问题不可解,是指无法构建一个通用机,用于判定任意图灵机是否可以停机。人类虽然不一定能判定任意图灵机是否可以停机,但人类可以做出此问题不可解的证明。如果有人说这个证明可以用形式语言表达,所以可以构建一个图灵机来证明停机问题不可解。这么做当然是可以,但构建的这个图灵机不是一个通用机,或者说是一个可以对任意良定义问题做出判定的通用机。再或者说,假如某为解决的问题,比如哥德巴赫猜想,没人知道是否真假,也没人知道是否可以证明,那么能否构建一台机器,判定猜想是否可以证明?人脑或许在某一天可以得到答案,但在此之前无法构建这样的机器。因为数论是不可被公理化的系统。详见哥德尔不完备定理。

  其实不完备定理和停机问题不可解是一样的,证明也非常相似。所以可以从这个角度理解,可以定义自然数的形式系统无法被归约,同理任意的形式语言也是无法被归约的,自然语言因此也无法被归约(形式语言是否是自然语言的真子集由前文所述,待确认。但“不弱于”,可以得到一致的认同吧)。而图灵机自身可以归约成有限的规则集合,因此可以理解图灵机的局限性。归约性可以参考 《an introduction to kolmogorov complexity》和《a new kind of science》。

  最后说点整体论和简化论的观点,个人是整体论,也就是说认为很多事情都是无法被归约的。虽然也很希望能够有一条解释万物的方程,这个方程可以是物理中的一个有限定律集合,可以是数学中的一个有限定理集合,可以是计算机中的一个通用算法。但可惜数学和计算机都无法实现这个愿望,数学参见哥德尔是如何破灭希尔伯特计划。当然,或许是我想错了,下面有朋友评论说这是信仰不同。嗯,求同存异欢迎各种讨论。下面的评论我会尽量回复。

  =============================================================================

  关于量子计算的一切 可以参照《an introduction to quantum computing》写的很详细,语言很平实。中文相关的书没见过一本,当年把整个深圳图书馆翻遍了都没看到有一本能看的书,甚至连基本的bra-ket notation都不给出清晰的定义。

  在邱奇-图灵假说成立的情况下,任何计算能力不超越图灵机的计算模型都无法实现一个真正的AI。

  证明思想很简单,如果邱奇图灵假说成立,那么任何的可计算方程都和图灵机等价。而人脑不可计算,所以不属于可计算方程,所以用图灵机无法模拟。而量子图灵机(简称量子机)和经典图灵机(简称经典机)计算性等价,所以量子机无法模拟大脑。

  这个假说很合理,因为任意的计算过程,都是遵循了一个有限的步骤集合,而这个步骤集合可以作为transition table(后面有定义)。甚至是,人类理性思维的极限。题外话……

  如果有人说更强的计算模型?有很多,参照hyper computation,例如zeno machine,芝诺机。但都实现不了。

  哦 这里说的模拟是指,造出一台机器和人脑一样,对于给定任何相同的输入,会有相同的结果。或者说绝大多数相同输入有相同结果。而并不只是,建立一个类似神经网络的东西,也不是对于所有人能做的所有事情统计,得出一个字典,对于任意输入查字典给出输出。如果是神经网络,那么是没有transition table,机器毫无意义。如果是字典,(按我理解大数据就这么做的,理解错了别拍)参见GEB作者侯世达在受采访时的批判。

  模型。从物理的角度讲没有基础的人应该容易理解。模型很简单,一条无限长的纸带,分成了无限多个小格。每个小格可以存储0或者1两种字符。{0,1}也就是此编码的字母表。(其实不是0 1也无所谓,只要是字母表是有限,那么统统都是多项式等价)。机器还有一个可以左右移动的读写头,每次可以读出读写头所在位置的字符,也可以改写。读写头有一个有限长度的寄存器(只读 不可改写),里面存储了有限个数的移动、读取和改写的规则。例如“如果当前小格内存储了0,向左移动一格。” 这个有限个数的规则,称之为transition table。其中有一个特殊的规则,是开机,一个特殊的规则是关机。开机很简单,不解释。关机例如“如果当前小格存储1,那么输出“接受”并且停机。”,当然也可能是输出“不接受”。

  对于给定一个图灵机上的计算,是给定一个输入的编好码的字符串,经过一系列的运行,最后得到接受 或者不接受这两种情况。所以,任何定义好的图灵机,都会接受一些字符串,这些字符串的集合叫做一个语言。

  通用图灵机是一种特殊的图灵机,他的输入是另一个图灵机的编码和这个图灵机一个输入的编码,通用机得到这两个编码后,可以自己模拟这个图灵机得到这个输入的计算,并且输出相同的输出。

  如果无法理解通用机,就想想实际的例子。任何一台现在的电脑还有智能手机,都是一台通用机的实现。用手机座例子应该更好理解,从前的功能机就是非通用机,他的功能在出厂的时候就已经确定好了,但现在的智能机,可以通过软件模拟任何功能机的功能。

  通用机似乎很强大,但因为太强大了所以对于某些给定输入无法停机。理解很简单,比如说有一个很粗心的程序员,他经常会在他写的程序里面产生死循环。老板很恼火就想找人写个程序来检测程序里面是否有死循环。但其实这样的程序是无法完成的。详见“停机问题”。

  是由字母表组成的任意长度的所有可能的字符串集合去除L里面字符串的集合。

  图灵机接受的语言是recursive 识别的语言是 recursively enumerable (RE). 都是形式语言,而人类,如果看成是一种机器,接受的语言是自然语言。形式语言是自然语言的子集。也可以看出机器无法模拟人脑。

  图灵机有一个最重要的特性,就是对于任何给定输入,如果能停机,那么停机前必定经过了有限个步骤。

  还有寄存器里面的transition table,其实这玩意就是整个图灵机的核心,可以理解为算法,可计算方程,代码实现了之后就是程序。

  还有,计算能力的定义,是指能够接受或者识别字符串个数的多少。所以 图灵机的计算能力就是RE语言。人脑机的计算能力是自然语言。

  以及……任何的实现(也就是我们用的计算机了)都因为有限存储而被限定了计算能力。所以图灵机的计算能力,比任何一台现有的计算机,今后出现的计算机都强大。甚至超越了人类历史上出现过的、现有的和将来会造出来的所有计算机计算能力之和。

  非常容易理解。经典机的一个格子存储0或者1(如果是二进制编码)。那么量子机的一个格子,存储的就是…… 看下面吧

  Dwave不能算是量子计算机吧,现在单个量子比特的精确控制都无法实现。还有量子计算机的计算能力是没办法超越通用图灵机的,所以如果在经典机上无法实现的计算 量子机也无法完成。量子机唯一能做的就是比经典机更快单不是更多,而且现有量子算法相对于经典机的加速也很有限,最多只是多项式加速,所以在经典机上的NPcomplete问题在量子机上依然是NPcomplete。上面说的量子比特的表达也不对吧,一个量子比特不仅能表示0和1 也不仅能表示00 01 10 11这4种状态,更重要的是能表示一个以0和1两个向量为基的希尔伯特空间上任意一条长度为1的向量。而这样的向量是有无限多条,并且是阿列夫1。所以可以将莎士比亚的所有著作写入一个单独的量子比特。只是经过测量后,一个量子比特只会坍塌到0或者1上。其实如果要讨论量子图灵机模型,那么势必要讨论概率图灵机。经典图灵机的一个比特是表示0或者1,而一个概率图灵机表示的是0到1之间的一个实数,代表着取0的概率(取1的概率就是1减去他),所以概率机中的一个比特的状态也是有阿列夫1个。但这样的状态是欧几里得空间的向量或者说是Norm1,也就是0和1的概率和为1。而量子比特是希尔伯特空间向量,也就是Norm2 也就是0和1的概率平方和为1。 其实量子机是一个确定的系统,虽然在观测一个量子,会使量子以概率坍塌到本征态上,但整个系统的量子状态,在任意时间都可以计算出来,写成一个张量积的形式。

  当然量子机也有停机问题,识别的语言也是RE,所以计算能力和经典机等价。

  那些对量子机抱很大希望的人,很抱歉,不可能的事情一开始就是不可能的,不用再想了。

  而且现在的量子机情况很尴尬,一些算法有了,但没有机器可以实现。一个单一的量子比特的控制都无法有效的实现。具体情况参见12年诺奖,2种方法,一个是用黑盒束缚光子,一个光子存储一个量子比特的信息。另一个是用磁场束缚电子,一个电子存储一个量子比特的信息。

  现在已经有方法可以有效控制单独的的量子比特了,也就是说12年物理诺奖的内容已经很好的实现了。但离真正的量子计算机还差很远

  既然量子机无法做的更多,那么为什么还有人乐此不彼的在折腾?因为他可以做的更快。摩尔定律什么的就不说了,纳米材料什么的在什么情况下会显现量子效应我也不说了,真的好麻烦啊

  速度呢,如果直接看图灵机,那么速度可以用图灵机为算出结果所经过步骤的个数来衡量。长度短的输入,当然计算时间短,长的输入计算时间长。所以我们可以对任何图灵机,建立一个函数,图灵机输入的长度作为自变量,计算时间长度作为应变量,那么这个函数的增长速度,就定义了图灵机的时间复杂度。如果一个图灵机的时间函数增长缓慢,那么机器速度快。

  对于所有的问题,有些图灵机可解,有些不可解。对于所有可解的问题,有些可以快速解,有些无法快速解。

  所谓快速解的问题,是指存在一个算法或者图灵机,两者等价,能在多项式时间内解决其问题,称为P。NP是指(有好些个等价定义),不确定在多项式时间内能解决的问题。NOT-P是无法在多项式时间内能解决的问题。NP-complete是如果他在多项式时间内能解决,那么解决这样问题的算法,可以在多项式时间内解决任意的NP问题。简单的理解为NP中最难的问题就是NPc。

  现在回到量子机,量子机的两个重要应用,一个是大数分解问题。此问题属于NP,但没被证明是NPc。在经典机上的最快算法是指数时间,而shor的量子算法,基于量子傅里叶变换,可以在log时间解决。另一个应用是,搜索。但只做到了线性加速(如果我没记错)。 所以可以见如果一个问题是NPc 那么不论是经典机还是量子机,他都是NPc,而无法快速解决。

  经典机等价 量子机 等价 可计算方程 等价lambda计算 等价形式系统证明 等价算法 等价程序 等价超级硬件(有无限存储) 等价超级算盘(无限小棍和无限算珠) 等价多纸带图灵机 等价双堆栈PDA(push down automata 解释起来好麻烦……)

http://infomisa.net/tongyongtulingji/209.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有