人工智能名人堂第16期 | 数理逻辑大师-阿隆佐·邱奇
丘吉尔曾说过，“The longer you can look back, the farther you can look forward. (回顾历史越久远，展望未来就越深远)”，为纪念人工智能领域做出杰出贡献的先辈与开拓者们，鼓励更多后起之秀投身该领域，人工智能国际杂志《IEEE Intelligent Systems》自2006年始至今陆续推选出了60位人工智能专家(参看《诺伯特·维纳奖得主王飞跃 | AI 名人堂，世界人工智能60年60位名人榜》)。德先生自10月31日起，已定期于每周一在微信公众号（D-Technologies）上发布人工智能名人堂60位成员的相关介绍。往期内容可查看延伸阅读。
人工智能的火热使很多人知道了阿兰·图灵和约翰·冯·诺伊曼。阿兰·图灵提出了图灵机的概念，约翰·冯·诺伊曼基于这一理论，设计出了第一台现代计算机。由于图灵以及冯·诺伊曼式计算机的大获成功，历史差点淹没了另外一位同样杰出的科学家和他的理论，那就是阿隆佐·邱奇和他的λ演算。阿隆佐·邱奇是阿兰·图灵的老师，上世纪三十年代，他们一起在普林斯顿研究可计算性问题，为了回答这一问题，阿隆佐·邱奇提出了λ演算，其后不久，阿兰·图灵提出了图灵机的概念，尽管形式不同，但后来证明，两个理论在功能上是等价的，条条大路通罗马。如果不是约翰·麦卡锡，阿隆佐·邱奇的λ演算恐怕还要在历史的故纸堆中再多躺几十年，约翰·麦卡锡是人工智能科学的奠基人之一，他发现了λ演算的珍贵价值，发明了基于λ演算的函数式编程语言：Lisp，由于其强大的表达能力，一推出就受到学术界的热烈欢迎，以至于一段时间内，Lisp 成了人工智能领域的标准编程语言。很快，λ演算在学术界流行开来，出现了很多函数式编程语言：Scheme 、SML、Ocaml 等，但是在工业界，还是命令式编程语言的天下，Fortran、C、C++、Java 等。随着时间的流逝，越来越多的计算机从业人员认识到函数式编程的意义，爱立信公司于上世纪八十年代开发出了 Erlang 语言来解决并发编程的问题；在互联网的发展浪潮中，越来越多的语言也开始支持函数式编程：JavaScript、Python、Ruby、Haskell、Scala 等。
邱奇-图灵论题
邱奇-图灵论题（The Church-Turing thesis）是计算机科学中以数学家阿隆佐•邱奇和阿兰•图灵命名的论题。该论题最基本的观点表明，所有计算或算法都可以由一台图灵机来执行。以任何常规编程语言编写的计算机程序都可以翻译成一台图灵机，反之任何一台图灵机也都可以翻译成大部分编程语言程序，所以该论题和以下说法等价：常规的编程语言可以足够有效的来表达任何算法。该论题被普遍假定为真，也被称为邱奇论题或邱奇猜想和图灵论题。
本论题之等价形式
本论题的另外一种说法就是逻辑和数学中的有效或机械方法可由图灵机来表示。通常我们假定这些方法必须满足以下的要求：
1.一个方法由有限多简单和精确的指令组成，这些指令可由有限多的符号来描述。
2. 该方法总会在有限的步骤内产生出一个结果。
3. 基本上人可以仅用纸张和铅笔来执行。
4. 该方法的执行不需人类的智慧来理解和执行这些指令。
此类方法的一个范例便是用于确定两个自然数的最大公约数的欧基里德算法。
“有效方法”这个想法在直觉上是清楚的，但却没有在形式上加以定义，因为什么是“一个简单而精确的指令”和什么是“执行这些指令所需的智力”这两个问题并没有明确的答案。 (如需欧几里得算法之外的范例，请参见数论中的有效结果。)
本论题之起源
在他1936年的论文“论可计算数字，及其在判定性问题(Entscheidungsproblem--德语，译者注)中的应用”中，阿兰•图灵试图通过引入图灵机来形式地展示这一想法。在此篇论文中，他证明了“判定性问题”是无法解决的。几个月之前，阿隆佐•邱奇在“关于判定性问题的解释”(A Note on the Entscheidungsproblem)一文中证明出了一个相似的论题，但他采用但是递归函数和Lambda可定义函数来形式地描述有效可计算性。Lambda可定义函数由阿隆佐•邱奇和史蒂芬•克林(Stephen Kleene) (Church 1932, 1936a, 1941, Kleene 1935)提出，而递归函数由库尔特•歌德尔(Kurt Gödel)和雅克斯•赫尔不兰特(Jacques Herbrand) (Gödel 1934, Herbrand 1932)提出。这两个机制描述的是同一集合的函数，正如邱奇和克林(Church 1936a, Kleene 1936)所展示的正整数函数那样。在听说了邱奇的建议后，图灵很快就证明了他的图灵机实际上描述的是同一集合的函数。
本论题之成功
之后用于描述有效计算的许多其他机制也被提了出来，比如寄存器机器(register machine), 埃米尔•波斯特(Emill Post)的波斯特体系，组合可定义性(combinatory definability)以及马尔可夫算法(Markov 1960)等。所有这些体系都已被证明在计算上和图灵机拥有基本相同的能；类似的系统被称为图灵完全。因为所有这些不同的试图描述算法的努力都导致了等价的结果，所以现在普遍认为邱奇-图灵论题是正确的。但是，该论题不具有数学定理一般的地位，也无法被证明；如果能有一个方法能被普遍接受为一个有效的算法但却无法在图灵机上允许，则该论题也是可以被驳斥的。
在20世纪初期，数学家们经常使用一种非正式的说法即可有效计算，所以为这个概念寻找一个好的形式描述也是十分重要的。当代的数学家们则使用图灵可计算(或简写为可计算)这一定义良好的概念。由于这个没有定义的用语在使用中已经淡去，所以如何定义它的问题几经不是那么重要了。
哲学内涵
邱奇-图灵论题对于心智哲学(philosophy of mind)有很多寓意。有很多重要而悬而未决的问题也涵盖了邱奇-图灵论题和物理学之间的关系，还有超计算性(hypercomputation)的可能性。应用到物理学上，该论题有很多可能的意义：
1.宇宙是一台图灵机(由此，在物理上对非递归函数的计算是不可能的)。此被定义为大邱奇-图灵论题。
2. 宇宙不是一台图灵机(也就是说，物理的定律不是图灵可计算的)，但是不可计算的物理事件却不能阻碍我们来创建 超计算机(hypercomputer)。比如，一个物理上实数作为可计算实数的宇宙就可以被划为此类。
3. 宇宙是一台超计算机, 因为建造物理设备来控制这一特征并来计算非递归函数是可能的。比如，一个悬而未决的问题是量子力学的的事件是图灵可计算的，尽管我们已经证明了任何由qubit所构成的系统都是(最佳)图灵完全的。约翰•卢卡斯(和罗格•本罗泽(Roger Penrose)曾经建议说人的心灵可能是量子超计算的结果。
实际上在这三类之外或其中还有许多其他的技术上的可能性，但这三类只是为了阐述这一概念。
声明：文章来源于网络，版权归原作者所有，如有侵权，请联系小编删除！
延伸阅读
德先生精彩文章回顾
在公众号会话位置回复以下关键词，查看德先生往期文章！
人工智能｜类脑研究｜人机大战｜机器人
虚拟现实｜无人驾驶｜智能制造｜无人机
科研创新｜网络安全｜数据时代｜区块链
……
更多精彩文章正在赶来，敬请期待！
点击“阅读原文”，移步求知书店，可查阅选购德先生推荐书籍。