邱奇-图灵论题
邱奇-图灵论题（The Church-Turing thesis）是计算机科学中以数学家阿隆佐•邱奇(Alonzo Church)和阿兰•图灵命名的论题。该论题最基本的观点表明，所有计算或算法都可以由一台图灵机来执行。以任何常规编程语言编写的计算机程序都可以翻译成一台图灵机，反之任何一台图灵机也都可以翻译成大部分编程语言程序，所以该论题和以下说法等价：常规的编程语言可以足够有效的来表达任何算法。该论题被普遍假定为真，也被称为邱奇论题或邱奇猜想 和图灵论题。
目录
• 1 本论题之等价形式
• 2 本论题之起源
• 3 本论题之成功
• 4 哲学内涵
• 5 补充材料
• 6 参考文献
本论题之等价形式
本论题的另外一种说法就是逻辑和数学中的有效或机械方法可由图灵机来表示。通常我们假定这些方法必须满足以下的要求：
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)所展示的正整数函数那样。在听说了邱奇的建议后，图灵很快就证明了他的图灵机实际上描述的是同一集合的函数(Turing 1936, 263ff).y
本论题之成功
之后用于描述有效计算的许多其他机制也被提了出来，比如寄存器机器(register machine), 埃米尔•波斯特(Emill Post)的波斯特体系，组合可定义性(combinatory definability)以及马尔可夫算法(Markov 1960)等。所有这些体系都已被证明在计算上和图灵机拥有基本相同的能；类似的系统被称为图灵完全。因为所有这些不同的试图描述算法的努力都导致了等价的结果，所以现在普遍认为邱奇-图灵论题是正确的。但是，该论题不具有数学定理一般的地位，也无法被证明；如果能有一个方法能被普遍接受为一个有效的算法但却无法在图灵机上允许，则该论题也是可以被驳斥的。
在20世纪初期，数学家们经常使用一种非正式的说法即可有效计算，所以为这个概念寻找一个好的形式描述也是十分重要的。当代的数学家们则使用图灵可计算(或简写为可计算)这一定义良好的概念。由于这个没有定义的用语在使用中已经淡去，所以如何定义它的问题几经不是那么重要了。
哲学内涵
邱奇-图灵论题对于心智哲学(philosophy of mind)有很多寓意。有很多重要而悬而未决的问题也涵盖了邱奇-图灵论题和物理学之间的关系，还有超计算性(hypercomputation)的可能性。应用到物理学上，该论题有很多可能的意义：
1. 宇宙是一台图灵机(由此，在物理上对非递归函数的计算是不可能的)。此被定义为大邱奇-图灵论题。
2. 宇宙不是一台图灵机(也就是说，物理的定律不是图灵可计算的)，但是不可计算的物理事件却不能阻碍我们来创建 超计算机(hypercomputer)。比如，一个物理上实数作为可计算实数的宇宙就可以被划为此类。
3. 宇宙是一台超计算机, 因为建造物理设备来控制这一特征并来计算非递归函数是可能的。比如，一个悬而未决的问题是量子力学的的事件是图灵可计算的，尽管我们已经证明了任何由qubit所构成的系统都是(最佳)图灵完全的。约翰•卢卡斯(和罗格•本罗泽(Roger Penrose)曾经建议说人的心灵可能是量子超计算的结果。
实际上在这三类之外或其中还有许多其他的技术上的可能性，但这三类只是为了阐述这一概念。
补充材料
• Hofstadter, Douglas R., Gödel, Escher, Bach: an Eternal Golden Braid, Chapter 17.
参考文献
• Church, A., 1932, "A set of Postulates for the Foundation of Logic", Annals of Mathematics, second series, 33, 346-366.
• Church, A., 1936, "An Unsolvable Problem of Elementary Number Theory", American Journal of Mathematics, 58, 345-363.
• Church, A., 1936, "A Note on the Entscheidungsproblem", Journal of Symbolic Logic, 1, 40-41.
• Church, A., 1941, The Calculi of Lambda-Conversion, Princeton: Princeton University Press.
• Gödel, K., 1934, "On Undecidable Propositions of Formal Mathematical Systems", lecture notes taken by Kleene and Rosser at the Institute for Advanced Study, reprinted in Davis, M. (ed.) 1965, The Undecidable, New York: Raven.
• Herbrand, J., 1932, "Sur la non-contradiction de l'arithmetique", Journal fur die reine und angewandte Mathematik, 166, 1-8.
• Kleene, S.C., 1935, "A Theory of Positive Integers in Formal Logic", American Journal of Mathematics, 57, 153-173, 219-244.
• Kleene, S.C., 1936, "Lambda-Definability and Recursiveness", Duke Mathematical Journal 2, 340-353.
• Markov, A.A., 1960, "The Theory of Algorithms", American Mathematical Society Translations, series 2, 15, 1-14.
• Turing, A.M., 1936, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, 42 (1936-37), pp.230-265.
• Pour-El, M.B. & Richards, J.I., 1989, Computability in Analysis and Physics, Springer Verlag.
[返回] 中文XML论坛 - 专业的XML技术讨论区 →
计算机理论与工程 → 『 理论计算机科学 』 → 数理逻辑大师们[转帖]
(订阅本版)
2006/4/18 15:23:00
新浪微博
顶端