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

从丘奇-图灵论题到多奇原理刘晓力(北京师范大学哲学系,北京100875)(中山大学逻辑与认知研究所,广东广州510275)摘要:本文对丘奇-图灵论题提出的背景,以及为什么哥德尔没有提出丘奇论题,而且直到给出图灵机概念之后才逐渐接受丘奇-图灵论题的真正原因作出某种解释,基于这种解释,将对多奇给出的“丘奇-图灵论题的物理版本”的内涵及意义作出评价,对量子计算机的计算本质给出逻辑分析。关键词:可计算性;哥德尔;丘奇-图灵论题;多奇原理;量子计算机中图分类号:B813 文献标识码:A—————————————————————————————在理论计算机科学中,有了可计算性概念严格的数学刻划,才使证明一系列重要的数学问题的算法不可解性成为可能。一个众所周知的事实是,直到1935年著名的“算法可计算函数都是递归函数”这一丘奇论题提出,算法可计算性这个直观概念才有了精确的数学刻划。而同样需要指出的是,哥德尔(ödel)在此之前的1931年就引进了原始递归函数概念,1934年明确给出一般递归函数的定义,1934年春还曾与丘奇()一起讨论如何给“算法可计算性”下一个精确的数学定义的问题。那么,为什么哥德尔没有适时给出丘奇论题,却对图灵工作大加赞赏,从而接受丘奇-图灵论题呢?我们认为,其中的最重要原因是,图灵是完全沿着哥德尔设想的思路对算法概念给出分析的第一人,图灵机概念澄清了形式系统概念的内涵;同时,与波斯特20年代的想法一样,图灵论题通过指出机器能做什么,把计算系统引入了物理世界,引发了一场信息革命和心-脑-计算机的大论战。而且图灵论题揭示了哥德尔认识到的,可计算性是一个不依赖于形式系统的绝对概念这一事实。随着“计算机的发展遵循摩尔定律”计算机专家断言,计算机的复杂性遵循摩尔定律:每18个月将翻一番。这一假说被普遍认可,哥德尔对图灵工作大加赞赏的几个因素更加显示出对计算机发展的理论意义和现实意义。1980年代人们开始讨论如何“超越图灵计算”,将算法或计算这样的纯粹抽象的数学概念看作物理定律的体现,把计算系统看作自然定律的一个自然结果。特别是认为,丘奇-图灵论题也同时断定了一条物理原理,这就是1985年多奇()提出的丘奇-图灵论题的物理版本(也称多奇原理)。正是基于这一原理,量子计算机的计算本质成为1990年以来人们关注的热点。我们认为,在当今对认知科学中认知可计算主义研究纲领提出质疑时,更有必要澄清关于丘奇-图灵论题和多奇原理的内涵,也有必要对量子计算机的计算本质作出恰当的逻辑分析。1哥德尔为什么没有提出丘奇论题历史上,狄特金(),皮亚诺(),司寇伦(),希尔伯特()和阿克曼()都曾研究过递归函数,但哥德尔是第一个精确定义这个概念的。今天我们所称的“原始递归函数”是哥德尔1931年在那篇划时代的论文中引进的。1934年2-5月,哥德尔在普林斯顿研究院关于不完全性结果的系列讲座中又引进了一般递归函数概念,指出:“一般递归函数(我们现在称原始递归函数)有着重要的特性,即对于每个给定的自变量值的集合,都能通过有穷程序计算出函数值。”具有历史意谓的是哥德尔还对此补充了一个颇具建设性的说明(著名的脚注3):“这个命题的逆[即每个通过有穷程序计算的函