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

第 18卷增刊自然辩证法研究 Vol . 18, Sup 2002 年9月 St udi es in Di al ect i cs of Nat ure Sept . , 2002 ————————————作者简介:刘晓力(1954 -),女,内蒙古人,北京师范大学哲学系教授,中山大学逻辑与认知研究所兼职研究员。主要研究方向:现代逻辑和哥德尔思想。 1 文章编号: 1000 – 8934 –( 2002 ) 增刊– 00 23–05 从丘奇- 图灵论题到多奇原理刘晓力( 北京师范大学哲学系,北京 100875 ) ( 中山大学逻辑与认知研究所,广东广州 510275 ) 摘要: 本文对丘奇- 图灵论题提出的背景,以及为什么哥德尔没有提出丘奇论题,而且直到给出图灵机概念之后才逐渐接受丘奇- 图灵论题的真正原因作出某种解释,基于这种解释,将对多奇给出的“丘奇-图灵论题的物理版本”的内涵及意义作出评价,对量子计算机的计算本质给出逻辑分析。关键词:可计算性;哥德尔;丘奇-图灵论题;多奇原理;量子计算机中图分类号: B813 文献标识码:A —————————————————————————————在理论计算机科学中, 有了可计算性概念严格的数学刻划, 才使证明一系列重要的数学问题的算法不可解性成为可能。一个众所周知的事实是,直到 1935 年著名的“算法可计算函数都是递归函数”这一丘奇论题提出, 算法可计算性这个直观概念才有了精确的数学刻划。而同样需要指出的是, 哥德尔( ? del ) 在此之前的 1931 年就引进了原始递归函数概念, 1934 年明确给出一般递归函数的定义, 1934 年春还曾与丘奇() 一起讨论如何给“算法可计算性”下一个精确的数学定义的问题。那么, 为什么哥德尔没有适时给出丘奇论题, 却对图灵工作大加赞赏,从而接受丘奇- 图灵论题呢? 我们认为, 其中的最重要原因是, 图灵是完全沿着哥德尔设想的思路对算法概念给出分析的第一人, 图灵机概念澄清了形式系统概念的内涵;同时,与波斯特 20 年代的想法一样,图灵论题通过指出机器能做什么, 把计算系统引入了物理世界, 引发了一场信息革命和心-脑- 计算机的大论战。而且图灵论题揭示了哥德尔认识到的, 可计算性是一个不依赖于形式系统的绝对概念这一事实。随着“计算机的发展遵循摩尔定律” 1 这一假说被普遍认可, 哥德尔对图灵工作大加赞赏的几个因素更加显示出对计算机发展的理论意义和现实意义。 1980 年代人们开始讨论如何“超越图灵计算”,将算法或计算这样的纯粹抽象的数学概念看作物理定律的体现, 把计算系统看作自然定律的一个自然结果。特别是认为,丘奇- 图灵论题也同时断定了一条物理原理,这就是 1985 年多奇() 提出的丘奇- 图灵论题的物理版本( 也称多奇原理)。正是基于这一原理, 量子计算机的计算本质成为 199 0 1 计算机专家断言, 计算机的复杂性遵循摩尔定律:每 18 个月将翻一番。年以来人们关注的热点。我们认为, 在当今对认知科学中认知可计算主义研究纲领提出质疑时, 更有必要澄清关于丘奇- 图灵论题和多奇原理的内涵, 也有必要对量子计算机的计算本质作出恰当的逻辑分析。 1 哥德尔为什么没有提出丘奇论题历史上,狄特金() ,皮