&&&&递归可枚举集和图灵度：可计算函数与可计算生成集研究/国外数学...
自营订单满39元（含）免运费
不足金额订单收取运费5元起
邀请好友参加吧
版 次：1页 数：字 数：印刷时间：日开 本：纸 张：胶版纸包 装：精装是否套装：否国际标准书号ISBN：1丛书名：国外数学名著系列所属分类：&&&
下载免费当当读书APP
品味海量优质电子书，尊享优雅的阅读体验，只差手机下载一个当当读书APP
本商品暂无详情。
当当价：为商品的销售价，具体的成交价可能因会员使用优惠券、积分等发生变化，最终以订单结算页价格为准。
划线价：划线价格可能是图书封底定价、商品吊牌价、品牌专柜价或由品牌供应商提供的正品零售价（如厂商指导价、建议零售价等）或该商品曾经展示过的销售价等，由于地区、时间的差异化和市场行情波动，商品吊牌价、品牌专柜价等可能会与您购物时展示的不一致，该价格仅供您参考。
折扣：折扣指在划线价（图书定价、商品吊牌价、品牌专柜价、厂商指导价等）某一价格基础上计算出的优惠比例或优惠金额。如有疑问，您可在购买前联系客服咨询。
异常问题：如您发现活动商品销售价或促销信息有异常，请立即联系我们补正，以便您能顺利购物。
当当购物客户端手机端1元秒
当当读书客户端万本电子书免费读「好书推荐」在人工智能的灵魂深处……
在人工智能的灵魂深处……
作者：刘锋
一个美丽的机器人使你如痴如狂了吗？
果真如此，程序笑了；
在程序背后，算法笑了；
在算法背后，计算理论笑了；
计算理论，也就是《计算理论解析》（张寅生著，清华大学出版社，2016年）这本书所揭示的东西！
《计算理论解析》是解释计算机编码背后的灵魂------计算的基本原理。不过，它不侧重提供具体问题的算法设计-------那是诸如“自然语言处理（图形图像、语音识别…）经典算法集成”一类的书籍所做的事情；这本书所做的事情是，阐释在这些算法背后的基本原理是什么。
图灵被称为人工智能之父。但是为什么图灵设计了图灵机了？他怎么会灵机一动设计了这个神一样的东西？还是有什么背景驱使他、启发他做这个事情？《计算理论解析》解释了这一内在的联系。这是《计算理论解析》的难能可贵之处。它以数学般的语言精微地展示了这一计算思想史的发展脉络-------
事实上，在图灵之前，还有“图灵”------那些希望将符号计算化的人；那些将计算机械化的人。
如果说，图灵是设计图灵机的人，那么可以说，设计图灵灵魂的人是递归论，其主要的人物是斯克伦、哥德尔和希尔伯特。
逻辑原子主义者，如罗素，认为数是逻辑的实现。给定一个被称为数字的符号0和一个操作（运算）符号“后继”，可以生成所有的自然数，即0的后继是1，1的后继是2 ……那么是否可以将数学运算也表示为像0和“后继”这样少数几个简单的运算呢？
斯克伦（ThoralfSkolem，年，挪威数学家）开始尝试这件事情。
他把一种函数命名为递归函数，他希望把各种函数都划归为递归函数。递归最初使用了Recursion。首先使用“递归”术语的人是希尔伯特（David Hilbert，年）。1904年和1923年，希尔伯特分别使用了rekurrent和rekursion，即德文“递归的”和“递归”(程序员还记得函数语句最后那个Return吧？)。1923年，斯科伦证明，加法和乘法是递归函数。
那么，递归函数是什么意思？为什么会构建所有可计算函数？作者剖析了递归函数在计算中的基础地位：正像盖房子要用砖石一类基本材料累积一样，如果对于函数的计算可以分解为很小的基本步骤，就有可能实现一个复杂函数的计算。这就是递归的原初思想。从递归，就是分步骤（“递”）地回去（“回去”）。从哪里回到哪里？假设要计算一个数（函数值），第一部计算仅仅实现了一点点进步，趋近于函数值近了一点点，这一点点计算的结果就可以用于计算的中间结果（自变量）计算下一步，这个从（中间步骤的）结算结果当作计算的原初材料（自变量）就是一个“回来”的过程，就完成了一次“递归”。以此，递归可以看作是计算的一个时间上的分部计算。
当然，不同函数的计算防范不同，递归函数的计算如何实现各种函数的计算呢？作者展示了哥德尔（Kurt G?del，）发现和定义的五花八门、千差万别的数学函数的基本的类别是“原始递归函数”，比如，在一个班级里选一个课代表，这是一个在封闭空间里向着本空间的一个元素的映射，即“投影函数”；在数学里，加法不正是这样一种映射吗？如果班级里每个学生都归结为一个班主任的管理，这是一个空间里向着一个确定的元素的映射，即“常值函数”；在数学里，求所有自然数的极小值是不是都等于1（如果0不算是自然数）？这就是常值函数的应用；如果求取班级里每个学生的学号的后一个学号，这就是“后继函数”。哥德尔把此三类函数归结为构造复杂函数的“砖石”，因此递归函数的另一个特征是空间上的分解计算。
至此，逻辑学家在图灵之前，论证了有可能以一种被称为递归函数的基本算法，计算各种各样的数学函数，也就是实现各种各样的数的计算。
当然，如果很复杂的计算可以通过简单的计算实现，或许有一种机械性的方法，实现这种简单的计算；因为简单计算不用多么聪明就能实现，或许机械就能应付了吧？如果机械能够实现这些简单的计算（诸如原始递归函数的计算），那么复杂的计算就像盖楼一样可以累积地实现！-------积跬步可以至千里啊！这个问题就是算法及其能行性的问题。算法问题提出可否将复杂问题简化为简单的计算；能行性问题提出可否机械可实现算法，即希尔伯特提出希尔伯特第十问题，即算法和能行性问题。正是为了证实为了求解希尔伯特第十问题，图灵设计了图灵机，它是机械装置实现递归计算的模型。这是《证明方法与理论》揭示的原理和核心。
递归的原理并不高深莫测，它浅显易懂、朴实而单纯。举个例子，如果让机器计算4+6，机器不懂，但是可以通过递归步骤一步一步递归实现（按照如下箭头的递归6次）：
4+1=(4+0)+1
4+2=(4+1)+1
4+3=(4+2)+1
4+4=(4+3)+1
4+5=(4+4)+1
4+6=(4+5)+1
大量的书籍介绍了图灵机的结构，但是探讨图灵机是如何实现递归计算的书籍，很少很少！这也就是程序员熟练编程而不懂计算机的数学原理的原因；是建筑工人不能成为设计师的原因，因为仅仅“照葫芦画瓢”知道了图灵机的运行方法，不去弄懂背后灵魂--------数学家在设计背后的思想-----的原因。与此不同，《计算理论解析》是一本触及灵魂的书，它抽取了计算的根本特征，勾勒了计算思想的发展脉络，展示了计算思想和实践的发展过程：哲学(R)逻辑(R)数学(R)（物理和工程）的计算机科学技术，是人类的计算思想的精华和浓缩。它实际上展示了人工智能的终极密码，揭示：
计算的通用公式；
算法的起源和通用表达；
人工智能的根本特征；
分析IT发展的坐标系和望远镜；
符号计算和数值计算的中继和桥梁。
这本书在我国的IT领域很有特点，特别是它阐释、介绍、解答了一些我国计算机科学技术领域“短板”的内容，比如，为什么图灵机是递归计算，书中列出了详细的图解和公式说明；如何实现符号计算（不只是0，1，2等等的数值计算），贯通语言学和计算科学，如何展现乔姆斯基语法和图灵机作为一枚硬币的两面的关系，如何对汉字进行计算，等等。它相当于计算模型、计算理论课的简化、通俗版讲义，也相当于程序员算法原理的背景和历史介绍，或IT人士战略分析的的参考读物，人工智能相关的数理逻辑（特别是递归论、集合论、证明论）导论。这一点很重要。很多人知道中国人工智能、计算机科学技术原创能力弱，与计算机科技发达国家有差距，但是如何弥补这一差距？作者的基本看法是，我们对计算的基础理论特别是数理逻辑掌握的不足。一个很好的例子是，我国是程序员大国，却很少研究能开发出编程语言，差距在于逻辑理论研究不足、落后。要在人工智能领域、IT领域掌握主动权，进行原始创新，必须对计算的基本思想的背景、发展历史、基本原理有透彻的理解和感悟，如此才能在次游、下游产生理论、技术、应用上创新。因此，在计算原理、思想上的融会贯通是原始创新的基本条件。这本书是作者尝试的在计算机基础理论和方法论上理解人工智能、计算机科学技术的一把钥匙，大有一册在手，胸有成竹的感觉。
清华大学出版社历来是出版计算机科学技术著作的前沿阵地，这一次，《计算方法与理论》以其独特的视角、笔触，严谨而深刻地展示了计算的普适性和能行性，展示了计算额精微和奥妙，展示了符号、数值与逻辑，机械与人的思想和工程的完美结合，为计算机科学技术学术著作的园地增添了新葩。
注：授权发布，转载须统一注明来自长安街读书会公众平台：changanjie-read。
本期责编：任天也
长安街读书会
相聚长安街，走读长安街。长安街读书会是在中央老同志的鼓励支持下发起成立，旨在继承总理遗志，践行全民阅读。为中华之崛起而读书、学习、养才、报国。现有近千位成员主要来自长安街附近中直机关及各部委中青年干部、中共中央党校学员、国家行政学院学员、全国青联委员、全国两会代表委员等喜文好书之士以及中央各主要出版机构的资深出版人学者等，书友以书相聚，以学养才。
长安街读书会
长安街读书会：长按二维码即可关注，自助申请入会。
责任编辑：
声明：本文由入驻搜狐号的作者撰写，除搜狐官方账号外，观点仅代表作者本人，不代表搜狐立场。
微信关注：长安街读书会公众号【changanjie-read】，可申请入会
2015长安街读书会年度好书榜评选
今日搜狐热点丘奇定理_百度百科
声明：百科词条人人可编辑，词条创建和修改均免费，绝不存在官方及代理商付费代编，请勿上当受骗。
本词条缺少名片图，补充相关内容使词条更完整，还能快速升级，赶紧来吧！
在理论计算机科学中，有了可计算性概念严格的数学刻划，才使证明一系列重要的数学问题的算法不可解性成为可能。一个众所周知的事实是，直到1935年著名的“算法可计算函数都是递归函数”这一丘奇论题提出，算法可计算性这个直观概念才有了精确的数学刻划。
丘奇定理丘奇定理
而同样需要指出的是，哥德尔(K.G&del)在此之前的1931年就引进了原始递归函数概念，1934年明确给出一般递归函数的定义，1934年春还曾与丘奇(A.Church)一起讨论如何给“算法可计算性”下一个精确的数学定义的问题。那么，为什么哥德尔没有适时给出丘奇论题，却对图灵工作大加赞赏，从而接受丘奇-图灵论题呢？
我们认为，其中的最重要原因是，图灵是完全沿着哥德尔设想的思路对算法概念给出分析的第一人，图灵机概念澄清了形式系统概念的内涵；同时，与波斯特20年代的想法一样，图灵论题通过指出机器能做什么，把计算系统引入了物理世界，引发了一场信息革命和心-脑-计算机的大论战。而且图灵论题揭示了哥德尔认识到的，可计算性是一个不依赖于形式系统的绝对概念这一事实。
随着“计算机的发展遵循摩尔定律”这一假说被普遍认可，哥德尔对图灵工作大加赞赏的几个因素更加显示出对计算机发展的理论意义和现实意义。1980年代人们开始讨论如何“超越图灵计算”，将算法或计算这样的纯粹抽象的数学概念看作物理定律的体现，把计算系统看作自然定律的一个自然结果。特别是认为，丘奇-图灵论题也同时断定了一条物理原理，这就是1985年多奇(D.Deutsch)提出的丘奇-图灵论题的物理版本(也称多奇原理)。正是基于这一原理，量子计算机的计算本质成为1990年以来人们关注的热点。我们认为，在当今对认知科学中认知可计算主义研究纲领提出质疑时，更有必要澄清关于丘奇-图灵论题和多奇原理的内涵，也有必要对量子计算机的计算本质作出恰当的逻辑分析。
丘奇定理逻辑分析
丘奇定理哥德尔为什么没有提出丘奇论题
历史上，狄特金(R.Dedekind)，皮亚诺(G.Peano)，司寇伦(T.Skolem)，希尔伯特(D.Hilbert)和阿克曼(W.Ackermann)都曾研究过递归函数，但哥德尔是第一个精确定义这个概念的。今天我们所称的“原始递归函数”是哥德尔1931年在那篇划时代的论文中引进的。月，哥德尔在普林斯顿研究院关于不完全性结果的系列讲座中又引进了一般递归函数概念，指出：
“一般递归函数(我们现在称原始递归函数)有着重要的特性，即对于每个给定的自变量值的集合，都能通过有穷程序计算出函数值。”
具有历史意谓的是哥德尔还对此补充了一个颇具建设性的说明(著名的脚注3)：
“这个命题的逆[即每个通过有穷程序计算的函数都是原始递归函数]似乎也是真的，除了[原始]递归，…其他形式的递归(例如与带两个变量的加法相对应的递归)是否也是允许的。由于有穷可计算的概念还没有定义，目前不可能证明这个命题的逆，但是，它完全可以充当一种助探原则。”[6]
哥德尔的这段脚注曾被戴维斯(Martin Davis)认为是丘奇论题的一种形式。 他甚至以“哥德尔论题”的名称对其重新做了表述:
“每个机械可计算函数都可用一般递归函数定义”。
在准备编进《不可判定的》论文集的一篇介绍哥德尔讲座的短文中，戴维斯表达了他的这一见解，并将初稿寄给哥德尔进行评价。完全出乎戴维斯意料的是，哥德尔在回信中对此表达了不同见解：
“… 说脚注3是丘奇论题的一种陈述是不正确的。我无非是提出了‘有穷可计算程序’与‘递归程序’是等价的一种猜想。但在系列讲座中我根本没有料想到，我的递归概念包含了所有可能的递归。”[3]
从这封信中至少我们可以看出，哥德尔1934年春就给出今天意义上的“递归函数”的定义了，但是他完全没有猜到他当时的定义足够宽，可以包容所有的递归。而且他认为，自己对算法可计算性的猜测(即戴维斯所说的“哥德尔论题”)并不是丘奇论题的等价说法，但它可以充当一种助探原则，帮助人们寻求算法可计算性概念的一个令人满意的数学刻划。
丘奇定理从l可定义性到丘奇论题
丘奇是在1935年4月美国数学会的一次报告中宣布他的论题的。事实上，丘奇最早关注可计算性是从l可定义性概念着手的。据当年丘奇的学生克林尼(S.C.Kleene)的说法，到了1933年，丘奇的“l可定义性”已经作为一个成熟的概念在普林斯顿的逻辑学家中流传。他当时猜测，l可定义函数就是算法可计算函数，并最终提出这一论题。后来，克林尼曾回忆说：
“当丘奇提出这一论题时，我准备用对角化方法否证它，希望指出算法可计算函数超出了l可定义函数类。但是我很快认识到做不到这一点。于是，一夜之间我成了丘奇这个论题的支持者。”[9]
据戴维斯考察，尽管丘奇年明显对可计算性概念怀有浓厚兴趣，但直到哥德尔作普林斯顿系列讲座之前，没有明显的迹象表明他认为算法可计算性与某种严格的数学概念相一致，也没有相关的什么特别的说法。也许正是在月与哥德尔讨论之后，他才形成了明确的见解，并给出后来的丘奇论题的。日，在给克林尼的一封信中，丘奇则对此曾给出了一个多少含糊其词的说法：
“谈及哥德尔、递归函数和算法可计算性概念，这段历史原本是这样的。在与哥德尔讨论l可定义性概念时，我们发现对于算法可计算性找不到一个好的定义，我建议，可以用l可定义性充当定义，但是哥德尔认为完全不合适。我回答说，如果你能提供任何一个，哪怕是部分令人满意的定义，我都将证明它一定包含在l可定义性概念之中。当时哥德尔唯一的想法是，先将算法可计算性当作一个不确定概念，陈述能描述这个概念公认特性的公理集合，然后在此基础上再去做其他事情。显然，后来他认为，可以对厄尔布朗(J.Herbrand)建议的递归函数概念沿着可计算性概念的方向加以修正。他特别指出，可以在这个意义上将递归和算法可计算性二者联系起来。但是，他又说，他并不认为这两个概念能够令人满意地被确认是彼此一致的，除非是在一种助探的意义上。”[3]
当1935年丘奇向数学界宣布他的论题时，他是如下表达的：“采纳厄尔布朗的建议，并在一个重要方面作了修正，哥德尔在1934年的系列讲座中提出了递归函数的定义，这里采取的基本上是哥德尔关于正整数递归函数的定义，而且需要强调的是，正整数的算法可计算函数将被确定为与递归函数一致。由于其他关于算法可计算性的似真定义原本都是导出概念，因此它们或者与递归性等价，或者比递归性弱。”[3]
显然，丘奇没有选择用“l可定义”的术语陈述他的论题，而是使用了“厄尔布朗-哥德尔一般递归函数”的术语。在这里，l可定义性隐含地划在了“其他算法可计算性的似真定义”中了。这种措辞给人的印象是，1935年春，丘奇还没有认定，l可定义性与厄尔布朗-哥德尔一般递归是等价的。直到1936年4月，丘奇在《初等数论中的一个不可解问题》中才断定l可定义性函数就是一般递归函数。
在1936年的论文中，丘奇给出了如今我们所知的丘奇论题的标准陈述：“现在我们通过与正整数的递归函数(或者正整数的l可定义函数)概念相一致，来定义已经讨论过的正整数的算法可计算的概念。这个选出的与直观的可计算性概念相符的定义被认为是已经核证了的。”[1]
这里，丘奇把算法可计算性与递归性之间的这种等价称为“定义”，波斯特(E.Post)1936年曾极力反对定义的提法，认为应当仅仅作为一种工作假说看待 。1943年克林尼指出，描述这种等价性的命题包含了很强的工作假说的特征，尽管我们确有不得不相信它的充足理由，因此，建议用“论题”的术语表达这个命题。
尽管提出了丘奇论题，但哥德尔当时并不赞成可计算性与递归性或l可定义性等价的说法。在他看来，在还没有找到一组公理刻划算法可计算性概念所包含的公认特性之前，不可能有完全令人满意的严格的数学定义。直到1936年图灵(A.Turing)的结果公布时，哥德尔才承认这个困难已经克服。
丘奇定理哥德尔为什么赞赏图灵论题
我们认为，正是由于年，丘奇、克林尼和哥德尔等人对于可计算性概念的数学刻划做了一系列工作，最终丘奇提出了他的标准形式的丘奇论题。同时在此期间，图灵完全独立于普林斯顿数学家思考可计算性问题，最终以通用图灵机概念刻划了算法可计算性，即“算法可计算的就是通用图灵机可实现的”。它可表达为如下“图灵论题”：
“每个算法可在一台通用图灵机上程序化。”
哥德尔在1965年发表的普林斯顿讲座笔记(1934)的后记中，对图灵的工作给予了极高的评价，我们认为，哥德尔不接受丘奇论题，而赞赏图灵论题的主要原因至少有几点：
(1) 通用图灵机概念澄清了形式系统概念
可以说，在哥德尔证明不完全性定理时，形式系统还是一个相当模糊的概念，否则哥德尔会采取更加简洁的方式证明自己的定理。正是有了图灵机概念，才使形式系统的特性更加清晰准确地为人们所把握，形式系统不过是一种产生定理的机械程序，图灵机的工作程序正是数学家在形式系统中实际工作的程序。或者说，形式系统不过是一台准许在某些步骤上按照预定范围作出选择的图灵机。当然，也正是由于有了图灵机概念，哥德尔关于数学形式系统的不完全性定理才有了各种用图灵机程序代替形式系统的版本，如停机问题版本以及后来的算法信息论中的复杂性版本等。[10]
(2) 图灵是沿着最贴近哥德尔设想的研究进路作出结论的
丘奇的工作尽管精道优雅，但他完全基于纯粹的数学分析；图灵的分析不仅仅局限于数学形式世界，它是值得称道的哲学应用的实例。[3]而且，图灵是沿着最贴近哥德尔设想的研究进路作出结论的。 哥德尔曾评价说，“图灵的工作对于‘机械程序’(也称‘算法’,‘计算程序’或‘组合程序’)概念给出了一种分析，指明这个概念是与‘图灵机’等价的”。而先前给出的其他关于可计算性的等价定义，“无论如何很少适合我们最初的目的”。[2]
那么，哥德尔所说的“最初目的”是什么？显然，是他一直主张的，“先将算法可计算性当作一种不定义概念，给出能够描述这个概念公认特性的公理集，在此基础上再做某些事情”，在他看来，这才是寻求可计算性严格的数学刻划的真正途径。尽管图灵并没有在任何形式化的意义上采用公理化方法处理问题，但是他指明了，“算法可计算性公认的特性”必然导致一个确定的函数类，这个函数类是可以精确定义的，图灵给出的清晰准确表达了机械程序概念的图灵机是指产生部分递归函数，而不是指产生一般递归函数的图灵机。因此，在哥德尔那里，图灵才是给出准确概念与直观概念相符的令人信服的理由的第一人，用“可在图灵机上程序化”或“图灵机可实现”这个鲜明概念对算法可计算性的刻划，既是正确的，又是唯一符合我们最初目的的。
(3) 图灵机可计算概念揭示了可计算性是一个不依赖于形式系统的事实
为了使我们进一步看出，为什么图灵的工作对于哥德尔有如此重要的意义，还应当考察哥德尔对于绝对可计算性概念的理解。日，哥德尔在维也纳大学报告“论证明长度”，提到所谓“加速定理”。[7]定理的严格陈述用到“在一个形式系统S中一个函数φ(x)是可计算的”这个概念，它是指对每个数m，都存在相应的数n，使φ(m)= n在系统中是可证的。对于满足每一个系统都比前一个系统更强的形式系统的序列S1,S2,…，称一个函数在Si中是可计算的，是指它是依赖于i的。
在这次报告中，哥德尔附加了关于“绝对可计算性”的一个说明：“可以指出，在形式系统之一的Si中可计算，甚至在一个超穷类型中可计算的一个函数,在 S1中已经是可计算的。因此，在某种确定的意义上，‘可计算’的概念是‘绝对的’，而现实中所有其他熟知的元数学概念(如可证,可定义)等，却完全是依赖于给定系统的。”
哥德尔在这种“绝对的”意义上认识可计算性大致是在年，在1946年《关于数学问题的普林斯顿200周年纪念会感言》中，哥德尔又特别强调了这种“绝对性”的意义：
“在我看来，一般递归或图灵机可计算这个概念的极端重要性似乎极大地归于这样一个事实，即有了这个概念，就第一次成功地给出有意义的认识论观念上的一种绝对的定义，即可计算性不依赖于形式系统的选择。但在所有先前处理的其他情形下，例如，像定义可判定性或可定义性时，都要依赖于给定的语言。尽管绝对可计算性也不过是特殊种类的可判定性概念，但情形已与过去完全不同。”[8]
(4) 图灵机概念把一个计算系统引入了物理世界
另一个值得哥德尔称道图灵工作的原因恐怕就是，同波斯特20年代曾经有过的想法一样，图灵通过指出计算机器能做什么，把一个计算系统引入物理世界，或者说，把一个是否可计算的问题转换成了一个物理上是否可实现的问题，引发了一场信息革命和心-脑-计算机的大论战。图灵实际上指出了，凡是可形式化描述并可以算法化的东西，都可以找到作为通用图灵机特例的计算机迅速准确地处理，这一原理开启了人类智能的机器模拟的新纪元。正如图灵在《可计算数》一文中所讲的，他本人研究可计算性的动机不仅仅在形式上，而在于“心智科学”上。哥德尔甚至直到晚年仍不减探讨由图灵提出的心灵-大脑-计算机的话题的兴趣，恐怕也表明他对于心智科学情有所钟。
5 丘奇-图灵论题的物理版本与量子计算机的计算本质
哥德尔赞赏图灵工作的几个因素，恰是现代理论计算机发展的基础和动力所在。当第一台通用电子计算机这种物理装置诞生后，人们真正看到了通用图灵机的物理实现(虽然没有无限存储)。从此，人们开始思考，实在世界本身是可计算的吗？模拟客观实在的理想模拟机器原则上究竟是物理可实现的，还是客观世界完全超出了通用图灵机所模拟的范畴？对此，相当一部分物理学家抱有乐观态度。1985年，牛津大学的多奇教授甚至引进了一个颇具启发的“丘奇-图灵论题的物理版本”，将“能行可计算的函数”替换为“有限可实现的物理系统”，陈述了他的所谓“多奇原理”(也称“物理的丘奇-图灵原理”)：“每个有限可实现的物理系统，总能为一台通用模拟机器以有限方式的操作来完美地模拟”[4]。我们知道，基于现代物理学和生物物理学，许多物理学家认为，从巨大的天体到我们的生命体，直至人类心灵，都是有限可实现的物理系统的子系统，因此，依多奇之见，原则上都可以用通用计算机以有限方式的操作完美的模拟。
显然，多奇原理是较丘奇-图灵论题更强的“工作假说”，从丘奇-图灵论题到多奇原理，我们的可计算疆域在不断拓展。如果多奇原理是正确的，它将揭示出物理实在的深刻本质。这种基于物理主义和可计算主义的立场也恰是人工智能专家奉行的各种工作假说的核心。多奇等人完全将算法或计算这样的纯粹抽象的数学概念看成了物理定律的体现，把计算系统看成了自然定律的一个自然结果，在他们看来，通用计算机的概念不仅为自然规律所认可，而且很可能就是自然规律的内在要求。事实上，我们知道，所有倡导虚拟现实技术、人工生命、人工智能的人都相信多奇原理的真理性。当然也没有任何有力的科学证据能够反驳多奇原理，因为它是一个包含“通用模拟机器”概念的全称命题，原则上通用模拟机器可实现的算法(程序)数目是无限的。
依照理论计算机的最新进展，量子计算机的倡导者断言，能够实现多奇原理的通用模拟机器只能是量子通用图灵机。1998年作为“量子领域旗手”的杰拉德·密尔本(G.L.Milburn)指出，物理理论与物理版本的丘奇-图灵论题密切相关的事实是，物理理论是通过数学给出观察数据的，这些数据正是那些被我们称作可计算问题所提供的数据，因此这些数据可通过在一台通用图灵机上运行的算法得到。无论是经典的还是量子的物理系统都可以任意高的精度模拟，然而对某些问题，运行程序的时间可能是一个天文数字。如果世界是经典的，可以用蒙特卡罗方法等有效模拟随机性；但如果世界是具有不可约随机性的量子的，就不能用基于隐变量的经典随机性来解释量子随机性，量子世界的游戏需遵循费曼规则。因此费曼(R.Feynmen)意识到，解决这一问题的方法是建造一种量子计算机，即利用量子过程本身作为计算手段，计算的基本步骤将在原子或亚原子水平上进行，于是，1998年，丘奇-图灵论题经多奇原理，又被修正成：
“所有有限可描述的物理测量系统的结果都可以很好地为一台通用量子计算机以有限方式的操作完美地模拟，测量结果的记录是最终产物。”
这里的“有限可描述的物理测量系统” 是指建立和操纵一个测量装置的指令必须能够用有限的代码来表达；“完美的模拟”是指，模拟产生的数据与真实测量所得的数据无法区分；“最终产物”是指所有的模拟测量必须在某一时刻结束，不再继续产生新结果。
那么量子计算机超越经典计算机之处何在？它的计算本质究竟为何？
首先，量子计算机可以完成经典计算机所不能完成的计算：例如，它可以任意的精确度模拟一个量子物理系统，可使求解时间不随问题的规模呈指数增长。例如，以往要完成一个64位数字分解成质因数的乘积的运算，即使是使用超级计算机也要花比宇宙年龄还要长的时间。而贝尔实验室的彼德·肖尔(Peter Shor)的量子算法，依赖于大尺度的量子纠缠，可在量子计算机上以相当短的时间内成功地将一个64位数字分解成质因数的乘积。量子计算机所以具有超出经典图灵机的能力，在于量子相干性产生的并行计算的威力。
量子计算机是一个实现计算的物理装置，是遵循量子物理学规律运行的物理系统，而且量子计算机是一种建立在量子图灵机基础上的现代计算机。通用图灵机的算法是完全确定性的，在这种确定性算法中，当图灵机的当前读写头的状态和当前存储单元内容给定时，下一步的状态及读写头的运动完全确定。在经典的概率算法中，当前读写头的状态和当前存储单元内容给定时，图灵机以一定的概率变换到下一个状态及完成读写头的运动。这个概率函数是取值[0，1]的实数，它完全决定了概率图灵机的性质。量子计算机与经典概率图灵机的区别仅仅在于当前读写头的状态和当前存储单元内容由经典的正交态(0，1)变成了量子态(0，1，0和1的几率迭加态)，而概率函数则变成了取值为复数的概率振幅函数，于是量子计算机的性质由概率振幅函数确定。量子计算机能作到高效的计算，完全得益于量子迭加效应，即一个原子的状态可处于0和1的几率迭加态。一般来讲，采用L个量子位，量子计算机可以一次同时对2L个数进行处理，相当于一步计算完成通常经典计算机2L个数的计算。量子计算机就是以量子态对应于计算机的数据和程序(这需要以量子比特取代经典比特)，读写头不同的物理状态由量子物理描述，机器的动力学机制也由量子物理决定，当然一个更为重要的问题是，我们还必须描述它的输出，而我们最后需要的又是经典比特，而不是量子比特，这就要解决棘手的“消相干性”。
但是，我们必须清楚地认识到，无论量子计算机的速度有多快，既然从理论上讲，量子计算机不过是一台量子图灵机，那么它就必然受到哥德尔定理所设定的逻辑极限的限制，量子计算机不能计算不可计算的函数，也不能解决停机问题。说到底，量子计算机的计算本质上依然是图灵机计算，即递归函数计算，因此丘奇-图灵论题依然是量子计算机的理论基础。多奇试图将整个物理世界纳入计算的范围，试图以量子计算机模拟人类智能仍然不能摆脱逻辑固有的极限。如果可计算性如哥德尔所言，是不依赖于形式系统的绝对概念，那么量子计算机也不过是另一个计算速度更快的计算载体而已。
值得思考的是，对计算技术的不懈追求是否能使我们切实在程序中捕获一个真实的 “一致而完备的”世界？[11]在为大自然中的问题提供一个科学解答过程中是否不存在任何逻辑障碍？除了图灵机之外，是否存在其他计算模型，比如DNA计算机等，人类心智是否可能是某种超越图灵机的机器？多奇原理告诉我们，不仅物理学决定了计算机能做什么，而且反过来，计算机能做什么，也将决定物理定律最终的性质，多奇原理的本意显然绝不局限于对计算载体进行变革的意义，而在于指出，真实世界 = 物理世界 = 计算世界。