从丘奇-图灵论题到多奇原理

《从丘奇-图灵论题到多奇原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第16卷增刊自然辩证法研究Vol.16,Spl2000年5月StudiesinDialecticsofNatureMay.,2000文章编号：1000–8934–(2002)增刊–0023–05从丘奇-图灵论题到多奇原理刘晓力(北京师范大学哲学系，北京100875)(中山大学逻辑与认知研究所，广东广州510275)摘要：本文对丘奇-图灵论题提出的背景，以及为什么哥德尔没有提出丘奇论题，而且直到给出图灵机概念之后才逐渐接受丘奇-图灵论题的真正原因作出某种解释，基于这种解释，将对多奇给出的“丘奇-图灵论题的物理版本”的内涵及意义作

2、出评价，对量子计算机的计算本质给出逻辑分析。关键词：可计算性；哥德尔；丘奇-图灵论题；多奇原理；量子计算机中图分类号：B813文献标识码：A—————————————————————————————————————————作者简介：(19–)，1从丘奇-图灵论题到多奇原理在理论计算机科学中，有了可计算性概念严格的数学刻划，才使证明一系列重要的数学问题的算法不可解性成为可能。一个众所周知的事实是，直到1935年著名的“算法可计算函数都是递归函数”这一丘奇论题提出，算法可计算性这个直观概念才有了精确的数学刻划。而同样需要指出的是，

3、哥德尔(K.Gödel)在此之前的1931年就引进了原始递归函数概念，1934年明确给出一般递归函数的定义，1934年春还曾与丘奇(A.Church)一起讨论如何给“算法可计算性”下一个精确的数学定义的问题。那么，为什么哥德尔没有适时给出丘奇论题，却对图灵工作大加赞赏，从而接受丘奇-图灵论题呢？我们认为，其中的最重要原因是，图灵是完全沿着哥德尔设想的思路对算法概念给出分析的第一人，图灵机概念澄清了形式系统概念的内涵；同时，与波斯特20年代的想法一样，图灵论题通过指出机器能做什么，把计算系统引入了物理世界，引发了一场信息革命和心

4、-脑-计算机的大论战。而且图灵论题揭示了哥德尔认识到的，可计算性是一个不依赖于形式系统的绝对概念这一事实。随着“计算机的发展遵循摩尔定律”计算机专家断言，计算机的复杂性遵循摩尔定律：每18个月将翻一番。这一假说被普遍认可，哥德尔对图灵工作大加赞赏的几个因素更加显示出对计算机发展的理论意义和现实意义。1980年代人们开始讨论如何“超越图灵计算”，将算法或计算这样的纯粹抽象的数学概念看作物理定律的体现，把计算系统看作自然定律的一个自然结果。特别是认为，丘奇-图灵论题也同时断定了一条物理原理，这就是1985年多奇(D.Deutsch

5、)提出的丘奇-图灵论题的物理版本(也称多奇原理)。正是基于这一原理，量子计算机的计算本质成为1990年以来人们关注的热点。我们认为，在当今对认知科学中认知可计算主义研究纲领提出质疑时，更有必要澄清关于丘奇-图灵论题和多奇原理的内涵，也有必要对量子计算机的计算本质作出恰当的逻辑分析。1哥德尔为什么没有提出丘奇论题历史上，狄特金(R.Dedekind)，皮亚诺(G.Peano)，司寇伦(T.Skolem)，希尔伯特(D.Hilbert)和阿克曼(W.Ackermann)都曾研究过递归函数，但哥德尔是第一个精确定义这个概念的。今天我

6、们所称的“原始递归函数”是哥德尔1931年在那篇划时代的论文中引进的。1934年2-5月，哥德尔在普林斯顿研究院关于不完全性结果的系列讲座中又引进了一般递归函数概念，指出：“一般递归函数(我们现在称原始递归函数)有着重要的特性，即对于每个给定的自变量值的集合，都能通过有穷程序计算出函数值。”具有历史意谓的是哥德尔还对此补充了一个颇具建设性的说明(著名的脚注3)：“这个命题的逆[即每个通过有穷程序计算的函数都是原始递归函数]似乎也是真的，除了[原始]递归，…其他形式的递归(例如与带两个变量的加法相对应的递归)是否也是允许的。由于

7、有穷可计算的概念还没有定义，目前不可能证明这个命题的逆，但是，它完全可以充当一种助探原则。”[6]哥德尔的这段脚注曾被戴维斯(MartinDavis)认为是丘奇论题的一种形式。例如，戴维斯(MartinDavis)1965年编辑《不可判定的》论文集时就曾认为，把脚注3与哥德尔后来在讲座中引进的一般递归函数的定义结合起来，相当于对算法可计算性作了严格的刻划，因此相当于哥德尔在丘奇之前提出了丘奇论题。他甚至以“哥德尔论题”6从丘奇-图灵论题到多奇原理的名称对其重新做了表述:“每个机械可计算函数都可用一般递归函数定义”。在准备编进《

8、不可判定的》论文集的一篇介绍哥德尔讲座的短文中，戴维斯表达了他的这一见解，并将初稿寄给哥德尔进行评价。完全出乎戴维斯意料的是，哥德尔在回信中对此表达了不同见解：“…说脚注3是丘奇论题的一种陈述是不正确的。我无非是提出了‘有穷可计算程序’与‘递归程序’是等价的一种猜想。但在系列