《church论题》word版

《《church论题》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、Church论题Church论题2010年05月26日星期三下午09：24在理论计算机科学中，有了可计算性概念严格的数学刻划，才使证明一系列重要的数学问题的算法不可解性成为可能。一个众所周知的事实是，直到1935年著名的"算法可计算函数都是递归函数"这一丘奇论题提出，算法可计算性这个直观概念才有了精确的数学刻划。而同样需要指出的是，哥德尔(K.Gdel)在此之前的1931年就引进了原始递归函数概念，1934年明确给出一般递归函数的定义，1934年春还曾与丘奇(A.Church)一起讨论如何给"算法可计算性"下一个精确的数学定义的问题

2、。那么，为什么哥德尔没有适时给出丘奇论题，却对图灵工作大加赞赏，从而接受丘奇-图灵论题呢?我们认为，其中的最重要原因是，图灵是完全沿着哥德尔设想的思路对算法概念给出分析的第一人，图灵机概念澄清了形式系统概念的内涵；同时，与波斯特20年代的想法一样，图灵论题通过指出机器能做什么，把计算系统引入了物理世界，引发了一场信息革命和心-脑-计算机的大论战。而且图灵论题揭示了哥德尔认识到的，可计算性是一个不依赖于形式系统的绝对概念这一事实。随着"计算机的发展遵循摩尔定律"这一假说被普遍认可，哥德尔对图灵工作大加赞赏的几个因素更加显示出对计算机发

3、展的理论意义和现实意义。1980年代人们开始讨论如何"超越图灵计算"，将算法或计算这样的纯粹抽象的数学概念看作物理定律的体现，把计算系统看作自然定律的一个自然结果。特别是认为，丘奇-图灵论题也同时断定了一条物理原理，这就是1985年多奇(D.Deutsch)提出的丘奇-图灵论题的物理版本(也称多奇原理)。正是基于这一原理，量子计算机的计算本质成为1990年以来人们关注的热点。我们认为，在当今对认知科学中认知可计算主义研究纲领提出质疑时，更有必要澄清关于丘奇-图灵论题和多奇原理的内涵，也有必要对量子计算机的计算本质作出恰当的逻辑分析。

4、1哥德尔为什么没有提出丘奇论题历史上，狄特金(R.Dedekind)，皮亚诺(G.Peano)，司寇伦(T.Skolem)，希尔伯特(D.Hilbert)和阿克曼(W.Ackermann)都曾研究过递归函数，但哥德尔是第一个精确定义这个概念的。今天我们所称的"原始递归函数"是哥德尔1931年在那篇划时代的论文中引进的。1934年2-5月，哥德尔在普林斯顿研究院关于不完全性结果的系列讲座中又引进了一般递归函数概念，指出："一般递归函数(我们现在称原始递归函数)有着重要的特性，即对于每个给定的自变量值的集合，都能通过有穷程序计算出函数值

5、。"具有历史意谓的是哥德尔还对此补充了一个颇具建设性的说明(著名的脚注3)："这个命题的逆[即每个通过有穷程序计算的函数都是原始递归函数]似乎也是真的，除了[原始]递归，…其他形式的递归(例如与带两个变量的加法相对应的递归)是否也是允许的。由于有穷可计算的概念还没有定义，目前不可能证明这个命题的逆，但是，它完全可以充当一种助探原则。"[6]哥德尔的这段脚注曾被戴维斯(MartinDavis)认为是丘奇论题的一种形式。他甚至以"哥德尔论题"的名称对其重新做了表述："每个机械可计算函数都可用一般递归函数定义"。在准备编进《不可判定的》论

6、文集的一篇介绍哥德尔讲座的短文中，戴维斯表达了他的这一见解，并将初稿寄给哥德尔进行评价。完全出乎戴维斯意料的是，哥德尔在回信中对此表达了不同见解："…说脚注3是丘奇论题的一种陈述是不正确的。我无非是提出了'有穷可计算程序'与'递归程序'是等价的一种猜想。但在系列讲座中我根本没有料想到，我的递归概念包含了所有可能的递归。"[3]从这封信中至少我们可以看出，哥德尔1934年春就给出今天意义上的"递归函数"的定义了，但是他完全没有猜到他当时的定义足够宽，可以包容所有的递归。而且他认为，自己对算法可计算性的猜测(即戴维斯所说的"哥德尔论题"

7、)并不是丘奇论题的等价说法，但它可以充当一种助探原则，帮助人们寻求算法可计算性概念的一个令人满意的数学刻划。2从l可定义性到丘奇论题丘奇是在1935年4月美国数学会的一次报告中宣布他的论题的。事实上，丘奇最早关注可计算性是从l可定义性概念着手的。据当年丘奇的学生克林尼(S.C.Kleene)的说法，到了1933年，丘奇的"l可定义性"已经作为一个成熟的概念在普林斯顿的逻辑学家中流传。他当时猜测，l可定义函数就是算法可计算函数，并最终提出这一论题。后来，克林尼曾回忆说："当丘奇提出这一论题时，我准备用对角化方法否证它，希望指出算法可计

8、算函数超出了l可定义函数类。但是我很快认识到做不到这一点。于是，一夜之间我成了丘奇这个论题的支持者。"[9]据戴维斯考察，尽管丘奇1933-1934年明显对可计算性概念怀有浓厚兴趣，但直到哥德尔作普林斯顿系列讲座之前，没有明显的迹象表