超计算的数学与物理原理(一）

可计算性理论（Computability theory）解决可计算问题，得出它们的解决方案。总体来说，难题可以被分为两种：一种是可以在算法上解决的难题，另一种则不可以。具体来说，一个能解决特定问题的算法设计通常意味着这个问题能“在算法上”被解决。

另外，一个能解决特定问题的算法设计等同于一个解决同样一个问题的图灵机构造下的一个工作。显然，当一个问题不能在算法上被解决，那就不存在图灵机能解决这个问题。

一个令人感到惊奇的结果是，如果一个人期望解决一个“不可计算”（noncomputable）的问题，也就是一个无法在算法上被解决的问题，可以在更高层次上是“可计算的”。

超计算（hypercomputation）可以解决传统意义上图灵机无法解决的问题，即“不可计算的”问题。

在介绍超计算模型前，首先让我们回顾一下图灵机模型的历史及其局限。

最初，计算这个词是计算和推算的同义词，计算机是计算方面的“擅长者”。 在20世纪50年代随着（电子）计算机的出现，计算一词的含义扩大到包括这些机器的操作和使用，这些过程在计算机硬件本身、内部和理论上所进行的管理它们的概念。 一般来说，这些理论概念是基于计算机能够枚举“事物”的能力并计算函数的值。 这个具体的直接后果计算的观点是所谓的丘奇图灵论题（Church-Turing thesis），是丘奇和图灵介绍了概念并构造了所谓可计算性理论的核心思想。

在这篇出于努力回答由大卫·希尔伯特（David Hilbert）所提议的23个问题而产生的论文中，在希尔伯特在二十世纪初所阐述的庞大数学基础研究计划的背景下，最终发现了这个特别的，在导致制定的特定框架中，无法解决问题的这篇论文。 由于这篇论文是可计算性的核心，理论上，它直接影响了我们实现计算的方式及其局限性。特别是，论文指出，无论给定多么强大的计算设备是，这台机器始终有无法解决的问题。 换句话说，根据丘奇图灵论题（Church-Turing thesis），有一个逻辑上的限制会规定任何计算设备能和不能计算什么。

为了充分理解希尔伯特的问题及其如何帮助解决形成丘奇图灵论题（Church-Turing thesis），我们需要了解相关背景。这些背景里数学哲学是至关重要的。 这些数学哲学是：

（i）直觉主义，根据该直觉主义，只有可知的陈述是正确的（Luitzen Egbertus Jan Brouwer是直觉主义的创始人）；

（ii）柏拉图主义（或现实主义），主张数学指的是独立于我们所拥有的知识的实体；

（iii）形式主义，主要关注的是通过形式上的规则来表达数学语言（形式主义与希尔伯特特别相关）；

（iv）逻辑主义，即所有数学都可以归结为逻辑（逻辑主义与弗里德里希·路德维希·弗雷格特别相关，也包括罗素和怀特海，Friedrich Ludwig Gottlob Frege,Bertrand Russell, and Alfred North Whitehead)

在柏拉图主义的“图景”里，陈述要么是真的，要么是假的。 一个陈述的真相是“绝对的”，并且独立于任何推理，理解或行动。 因此，表达不虚假仅仅意味着真实;同样，不正确只是意味着虚假。 作为其直接后果，亚里士多德排除中间（tertium non datur）的原则，他指出陈述要么是真的，要么是假的，总是如此。 根据Arend Heyting的说法（直觉主义逻辑的创始人），如果一个陈述有证明，则该陈述为真。 但究竟什么证明呢？ Jean-Yves Girard 给出了以下阐释：

通过证明，我们不理解句法的正式副本（柏拉图主义者把世间万物都堪称绝对理念的副本），但是却理解了其内在客体，其中，句法的书写形式给予了一个朦胧的投影。

而直觉主义逻辑进路的一个有趣结果是：排除中间原则是无效的，否则我们不得不能够找到一个陈述的证明或者一个句陈述的证伪。

正如Heyting观察到的：p∨¬p需要一种解决每个问题的通用方法，或者更明确地说，对于任何命题p的一般方法，通过这种专业化的方法得到p的证明或¬p的证明。 如我们没有这种构造性的方法，我们就没有主张这一原则的权利。

在表达有效函数的形式主义（formalisms for expressing effective functions）与表达证明的形式主义（formalisms for expressing proofs）之间，库里 - 霍华德同构主义宣称有一个非同寻常的类比。实际上，这意味着逻辑证明对应于编程语言中的表达与阐释。 也就是，当一个人构造公式的证明时，其中是包括零的自然数集，他或她实际上构建了一个有效的找到满足的自然数的方法。换句话说，证明可以被视为程序。

伟大的古希腊哲学家柏拉图认为，数学命题不是指实际的物理对象，而是指某些理想化的对象。柏拉图设想这些理想的实体居住在一个不同的世界，与物质世界截然不同。 罗杰彭罗斯称这个世界为柏拉图式的数学形式世界（Platonic world of mathematical forms），并假设可以属于柏拉图世界的数学断言正是那些客观上为真的断言。 根据彭罗斯的说法，柏拉图的世界不在我们生活的世界之外，但是，相反，后者是前者的一部分。 事实上，彭罗斯实际上是一名伟大的探索者，因为他认为有三个世界不断相互作用：物理世界，心智世界和柏拉图式的世界。

一般来说，数学形式主义是关于操纵符号的数学哲学派别，而无论其符号含义如何。 希尔伯特的形式主义是企图通过建立一个形式系统，使数学处于安全可靠的基础上，这个形式系统能够表达所有数学并证明形式系统是一致的（即，不可能从一组公理推导出来两个形式上矛盾的定理）。在形式系统中，证明包括根据固定规则操纵符号，不采取考虑任何意义的概念。 当然，这并不意味着数学对象本身缺乏意义，或者说这个意义不重要。

总之，正如Girard所述：希尔伯特将数学视为一种形式活动，这是一种无稽之谈，如果我们从字面上理解它。。。 但是，我们应该怎样考虑那些将思想视为形式活动的人？

由于逻辑主义在计算理论的发展中起到了无足轻重的作用，笔者暂时不会详细说明它。

下面介绍从计算到超计算中的图灵的发现。

阿兰图灵（Alan Turing）介绍了可计算（实数）的概念，在他的开创性论文题为“可计算的数字”中，附有一个应用程序名为Entscheidungs problem 。 在本文中，图灵确定了可计算数字与图灵机实际可以计算的数字。特别是，如果实数是十进制数，则可以计算实数可通过有限手段计算。 在形式上，我们有以下定义：

定义1： 一个实数是可计算的，如果它有一个给二进制表达。也就是说，有一个可计算函数其中。

（待续）