奇数和教会制的数学概念是什么？
在我们看来，最重要的原因是图灵是第一个完全沿着哥德尔思想分析算法概念的人，图灵机的概念阐明了形式系统概念的内涵；同时，与波斯特在20世纪20年代的想法一样，图灵通过指出机器能做什么，将计算系统引入物理世界，引发了一场信息革命和一场关于心-脑-计算机的大辩论。而且，图灵的论文揭示了一个事实，即哥德尔意识到可计算性是一个不依赖于形式系统的绝对概念。
随着“计算机的发展遵循摩尔定律”这一假设被普遍接受，哥德尔极力推崇图灵工作的几个因素对计算机的发展显示出更多的理论和实践意义。在1980年代，人们开始讨论如何“超越图灵计算”，将算法或计算等纯粹抽象的数学概念视为物理规律的体现，将计算系统视为自然规律的自然结果。特别是认为丘奇-图灵命题还得出一个物理原理，这是D .多伊奇在1985中提出的丘奇-图灵命题的物理版本(也称奇原理)。正是基于这一原理，量子计算机的计算本质从1990开始成为人们关注的焦点。我们认为，在对认知科学中认知可计算性的研究纲领提出质疑时，更有必要澄清丘奇-图灵命题和奇性原理的内涵，也有必要对量子计算机的计算本质进行恰当的逻辑分析。
1哥德尔为什么没有提出教会这个话题？
历史上，R.Dedekind，G .阿砣，T.Skolem，D.Hilbert和W.Ackermann都研究过递归函数，但哥德尔是第一个准确定义这个概念的人。我们今天所说的“原始递归函数”，是哥德尔在1931那篇划时代的论文中介绍的。1934年2月至5月，哥德尔在普林斯顿学院关于不完全结果的系列讲座中引入了一般递归函数的概念，指出:
“一般的递归函数(我们现在称之为原递归函数)有一个重要的特点，就是对于给定的每一组自变量值，都可以通过有限的程序计算出函数值。”
历史意义在于，哥德尔还补充了一个非常有建设性的解释(著名的脚注3):
“这个命题的逆命题[即有限程序计算的每一个函数都是原递归函数]似乎成立。除了[原始]递归之外，是否允许其他形式的递归(比如对应于两个变量相加的递归)？因为有限可计算性的概念还没有定义，目前还无法证明这个命题的逆，但完全可以作为一个帮助探索的原则。”[6]
哥德尔的脚注曾被马丁·戴维斯认为是教会论文的一种形式。他甚至以“哥德尔论题”的名义重述了这一点:
“每一个机械可计算函数都可以由一个一般的递归函数来定义”。
在一篇介绍哥德尔讲座的论文中，戴维斯表达了自己的观点，并将初稿送交哥德尔评估，这篇论文将被编入《不可确定论文集》。令戴维斯惊讶的是，哥德尔在回信中表达了不同的意见:
"...说脚注3是对教会论题的陈述是不正确的。我只是提出一个猜想，‘有限可计算程序’和‘递归程序’是等价的。但在系列讲座中，我没想到我的递归概念包含了所有可能的递归。”[3]
从这封信中，至少可以看出哥德尔在1934的春天给出了今天意义上的“递归函数”的定义，但他并没有猜想到他当时的定义已经宽到可以包含所有的递归。而且，他认为他关于算法可计算性的猜想(即戴维斯的“哥德尔论题”)并不等同于丘奇的论题，但它可以作为一个探测原理，帮助人们找到算法可计算性概念的满意的数学描述。
2从l可定义性到教会论题
丘奇在1935年4月美国数学学会的一份报告中公布了他的论文。其实丘奇最早关注可计算性是从l可定义的概念开始的。根据丘奇的学生S.C.Kleene的说法，到1933，丘奇的“l可定义性”已经作为一个成熟的概念在普林斯顿的逻辑学家中流传。当时他猜测L可定义函数就是算法可计算函数，最后提出了这个题目。后来，柯林尼曾回忆说:
“丘奇提出这个题目的时候，我准备用对角化的方法来证明，希望指出算法的可计算函数超出了L个可定义的函数类。但我很快意识到我做不到。于是，一夜之间，我成了教会话题的支持者。”[9]
根据戴维斯的调查，虽然丘奇在1933-1934中对可计算性的概念有明显的兴趣，但直到哥德尔在普林斯顿的一系列讲座中，没有明显的迹象表明他认为算法的可计算性符合某种严格的数学概念，对此也没有特别的说法。也许是在1934年2月到5月与哥德尔讨论之后，形成了明确的意见，给出了后来的教会论文。1935 165438+10月29日，丘奇在给克林特尼的信中，对此给出了一个有些模糊的说法:
“说起哥德尔、递归函数、算法可计算性这些概念，这段历史原来是这样的。在和Godel讨论L可定义性的概念时，我们发现找不到一个好的算法可计算性的定义。我提出L可定义性可以作为定义，但是哥德尔认为完全不合适。我回答说，如果你能提供任何一个定义，哪怕是部分满意的，我都会证明它一定包含在L可定义的概念中。当时哥德尔唯一的想法就是把算法可计算性当作一个不确定的概念，陈述一个可以描述这个概念的公认特征的公理集，然后在这个基础上做其他的事情。显然，他后来认为J.Herbrand提出的递归函数概念可以沿着可计算性的方向修正。他特别指出递归和算法的可计算性可以在这个意义上联系起来。然而，他补充说，他不认为这两个概念可以令人满意地证实彼此一致，除非在某种意义上有助于探索。”[3]
丘奇在1935向数学界宣布他的课题时，是这样表达的:“采纳厄尔·布朗的建议，在一个重要的方面做一些修正。哥德尔在1934系列讲座中提出了递归函数的定义，基本采用了哥德尔对正整数递归函数的定义，需要强调的是，正整数的算法可计算函数将被确定为与递归函数一致。因为其他关于算法可计算性的似是而非的定义，原本都是派生概念，要么等同于递归，要么弱于递归。”[3]
显然，丘奇并没有选择使用“l可定义”这个术语来陈述他的论题，而是使用了“Elbrown-Godel一般递归函数”这个术语。在这里，L的可定义性隐含在“其他算法的可计算性的似是而非的定义”中。这种措辞给人的感觉是，在1935的春天，丘奇还没有决定L的可定义性等价于厄尔·布朗-哥德尔的一般递归。直到1936年4月，丘奇才在初等数论中的一个无解问题中，得出L可定义函数是一般递归函数的结论。
在1936的论文中，丘奇给出了我们现在所知的丘奇论文的标准表述:“现在我们通过符合正整数递归函数(或正整数L可定义函数)的概念来定义正整数的算法可计算性概念。这种符合可计算性直观概念的选定定义被认为已经得到验证。”[1]
在这里，丘奇把算法的可计算性和递归性之间的这种等价关系称为“定义”，Post (E.Post)1936强烈反对定义的提法，认为应该只把它当作一个工作假设。在1943中，Clinney指出描述这种等价的命题包含了强工作假说的特征，尽管我们确实有充分的理由相信它。所以建议用“论题”这个术语来表达这个命题。
虽然提出了丘奇的论题，但哥德尔当时并不认同可计算性等同于递归或l可定义性。在他看来，在公理化表征算法的可计算性概念的一组公认特征被找到之前，不可能有一个完全令人满意的、严格的数学定义。直到A.Turing在1936的结果发表后，哥德尔才承认这个困难已经被克服了。
哥德尔为什么欣赏图灵的论文？
我们认为，正是因为1934-1936，丘奇、柯林尼和哥德尔在可计算性概念的数学描述上做了一系列工作，最后丘奇提出了他的丘奇论题的标准形式。同时，图灵对可计算性的思考完全独立于普林斯顿数学家，最终用泛图灵机的概念来描述算法的可计算性，即“算法能计算的就是泛图灵机能实现的”。可以表述为以下“图灵命题”:
"每种算法都可以在通用图灵机上编程."
在1965年出版的《普林斯顿讲义(1934)》的后记中，哥德尔高度评价了图灵的工作。我们认为，哥德尔不接受教会命题，而赞赏图灵命题，至少有几个主要原因:
(1)泛图灵机的概念澄清了形式系统的概念。
可以说，当哥德尔证明不完全性定理时，形式系统还是一个相当模糊的概念，否则哥德尔会用更简洁的方式证明他的定理。正是图灵机的概念使形式系统的特征更清晰、更准确地被人们所把握。形式系统只是一个产生定理的机械程序，图灵机的工作程序恰恰是数学家在形式系统中实际工作的程序。换句话说，形式系统只是一个图灵机，让你按照预定的范围，在某些步骤中做出选择。当然，正是因为图灵机的概念，哥德尔关于数学形式系统的不完全性定理才产生了图灵机程序用来代替形式系统的各种版本，比如停机问题的版本，以及算法信息论中复杂性的后来版本。[10]
(2)图灵是沿着最接近哥德尔思想的研究途径得出他的结论的。
虽然丘奇的工作精致优雅，但他完全基于纯数学分析。图灵的分析并不局限于数学的形式世界，它是一个值得称赞的哲学应用的例子。[3]此外，图灵是沿着最接近哥德尔设想的研究方法得出他的结论的。哥德尔曾评价“图灵的工作给出了对‘机械程序’(又称‘算法’、‘计算程序’或‘组合程序’)概念的分析，指出这个概念相当于‘图灵机’”。然而，之前给出的可计算性的其他等价定义“无论如何很少适合我们最初的目的”。[2]
那么，哥德尔的“最初目的”是什么？显然，他一直主张“把算法的可计算性看作一个未定义的概念，给出一个能描述这个概念的公认特征的公理集，然后有所作为”。在他看来，这才是寻求可计算性的严格数学描述的真正途径。虽然图灵没有使用任何形式意义上的公理化方法来处理问题，但他指出“算法可计算性的公认特征”必然导致某种函数类，这种函数类是可以精确定义的。图灵的图灵机，清晰准确地表达了机械程序的概念，是指产生部分递归函数的图灵机，而不是一般的递归函数。因此，在哥德尔看来，图灵是第一个给出精确概念与直观概念相一致的令人信服的理由的人。用“在图灵机上可编程”或“在图灵机上可实现”这种鲜明的概念来描述算法的可计算性，既正确又符合我们的初衷。
(3)图灵机可计算性的概念揭示了可计算性独立于形式系统的事实。
为了让我们进一步看到为什么图灵的工作对哥德尔如此重要，我们还应该考察哥德尔对绝对可计算性概念的理解。6月1935，19日哥德尔在维也纳大学报告《论证明的长度》，提到所谓的“加速定理”。[7]定理的严格陈述使用了一个函数φ(x)在形式系统S中是可计算的概念，这意味着对于每一个数m，都有一个对应的数n，所以φ(m)= n在系统中是可证的。对于序列S1，S2、...其中满足形式系统的每一个系统都比前一个系统强，这意味着一个函数在Si中是可计算的，这意味着它依赖于I..
在这篇报告中，哥德尔补充了一个关于“绝对可计算性”的注释:“可以指出，一个可以在形式系统之一的Si中，甚至在超差类型中计算的函数，在S1中已经是可计算的了。因此，从某种意义上来说，‘可计算性’这个概念是‘绝对的’，而现实中所有其他众所周知的元数学概念(如可证明的和可定义的)都完全依赖于给定的系统。”
哥德尔对这种“绝对”意义上的可计算性的理解大致在1934-1935，1946，在《在普林斯顿200周年纪念日关于数学问题的讲话》中，哥德尔特别强调了这种“绝对”的意义:
“在我看来，一般递归或图灵机可计算性概念的极端重要性似乎在很大程度上归功于这样一个事实，即借助这个概念，它第一次成功地给出了有意义的认识论概念的绝对定义，即可计算性不依赖于形式系统的选择。但是在之前处理的所有其他情况下，例如定义可判定性或可定义性，这取决于给定的语言。虽然绝对可计算性只是一种特殊的可判定性概念，但情况与过去完全不同。”[8]
(4)图灵机的概念将计算系统引入物理世界。
哥德尔值得称赞图灵工作的另一个原因可能是，与波斯特在20世纪20年代的想法一样，图灵通过指出计算机器可以做什么，将计算系统引入了物理世界，或者换句话说，将一个可计算的问题变成了物理上可实现的问题，从而引发了一场信息革命和一场关于心-脑-计算机的大辩论。图灵实际上指出，任何可以形式化描述和算法化处理的东西，都可以作为通用图灵机的特例，被计算机快速准确地处理。这个原理开启了机器模拟人类智能的新时代。正如图灵在他的文章《可数的数》中所说，他研究可计算性的动机不仅仅是形式上的，而是“心智科学”。即使在晚年，哥德尔仍然对讨论图灵提出的心灵-大脑-计算机的话题感兴趣，这可能表明他喜欢心理科学。
丘奇-图灵命题的物理版本与量子计算机的计算本质
哥德尔对图灵工作的赞赏恰恰是现代理论计算机发展的基础和动力。当第一台通用电子计算机诞生时，人们才真正看到了通用图灵机的物理实现(虽然没有无限存储)。从此，人们开始思考，现实世界本身是可计算的吗？模拟客观现实的理想模拟机是在原理上物理上可实现的，还是客观世界完全超出了一般图灵机模拟的范围？对此，相当一部分物理学家持乐观态度。1985年，牛津大学的多奇教授甚至推出了一个鼓舞人心的物理版的丘奇-图灵论题，用“有限可实现的物理系统”代替了“可计算的功能”，并陈述了他所谓的“多奇原理”(又称物理学的丘奇-图灵原理):“每一个有限可实现的物理系统，正如我们所知，基于现代物理学和生物物理学，许多物理学家认为，巨大的天体，我们的生命体，甚至人类的心灵，都是有限可实现的物理系统的子系统。因此，原则上，通用计算机可以用于以有限的方式操作完美的模拟。
显然，多奇原理是一个比丘奇-图灵论题更强的“工作假说”。从丘奇-图灵命题到多奇原理，我们的可计算领土在不断扩大。如果多奇原理是正确的，它将揭示物理现实的深刻本质。这种基于物理主义和可计算性的立场，也是人工智能专家所追求的各种工作假说的核心。道奇等人将算法或计算等纯粹抽象的数学概念视为物理规律的体现，将计算系统视为自然规律的自然结果。在他们看来，通用计算机的概念不仅是自然规律所认可的，而且很可能是自然规律的内在要求。其实我们知道，所有鼓吹虚拟现实技术、人工生命、人工智能的人，都相信奇性原理的真理。当然，并没有强有力的科学证据来反驳奇数原理，因为它是一个包含“通用模拟机器”概念的全称命题。原则上通用仿真机可以实现的算法(程序)数量是无限的。
根据理论计算机的最新发展，量子计算机的倡导者断言，能实现奇原理的通用模拟机只能是量子通用图灵机。1998“量子领域的旗手”G.L.Milburn指出，物理理论与丘奇-图灵论题的物理版本密切相关的事实是，物理理论通过数学给出的观测数据，正是我们所说的可计算问题所提供的数据，所以这些数据可以通过运行在一般图灵机上的算法得到。经典和量子物理系统都可以任意高精度模拟。但是，对于某些问题，程序的运行时间可能是一个天文数字。如果世界是经典的，可以用蒙特卡罗方法有效模拟随机性；但如果世界是具有不可约随机性的量子，基于隐变量的经典随机性就不能用来解释量子随机性，量子世界的博弈应该遵循费曼法则。因此，R.Feynmen意识到解决这一问题的方法是建造一台量子计算机，即利用量子过程本身作为计算手段，计算的基本步骤将在原子或亚原子水平上进行。因此，在1998中，丘奇-图灵命题被修改为:
“所有有限描述性物理测量系统的结果，都可以用有限的方式完美模拟一台通用量子计算机的运行，测量结果的记录就是最终产品。”
这里的“有限的可描述的物理测量系统”是指用于建立和操作测量装置的指令必须能够用有限的代码来表达；“完美模拟”是指模拟产生的数据与真实测量得到的数据无法区分；“最终产品”意味着所有模拟测量必须在某一时刻结束，并且不会产生新的结果。
那么量子计算机超越经典计算机的地方在哪里？它的计算本质是什么？
首先，量子计算机可以进行经典计算机无法进行的计算:比如可以模拟任意精度的量子物理系统，使得求解时间不随问题规模呈指数增长。比如，过去即使使用超级计算机，完成将一个64位的数分解成质因数的乘积的运算，也需要比宇宙年龄更长的时间。贝尔实验室的彼得·肖尔(Peter Shor)的量子算法，依靠大规模量子纠缠，可以在量子计算机上，在相对较短的时间内，成功地将一个64比特的数分解成素数因子的乘积。量子计算机超越经典图灵机的能力在于量子相干产生的并行计算的力量。
量子计算机是实现计算的物理器件，是按照量子物理规律运行的物理系统，是基于量子图灵机的现代计算机。通用图灵机的算法是完全确定的。在这种确定性算法中，当图灵机读写头的当前状态和当前存储单元内容给定时，读写头的下一个状态和运动就完全确定了。在经典概率算法中，当读写头的当前状态和存储单元的当前内容给定时，图灵机以一定的概率变化到下一个状态，完成读写头的移动。这个概率函数是一个实数，值为[0，1]，完全决定了概率图灵机的性质。量子计算机和经典概率图灵机的区别在于，当前读写头状态和当前存储单元内容从经典正交态(0，1)变成了量子态(0，1，0和1的概率叠加态)，概率函数变成了复值的概率振幅函数，因此量子计算机的性质是由概率振幅函数决定的。量子计算机能够进行高效的计算，完全是由于量子叠加效应，即一个原子的状态可以处于0和1的概率叠加态。一般来说，有了L个量子比特，一台量子计算机可以同时处理2L数，相当于一步就能计算出经典计算机中的2L数。量子计算机用量子态(需要用量子比特代替经典比特)对应计算机的数据和程序。读写头的不同物理状态由量子物理描述，机器的动力机制也由量子物理决定。当然，一个更重要的问题是，我们还必须描述它的输出，而我们最终需要的是经典比特，而不是量子比特，这将解决棘手的“退相干”。
但是，我们必须清楚地认识到，无论量子计算机的速度有多快，既然它在理论上只是一台量子图灵机，就必然会受到哥德尔定理所设定的逻辑极限的限制。量子计算机无法计算不可数的函数，也无法解决关机问题。归根结底，量子计算机的计算本质上是图灵机计算，也就是递归函数计算，所以丘奇-图灵命题仍然是量子计算机的理论基础。道奇试图将整个物理世界纳入计算范围，试图用量子计算机模拟人类的智能，但仍然无法摆脱逻辑的固有限制。如果可计算性如哥德尔所说，是一个独立于形式系统的绝对概念，那么量子计算机只是另一个计算速度更快的计算载体。
对计算技术的不懈追求是否能让我们在程序中捕捉到一个真实的“一致完整”的世界，值得思考？[11]在为自然界的问题提供科学答案的过程中，是否不存在逻辑障碍？除了图灵机，还有其他计算模型吗，比如DNA计算机等。人类的思维有没有可能是超越图灵机的机器？多奇原理告诉我们，不仅物理决定了计算机能做什么，反过来，计算机能做什么也将决定物理定律的终极性质。显然，多奇原理的初衷并不局限于改造计算载体的意义，而在于指出现实世界=物理世界=计算世界。