超计算

超计算或超图灵计算是指可以提供图灵不可计算的输出的计算模型。 Hava Siegelmann 在 1990 年代早期提出的超级图灵计算指的是这种神经学启发的、生物和物理可实现的计算； 它成为终身机器学习的数学基础。 超计算在 1990 年代末作为一个科学领域被引入，据说是基于超级图灵，但它也包括哲学结构。 例如，可以解决停机问题的机器是超级计算机； 一个能够正确评估 Peano 算术中的每个语句的人也是如此。

Church-Turing 论文指出，任何可以由数学家使用笔和纸使用一组有限的简单算法计算的可计算函数，都可以由图灵机计算。 超级计算机计算图灵机无法计算的函数，因此在 Church-Turing 意义上是不可计算的。

从技术上讲，随机图灵机的输出是不可计算的； 然而，大多数超级计算文献都侧重于确定性函数的计算，而不是随机的、不可计算的函数。

艾伦图灵在其 1938 年的博士论文《基于序数的逻辑系统》中介绍了超越图灵机的计算模型。 这篇论文研究了可以使用 oracle 的数学系统，它可以计算从自然数到自然数的单个任意（非递归）函数。 他用这个装置证明，即使在那些更强大的系统中，不确定性仍然存在。 图灵的预言机是数学抽象，无法在物理上实现。

从某种意义上说，大多数函数都是不可计算的：有 ℵ 0 {displaystyle aleph _{0}} 可计算函数，但是有不可数的数（ 2 ℵ 0 {displaystyle 2{aleph _{0 }}} ) 可能的超级图灵函数。

超级计算机模型的范围从有用但可能无法实现的（例如图灵的原始预言机）到不太有用但更可能实现的随机函数生成器（例如随机图灵机）。

一个系统将不可计算的、神谕般的 Chaitin 常数（一个具有无限数字序列的数字，编码了停机问题的解决方案）作为输入的知识可以解决大量有用的不可判定问题； 授予不可计算的随机数生成器作为输入的系统可以创建随机的不可计算的函数，但通常不认为能够有意义地解决有用的不可计算的函数，例如停机问题。 可以想象的超级计算机有无数种不同类型，包括：

• 图灵的原始预言机，由图灵于 1939 年定义。
• 如果物理学允许一般的实数变量（而不仅仅是可计算的实数），那么一台真实的计算机（一种理想化的模拟计算机）可以执行超计算，并且这些变量在某种程度上可以用于有用的（而不是随机的）计算。 这可能需要非常奇异的物理定律（例如，具有神谕值的可测量物理常数，例如 Chaitin 常数），并且需要能够以任意精度测量实数值的物理值，尽管标准物理学 使得这种任意精度的测量在理论上是不可行的。
  • 类似地，以某种方式将 Chaitin 常数精确嵌入其权重函数的神经网络将能够解决停机问题，但与其他基于实际计算的超计算模型一样，会遇到相同的物理困难。

• 根据定义，某些基于模糊逻辑的模糊图灵机可以意外地解决停机问题，但这只是因为它们解决停机问题的能力是在机器的规范中间接假设的； 这往往被视为机器原始规格中的错误。
  • 类似地，被称为公平非确定性的提议模型可能会意外地允许对不可计算函数进行神谕计算，因为根据定义，某些此类系统具有神谕能力来识别拒绝输入，这些拒绝输入会不公平地导致子系统永远运行。</ 李>
• Dmytro Taranovsky 提出了传统非有限分析分支的有限模型，该模型围绕配备快速增长函数作为其 oracle 的图灵机构建。 通过这个和更复杂的模型，他能够给出二阶算术的解释。 这些模型需要不可计算的输入，例如物理事件生成过程，其中事件之间的间隔以无法计算的大速率增长。
  • 同样，根据定义，无限非确定性模型的一种非正统解释假定