图灵完整性有多有用？神经网图完整吗？

Question

在阅读一些有关复发性神经网络完整性的论文时（例如：带有神经网的图灵可计算性，Hava T. Siegelmann和Eduardo D. Sontag，1991），我得到了这样的证据，没有真正的证据。实际的。例如，引用的论文需要一个神经元活动必须具有无限精确性的神经网络（可靠代表任何有理数）。其他证明需要无限规模的神经网络。显然，这并不是那么实用。

但是我开始怀疑现在是否确实有意义地要求图灵完整性。按照严格的定义，如今没有计算机系统正在完成，因为它们都无法模拟无限磁带。

有趣的是，编程语言规范如果图丁完整或不完整，通常会打开它。这一切都归结为问题是否始终能够分配更多的内存以及功能调用堆栈大小是否无限。大多数规范并未真正指定这一点。当然，在这里所有可用的实现都受到限制，因此编程语言的所有实际实现都不完整。

因此，您可以说的是，所有计算机系统都与有限状态机一样强大，而不是更多。

这给我带来了一个问题： Turing一词完全有用？

回到神经网：对于神经网的任何实际实施（包括我们自己的大脑），它们将无法代表无限数量的状态，即通过严格的图灵完整性定义，它们没有完成。 那么，神经网是否完全有意义吗？

问题是否像有限状态机器一样强大，已经回答了很早（Minsky的1954年，答案：是的），似乎也更容易回答。即，至少从理论上讲，这已经证明了它们与任何计算机一样强大。

---

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

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

• 您如何将神经网的实际实现的计算能力与计算机进行比较？ （图灵完整性并不如上所述。）

Answer 1

指出数学模型正在完成的目的是揭示该模型执行任何计算的能力， 给定足够数量的资源（即无限）, ，不说明模型的特定实现是否确实具有这些资源。非整齐的完整模型将无法处理一组特定的计算， 即使有足够的资源, ，揭示了两个模型运行方式的差异， 即使他们的资源有限. 。当然，要 证明 此属性，您必须假设这些模型能够使用无数资源，但是 即使资源有限，模型的属性也很重要。

Answer 2

复发性神经网络的图灵完整性可能意味着：每台图灵机的（有限的）过渡表（有限状态的头部和无限胶带）可以通过有限的复发性神经网络建模（有限的许多神经元有限的许多具有有限的神经元，许多神经元有限国家，特别是两个州）。过渡表定义了三个函数：

• 下一态（电流状态，电流符号）

• 临时符号（电流状态，电流符号）

• 方向（电流状态，电流符号）

这就是复发性神经网络可以执行此任务的方式（只是一个非常原始的草图）：

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

主张是 那 对于每台图灵机，都有这样的复发性神经网络。

我想知道是否有一种系统的方法可以从给定的过渡表中构建此类网络。

Answer 3

当据说现代计算机是 图灵完成 描述的无限存储设备图灵有一个无声的例外，这显然是有限的物理计算设备上不可能的。如果计算设备可以完成图灵机可以做的一切（无限存储），则是 图灵完成 出于所有实际意图和目的。通过这种不太严格的定义 图灵完整性, ，是的，许多神经网络可能是 图灵完成.

当然可以创建一个不是 图灵完成.

Answer 4

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

神经网络具有存在的特性 通用近似值 - 也就是说，它们可以将任何功能近似于任意程度的精度。这是“精确度”部分，使神经网络不需要无限。

Answer 5

定期前馈神经网络是 不完整. 。实际上，它们等同于单个复杂的数学函数，该功能可能会执行很多计算，但没有任何能力执行循环或其他控制流动操作。

但是，如果您以某种方式连接神经网络，以访问状态环境 可以制作成图灵完整的机器.

作为一个最琐碎的例子，您可以重新创建经典风格的Turing机器：

• 神经网络的输入是磁带和先前状态的值
• 神经网络的输出是下一个状态和动作

然后，您可以训练神经网络以效仿任何所需的图灵机状态表 /配置的动作（也许是通过对另一台图灵机的动作进行监督学习？）

注意：反复以某种形式的状态反馈反复运行前馈网的想法本质上等同于 复发性神经网络. 。因此，您可以想到一个反复的神经网络 加 将其重复运行的逻辑完成。您需要额外的逻辑（在网络本身之上），以确保图丁完整性，因为有必要处理终止，重复和IO之类的内容。

Answer 6

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

相反，它的目的是说出特定语言是否能够表达特定任务。也就是说，我说这真的是关于 表达 算法不是 表演 它。

由于神经网络没有语言，因此这是通过神经网络而不是该网络的能力来表达算法的问题。因此，我不知道您问题的最后一点答案！

Answer 7

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

图灵完整性

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

复发性神经网络（RNN）

关于神经网的计算能力

经常引用的纸是 关于神经网的计算能力，Siegelmann＆Sonntag，1992, ，其中指出RNNS正在完成。本文假设我们在提名人/分母中没有限制的理性数字，即无限记忆被编码为有理数，或无限精度的浮点数。也可以看看 这里. 。通常，我们不会以具有合理数字（无限制）运行的方式对NN进行建模。当我们将自己限制在具有有限的精度权重和激活的（r）NN时，纸张中的证明就会落在Appart中，并且不再适用。因此，本文并不重要。

有一篇最近的论文， 关于语言识别的有限精度RNN的实用计算能力，Weiss等，2018, ，确切解决这个问题。

通用近似值

众所周知，大多数标准NN是 通用近似值. 。这指出了给定的任何函数（非稳定，边界和连续），并且给定一些允许的阈值，您可以构造一个nn，该nn在允许的阈值中近似于此函数。这是关于有限维矢量空间的。当我们谈论可计算性时，我们会谈论序列，因此我们有一个无限的维矢量空间。因此，该属性并不重要。

没有外部记忆

因此，明确说明它：没有外部内存，标准RNN以及 LSTM 是 不完整。也没有直接的方式如何定义 RNN的概念, ，您可以按需添加内存。 RNN的记忆是最新的隐藏激活。添加更多内存意味着更改nn，即添加新的神经元，从而添加其内部功能。这就像更改程序本身。

与外部内存

有 神经图灵机（NTM） 还有一些具有某种外部内存的类似模型。在这里考虑一个 NTM的概念 您将按需添加内存。因此，我们可以说 这 NTM的概念 图灵完整.

有一些细节，例如头部使用的关注类型，需要一些适应性。该模型有一个后续行动 可区分的神经计算机（DNC） 它明确解决了这一点，并且还具有一些明确的机制来添加内存。

学习 /培训

我们主要谈论理论计算能力。一个截然不同的问题是NN是否可以学习这样的功能。即训练（梯度搜索）是否导致学习可计算功能的NN。

人脑

我们可能会将人脑（或任何大脑）解释为一种复杂的神经网络。我们还可以问一个问题，人类大脑（模型）是否完整。参见例如 这里. 。这个问题很棘手。直觉会说我们能够执行任何类型的计算，因此人的大脑已经完成。但是，我们在这里概述的论点表明，RNN并未完成。重要的是记忆效应。在某个时候，人脑的记忆能力不足以在某些输入上运行。因此，我们需要外部内存。因此，显然，人的大脑以及外部记忆正在完整。

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

Answer 8

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

Answer 9

知道您的系统是乔姆斯基层次结构中哪个类几乎总是很高兴。这在更狭窄的类中尤其重要，例如普通语言 /有限自动机与无上下文的语言。还要拥有能够识别您要解决的问题的技能也很重要，否则，人们可能会尝试进行愚蠢的事情，例如仅使用正则表达式解析HTML或XML，这是不可能的。

让您的形式主义或系统完整的知识知道您可以用它来构建任何想要的内容。它没有说明实用性，只是解决问题的可能性或不可能。当考虑图灵的篷布时，这是痛苦的，但是也有许多图灵完整的系统是专门用于利基市场的，没有人应该梦想在生产环境中使用通用工作。

简而言之，对乔姆斯基层次结构的良好知识将在许多情况下为您提供帮助，不仅是为了选择正确的解析器； REGEXP，下降，CFG或更强大，但也用于选择一般表达过程的正确类型的机器或形式主义类型。

Answer 10

基本上，这意味着准备完整的编程语言或架构
您可以执行各种算法...主要是 - 任何一种。

非语言的潜力更加紧密。

Answer 11

答案很简单。如果您可以与它模仿或与NAND大门一起使用，那么假设其余的只是将事物结合在一起的问题，那么它就完整了。