neural-network - 图灵完备性有多大用处？神经网络图灵完备吗？

Question

在阅读一些关于循环神经网络的图灵完备性的论文时（例如：Turing computability with neural nets，Hava T. Siegelmann 和 Eduardo D. Sontag，1991），我觉得那里给出的证明并不是真的那样实际的。例如，参考论文需要一个神经网络，其神经元活动必须具有无限精确性（以可靠地表示任何有理数）。其他证明需要一个无限大小的神经网络。显然，这并不是那么实际。

但我现在开始怀疑，要求图灵完备是否真的有意义。按照严格的定义，现在没有一个计算机系统是图灵完备的，因为它们都无法模拟无限磁带。

有趣的是，编程语言规范最常将其打开，无论它们是否完整。这一切都归结为他们是否总是能够分配更多内存以及函数调用堆栈大小是否无限的问题。大多数规范并没有真正指定这一点。当然，所有可用的实现都在这里受到限制，因此编程语言的所有实际实现都不是图灵完备的。

因此，您可以说所有计算机系统都与有限状态机一样强大，仅此而已。

这让我想到了一个问题：图灵这个术语到底有多大用处？

回到神经网络：对于神经网络（包括我们自己的大脑）的任何实际实现，它们将无法表示无限数量的状态，即根据图灵完备性的严格定义，它们不是图灵完备的。那么，如果神经网络是图灵完备的，这个问题是否有意义呢？

它们是否与有限状态机一样强大的问题已经在更早的时候得到了回答（Minsky 于 1954 年给出的答案：是的），而且似乎也更容易回答。即，至少在理论上，这已经证明它们与任何计算机一样强大。

---

其他一些更多关于我真正想知道的问题：

• 是否有任何理论术语可以更具体地说明计算机的计算能力？（鉴于其有限的内存空间）

• 您如何将神经网络的实际实现与计算机的计算能力进行比较？（如上所述，图灵完备性没有用。）

Answer 1

说明一个数学模型是图灵完备的，是为了揭示模型在给定足够数量的资源（即无限）的情况下执行任何计算的能力，而不是显示模型的特定实现是否确实具有这些资源。即使有足够的资源，非图灵完备模型也无法处理一组特定的计算，这表明这两种模型的运行方式存在差异，即使它们的资源有限。当然，要证明这个属性，你必须假设模型能够使用无限量的资源，但是即使资源有限，模型的这个属性也是相关的。

Answer 2

当现代计算机被称为图灵完备时，图灵描述的无限存储设备有一个不言而喻的例外，这在有限的物理计算设备上显然是不可能的。如果计算设备可以做图灵机可以做的所有事情（无限存储无法承受），那么它对于所有实际意图和目的来说都是图灵完备的。通过这种不太严格的图灵完备性定义，是的，许多神经网络可能是图灵完备的。

当然可以创建一个不是图灵完备的。

Answer 3

递归神经网络的图灵完备性可能意味着：每台图灵机（具有有限状态头和无限磁带）的（有限）转换表可以由有限递归神经网络（有限多个神经元与有限多州，尤其是只有两个州）。转换表定义了三个功能：

• 下一个状态（当前状态，当前符号）

• 下一个符号（当前状态，当前符号）

• 方向（当前状态，当前符号）

这就是循环神经网络执行此任务的方式（只是一个非常原始的草图）：

绿色神经元读取当前单元格中的符号（二进制表示），灰色神经元（初始静音）确定当前状态，红色神经元将新符号写入当前单元格，黄色神经元确定是向左还是向右. 蓝色神经元是内部神经元（最初是静音的）。

声称是，对于每台图灵机，都有这样一个循环神经网络。

我想知道是否有一种系统的方法可以从给定的转换表构建这样的网络。

Answer 4

Regular feedforward neural networks are not turing complete. They are, in effect, equivalent to a single complicated mathematical function that may do quite a lot of calculations but doesn't have any ability perform looping or other control flow operations.

However, if you wire up a neural network with some way to access a stateful environment then it can be be made into a turing complete machine.

As a most trivial example, you could recreate a classic-style Turing machine where:

• the input to the neural network is the value on the tape and the previous state
• the output of the neural network is the next state and the action

You could then train the neural network to emulate the actions of any desired turing machine state table / configuration (perhaps by supervised learning on the actions of another turing machine?)

Note: The idea of running a feedforward net repeatedly with some form of state feedback is essentially equivalent to a recurrent neural network. So you can think of a recurrent neural network plus the logic that runs it repeatedly as being Turing complete. You need the extra logic (over and above the network itself) to ensure Turing completeness because it is necessary to handle things like termination, repetition and IO.

Answer 5

部分解决您的第二个问题：

神经网络具有作为通用逼近器的特性——也就是说，它们可以将任何函数逼近到任意精度。正是“精确度”部分使神经网络不需要是无限的。

Answer 6

多年以后，让我自己来回答这个问题。

图灵完备性

• 与图灵机 (TM) 一样强大。
• 需要无限的记忆。即在实践中，没有任何物理设备可以是图灵完备的。
• 考虑一台普通的个人计算机（PC）：
  • 特定的物理实例不是图灵完备的，因为它具有有限的内存。
  • 但是，将PC 的概念视为可以按需添加内存的东西。当您添加更多内存时，所有程序仍将以相同的方式运行。对于任何给定的输入和任何给定的程序，都有一个最大的内存量，它应该可以工作。（现在让我们不要对int64内存地址限制或类似的东西过于迂腐。这些是技术限制，可以通过例如大整数等来解决。）因此，我们可以说PC的概念是图灵完备的。
• 图灵完整性实际上主要与内存概念有关。考虑任何有限状态机/自动机 (FSA)，以及对外部存储器的一些访问。根据内存的类型，您最终会进入乔姆斯基层次结构的不同类别：
  • 没有记忆/有限记忆：常规语言
  • 单栈：下推自动机，上下文无关语言
  • 两个或多个堆栈：图灵完备、递归可枚举语言

递归神经网络 (RNN)

关于神经网络的计算能力

一篇经常被引用的论文是关于神经网络的计算能力，Siegelmann & Sonntag，1992，其中指出 RNN 是图灵完备的。本文假设我们在提名/分母中有无限制的有理数，即无限内存被编码为有理数，或无限精度的浮点数。另请参见此处。通常我们不会以使用有理数（无限制）操作的方式对 NN 进行建模。当我们将自己限制在具有有限精度权重和激活的 (R)NN 上时，论文中的证明就变得不合时宜，不再适用。因此，这篇论文没有那么重要。

Weiss 等人在 2018 年发表了一篇更近期的论文On the Practical Computational Power of Finite Precision RNNs for Language Recognition，正好解决了这个问题。

通用逼近器

众所周知，大多数标准 NN 都是通用逼近器。这表明，给定任何函数（非常量、有界和连续），并给定一些允许的阈值，您可以构造一个在允许的阈值内逼近该函数的 NN。这是关于有限维向量空间的。当我们谈论可计算性时，我们谈论的是序列，因此我们有一个无限维的向量空间。因此，这个属性不是那么相关。

没有外部存储器

因此，明确地说：没有外部存储器，标准的 RNN 和LSTM都不是图灵完备的。也没有直接的方法可以定义RNN 的概念，您可以在其中按需添加内存。RNN 的记忆是最近的隐藏激活。添加更多的内存意味着改变神经网络，即添加新的神经元，从而增加它的内部工作。这就像改变程序本身一样。

带外部存储器

有神经图灵机 (NTM)和一些类似的模型，它们具有某种外部存储器。在这里，您可以直接考虑NTM 的概念，您可以在其中按需添加内存。因此我们可以说NTM的概念是图灵完备的。

有一些细节，比如头部使用的注意力类型，需要一些调整。该模型有一个后续版本，可微神经计算机 (DNC)明确解决了这个问题，并且还具有一些明确的机制来添加内存。

学习/培训

我们主要谈论的是理论计算能力。一个非常不同的问题是神经网络是否可以学习这样的功能。即训练（梯度搜索）是否导致学习了可计算函数的NN。

人脑

我们可以将人脑（或任何大脑）解释为一种复杂的神经网络。我们也可以问一个问题，人脑（模型）是否是图灵完备的。参见例如这里。这个问题很棘手。直觉会说我们能够执行任何类型的计算，因此人脑是图灵完备的。然而，我们在这里概述的论点表明 RNN 不是图灵完备的。重要的是记忆效应。在某些时候，人脑的记忆容量不足以对某些输入进行操作。因此，我们需要外部存储器。因此，显然，人脑连同外部记忆是图灵完备的。

然而，人脑中的记忆有一个方面与标准 RNN 有点不同：它可以高度概括，并且访问某些激活的寻址机制不同。此外，它具有某种自适应权重（但也只能存储有限信息）。

Answer 7

我认为图灵完备性的概念并不是要告诉我们特定的计算机是否可以执行特定的任务。

相反，它的目的是判断一种特定的语言是否能够表达特定的任务。也就是说，我想说这实际上是关于表达一个不执行它的算法。

由于神经网络没有语言，这是一个用神经网络表达算法的问题，而不是该网络的能力。所以我不知道你问题最后一点的答案！

Answer 8

我认为关于图灵机的重要一点是，对于任何给定的输入和程序，机器只需要有限数量的磁带，假设它停止一段时间。这就是为什么我会说“图灵完备”一词很有用：您只需要有限的内存即可在某些特定输入上运行一个特定的图灵完备程序（如果程序停止）。但是，如果您拥有非图灵完备的机器/语言/技术，则无论您添加多少内存，它都无法模拟某些算法。

Answer 9

知道您的系统是乔姆斯基层次结构中的哪个类几乎总是很高兴。这在更受限制的类中尤其重要，例如常规语言/有限自动机与无上下文语言。同样，具有识别您要解决的问题属于哪个类的技能也很重要，否则可能会尝试做一些愚蠢的事情，例如仅使用正则表达式解析 HTML 或 XML，这是不可能的。

知道你的形式主义或系统正在完善，这表明你可以用它构建任何你想要的东西。它没有说任何实用性，只是解决问题的可能性或不可能性。在考虑 turing tarpit 时，这是令人痛苦的事实，但也有许多 turing 完整系统是专门为小众目的而制造的，任何人都不应该梦想在生产环境中将其用于通用工作。

简而言之，对乔姆斯基层次结构的深入了解将在很多情况下帮助您，不仅可以选择正确的解析器类型；正则表达式、下推、CFG 或更强大，但也用于选择正确类型的机器或形式主义来表达一般的过程。

Answer 10

基本上，这意味着使用图灵完备的编程语言或架构，
您可以执行各种各样的算法……主要是——任何一种。

非图灵语言的潜力要大得多。

Answer 11

答案很简单。如果你可以用它来模拟 NOR 或 NAND 门，那么它就是图灵完备的，假设剩下的只是将事物组合在一起的问题。