背景

我们首先必须从计算理论中回顾一些概念。算法是计算函数的过程。给定输入，算法必须在有限的步数内产生正确的输出，然后终止。说一个函数是可计算的，意味着存在一个计算它的算法。在所有函数的无限集合中，大多数是不可计算的。图灵机是一种形式化计算概念的数学模型。存在其他等效模型，但图灵机是标准的“参考模型”。根据Church-Turing 命题，任何算法都可以用图灵机来实现，所有可计算的函数都可以由此计算出来。图灵机的任何特定实例仅计算特定函数。但是，存在一类特殊的图灵机，称为通用图灵机，可以模拟任何其他图灵机的任何输入。他们通过将要模拟的机器（及其输入）的描述作为他们自己输入的一部分来做到这一点。因此，通用图灵机的任何特定实例都可以计算任何可计算函数（即可以实现任何算法）。任何具有这种能力的系统都称为图灵完备. 证明系统是图灵完备的一种方法是证明它可以模拟通用图灵机。许多系统已被证明是图灵完备的（例如大多数编程语言、某些元胞自动机和量子力学）。

递归神经网络

以下论文表明，对于任何可计算函数，都存在一个可以计算它的有限循环神经网络 (RNN)。此外，存在图灵完备的有限 RNN，因此可以实现任何算法。

西格尔曼和桑塔格 (1992)。关于神经网络的计算能力

他们使用包含有限数量的循环连接单元的网络，这些单元在每个时间点接收外部输入。每个单元的状态由其输入的加权和（加上一个偏差）给出，通过非线性激活函数运行。激活函数是一个饱和线性函数，是一个sigmoid的分段线性逼近。权重和偏差是固定的，因此不会发生学习。

网络执行从二进制输入序列到二进制输出序列的映射。网络有两个外部输入，它们被馈送到所有单元：“数据线”和“验证线”。数据线包含零和一的输入序列，然后在输入序列完成后为零。验证行让网络知道输入序列何时发生。它在输入序列的持续时间内包含一个，然后在完成后为零。一个单元被认为是“输出单元”。它在任意延迟时输出零，然后是零和一的输出序列，然后在输出序列完成后输出零。另一个单元被认为是“验证单元”，它让我们知道输出序列何时发生。

尽管这些 RNN 将二进制输入序列映射到二进制输出序列，但我们可能对在各种其他数学对象（其他类型的数字、向量、图像、图形等）上定义的函数感兴趣。但是，对于任何可计算函数，这些其他类型的对象可以被编码为二进制序列（例如，请参阅此处了解使用自然数对其他对象进行编码的描述，而自然数又可以用二进制表示）。

结果

他们表明，对于每个可计算函数，都存在一个可以计算它的有限 RNN（上述形式）。他们通过展示可以使用 RNN 显式模拟具有两个堆栈的下推自动机来做到这一点。这是另一个在计算上等同于图灵机的模型。任何可计算函数都可以由图灵机计算。任何图灵机都可以通过具有两个堆栈的下推自动机来模拟。任何具有两个堆栈的下推自动机都可以由 RNN 模拟。因此，任何可计算的函数都可以由 RNN 计算。此外，由于某些图灵机是通用的，因此模拟它们的 RNN 是图灵完备的，因此可以实现任何算法。特别是，他们表明存在具有 1058 个或更少单元的图灵完备 RNN。

其他后果

模拟结果的一个有趣结果是，关于 RNN 行为的某些问题是无法确定的。这意味着不存在可以为任意 RNN 回答它们的算法（尽管它们可能在特定RNN 的情况下可以回答）。例如，一个给定的单位是否曾经取值 0 的问题是不可判定的；如果可以笼统地回答这个问题，就可以解决图灵机的停机问题，这是不可判定的。

计算能力

在上述论文中，所有网络参数和状态都是有理数。这很重要，因为它限制了 RNN 的能力，并使生成的网络更加真实。原因是有理数是可计算的数字，这意味着存在一种算法可以将它们计算到任意精度。大多数实数是不可计算的，因此无法访问——即使是最强大的图灵机也无法表示它们，许多人怀疑它们甚至可以在物理世界中表示。当我们在数字计算机上处​​理“实数”时，我们正在访问一个更小的子集（例如 64 位浮点数）。表示任意实数需要无限的信息。

该论文称，让网络访问实数将进一步提高计算能力，超越图灵机。Siegelmann 撰写了许多其他论文来探索这种“超级图灵”能力。然而，重要的是要注意这些是数学模型，结果并不意味着这样的机器实际上可以存在于物理世界中。有充分的理由认为它不能，尽管这是一个悬而未决的问题。

我想这就是你要找的。这家伙证明了多层，甚至单层前馈网络可以逼近任何函数，只要网络有足够的隐藏单元。

霍尼克，K. (1991)。多层前馈网络的逼近能力。神经网络，4（2），251-257。

RNN 也意味着随机神经网络。它的逼近能力在两篇论文中得到证明：

Erol Gelenbe、Zhi-Hong Mao、Yan-Da Li：尖峰随机网络的函数逼近。IEEE Trans。神经网络 10(1): 3-9 (1999)

Erol Gelenbe、Zhi-Hong Mao 和 Yan-Da Li：具有有限层数的随机神经网络的函数逼近，计算机科学与工程的进展：文本。透视计算机系统性能建模，第 35-58 页 (2006) https://doi.org/10.1142/9781860948923_0005