算法概念的流变
     “算法”（algorism）一词最早来自9世纪波斯数学家比阿勒.霍瓦里松的一本影响深远的著作《代数对话录》，后来这个词改成algorithm多半是由于它和算术相关联了。本世纪30年代以前算法还只是一个直观的概念，人们直观上理解的算法就是在有限的时间内，可以根据明确规定的运算规则，在有穷步骤内得出确切计算结果的机械步骤或能行可计算程序。人们最熟悉的经典算法是公元前300年欧几里得关于求两个数的最大公约数的辗转相除法。1928年希尔伯特在波伦亚国际数学家大会上提出一个具有挑战性的判定问题：是否存在一般的能在原则上一个接一个地解决所有（属于某种适当定义的类的）数学问题的机械步骤？这里的“机械步骤”实际上就是“算法”和“可计算程序”的直观概念。1936年英国数学家图灵（A.M.Turing）通过引进“图灵机”概念，给出算法概念严格的数学表达，并指出“算法可计算函数”即“用图灵机可计算的函数”。

     事实上，在此之前，1934年在普林斯顿的一次演讲中，根据艾尔布朗（Herbrand,J.）的建议哥德尔就提出了“一般递归函数”的概念，其后，经克利尼改进作为不完全性定理研究的副产品成为可计算概念的一种数学表述。在图灵之前美国逻辑学家丘奇（A.Church）为解决希尔伯特判定问题提出了“λ可定义函数”概念。稍晚一些的则有波兰美国逻辑学家波斯特（E.Post）的“波斯特演算”以及马尔可夫“正规算法”等关于算法概念的不同表达。1935年丘奇指出，“算法可计算的函数都是λ－可定义函数”和“算法可计算的函数都是递归函数”，这就是著名的“丘奇论题”，而图灵独立提出的“一切算法可计算函数都是图灵机可计算函数”的论断称为“图灵论题”。事实上，人们发现“λ可定义函数”、“一般递归函数”、“图灵机可计算函数”、“波斯特演算”等都是与“算法可计算的函数”这个直观概念等价的数学表述。
     正是有了算法概念的精确表述，数学家很快证明了不存在解决所有数学问题的一般算法，希尔伯特的判定问题只有否定解！1936年以来人们具体证明了一大批重要的判定问题的不可解（例如谓词演算的判定、停机问题的判定、半群上字的等价性的判定、丢番图方程可解性的判定等）。更重要的是，正是算法概念精确的数学表述使现代意义上的电子计算机得以产生。
     据说，哥德尔1934年到普林斯顿时，这些结果正在普林斯顿的逻辑学家中间流传,但哥德尔一直主张，只有首先清楚地表述一组公理，使它们能体现公认的关于可计算性或机械程序这一直观概念的基本特性，才能找到算法概念的精确定义。1934年在与丘奇的讨论中他谈到了能行可计算性和递归性的关系问题，但没有猜想到他的递归概念包括了全部的递归,因此不认为自己引进的一般递归函数概念能与直观的可计算性概念等价，他说,除非从“助探的观点看”,否则就不能把这两个概念等同视之。而且很长时间哥德尔都对丘奇论题表示怀疑，却对图灵机概念大加赞扬，认为图灵机的定义完全刻画了直观可计算性概念。当时哥德尔并没有意识到，能行可计算性函数既等价于图灵可计算函数，也等价于λ可定义函数和他自己的一般递归函数概念。今天“算法”已经演变为计算机所能模拟的一切，包括“并行计算”、“神经网络”、“启发”、“学习”及学习与环境的作用等。

3. 鲁卡斯论证和彭罗斯论证
    关于心脑计算机关系问题的争论也许最早的可见波斯特关于人心比机器优越的猜想。1921年，波斯特推断：“数学家远远不只比机器更灵巧，能更快地做到机器最终可以做到的事情。我们看到，机器永远不可能提出完备的逻辑，因为机器一旦造成，我们总能证明一个它不能证明的定理。”(据说20年代波斯特在哥伦比亚大学作了关于PM的不完全性的讲座)不久，经过斟酌之后波斯特又修正了这个“看似草率”的推论：“‘人不是机器’这个结论不能成立。我们所能说的只是，人无法制造一台能进行人的所有思维的机器。要说明这一点，我们可以想象制造一台能够证明其自身心理运作的人机复合体。”事隔十几年，1936年图灵在《伦敦数学会通报》上发表了一篇重要文章《论可计算数》，其中指出，“我们将假定需要计数的心的状态数是有穷的。这是因为，如果我们承认心的状态有无穷多，它们中的某些状态就会由于‘任意接近’而被混淆”。图灵的这段话当时曾被看作“人类心智活动不可能超越任何机械程序”的一个论证。1950年图灵又在《心》（Mind）杂志上发表了一篇题为《计算机与心智》的文章，开篇写道：“我准备考虑一个问题：机器能思维吗？”，并提出了著名的“图灵检验”的概念。文章隐含着“人心等价于一台计算机”的论断，这一论断对40年代后期刚刚兴起的人工智能方案无疑是一强有力的声援，也自然引起了一场大争论。在这场争论中反对派中的一些哲学家和逻辑学家更热衷于以哥德尔定理为依据反对图灵的论断。
    人们确实很难抵御一种强烈的诱惑：从哥德尔的不完全性定理出发证明“人心胜过计算机”这一论断。1961年美国哲学家鲁卡斯（JohnLucas)在36卷《哲学》 (Philosophy）杂志上以极其激烈的言辞首先撰文《心、机器、哥德尔》，试图用哥德尔定理证明“人心超过计算机”的结论:“依我看，哥德尔定理证明了机械论是错误的，也就是说，心不能解释成机器。”因为，“无论我们造出多么复杂的机器，只要它是机器，就将对应于一个形式系统，接着就能找到一个在该系统内不可证的公式而使之受到哥德尔构造不可判定命题那种程序的打击，机器不能把这个公式作为定理推导出来，但是人心却能看出它是真的。因此这台机器不是心的一个恰当模型。人们总想制造心的一种机械模型，即从本质上是‘死’的模型，而心是‘活’的，它总能比任何形式的、僵死的系统干得好”。这就是著名的鲁卡斯论证.
    随后，另一位美国哲学家怀特利（C.H.Whitely）在接下来的37卷《哲学》杂志上发表了虽简短但强有力的批驳文章《心、机器、哥德尔,回应鲁卡斯》，遂引起许多人卷入并长达几十年的争论(例如伯纳塞拉夫(Benacerruf),普特南(Putnam),奇哈若(Chihara),吉利斯(D.Gillies)等人)。
    1979年获得普利策文学大奖的美国畅销书《哥德尔、艾舍、巴赫,一条永恒的金带》将艾舍尔义蕴深刻的绘画、巴赫脍炙人口的乐章及哥德尔定理以一种独特的方式连接起来，以极大的视觉冲击效果极具戏剧性地谱写了一曲心脑计算机的“隐喻赋格曲”，从多个视角试图阐明如何用哥德尔定理否证人工智能方案的观点.

    1989年,英国数学家、物理学家罗杰·彭罗斯 （Roger Penrose）在那本风靡全球 的《皇帝新脑,计算机、心智和物理定律》中,首先对鲁卡斯论证作了扩展,并以大量笔墨试图从哥德尔定理出发直接论证“人心超过计算机”的结论，被称为“对哥德尔定理令人吃惊的强应用。”因此在1990年的《行为和大脑科学》杂志第13卷上，借评价该书的机会重又引发了许多人介入的一场争论。彭罗斯的一个强硬论证是：根据哥德尔定理可以“像在数学中所做的那样，严格证明”数学真理的概念不可能包容于形式主义的框架之中，数学真理是某种超越纯粹形式主义的东西，人类判断数学真理的过程是超越任何算法的。这是因为，意识是我们赖以理解数学真理的关键，这种意识使我们能够借直觉的洞察力“看出”（see）某些在数学形式系统中不能证明的数学命题的真理性，而这种意识是不能被形式化的，它必定是非算法的。因此计算机绝不可能超越人类心智，计算机不过是强人工智能专家所钟爱的一副“皇帝新脑”而已。