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

Question

在阅读一些关于递归神经网络的图灵完整性的论文时(例如:使用神经网络进行图灵可计算性,Hava T. Siegelmann和Eduardo D. Sontag,1991),我感觉到那里给出的证据并不是真的那样实际的.例如,参考文献需要神经网络,神经元活动必须具有无限精确性(可靠地表示任何有理数).其他证明需要无限大小的神经网络.显然,这并不是那么实用.

但是我开始怀疑现在是否真的有意义要求图灵的完整性.根据严格的定义,现在没有计算机系统是图灵完整的,因为它们都不能模拟无限的磁带.

有趣的是,如果编程语言规范完整或不完整,那么编程语言规范最常开放.这一切归结为问题,如果它们总是能够分配更多的内存,并且函数调用堆栈大小是无限的.大多数规范并没有真正指定这一点.当然,所有可用的实现都受到限制,因此编程语言的所有实际实现都不是图灵完整的.

所以,你可以说是所有计算机系统都和有限状态机一样强大而不是更多.

这让我想到了这样一个问题:图灵这个词完全有用吗？

回到神经网络:对于神经网络(包括我们自己的大脑)的任何实际实现,它们将无法表示无限数量的状态,即通过严格定义图灵完整性,它们不是图灵完整的.那么神经网络图灵完全是否有意义的问题呢？

他们是否像有限状态机一样强大的问题早已得到了回答(1954年由明斯基回答,答案当然是肯定的)并且似乎也更容易回答.即,至少在理论上,这已经证明它们和任何计算机一样强大.

---

其他一些问题更多的是我真正想知道的:

• 是否有任何理论术语可以说明计算机的计算能力？(鉴于其有限的存储空间)

• 你怎么能比较神经网络的实际实现与计算机的计算能力？(如上所述,图灵完整性没有用.)

Answer 1

说明数学模型是图灵完成的观点是,在给定足够数量的资源(即无限)的情况下,揭示模型执行任何计算的能力,而不是显示模型的特定实现是否具有这些资源.非图灵完备车型将无法处理一组特定的计算,即使有足够的资源,一些揭示了两种模式操作方式的差别,即使他们的资源有限.当然,为了证明这个属性,你必须假设模型能够使用无限量的资源,但即使资源有限,模型的这个属性也是相关的.

Answer 2

递归神经网络的图灵完备性可能意味着:每个图灵机(有限状态头和无限带)的(有限)转换表可以通过有限递归神经网络建模(有限多个有限多个神经元)国家,特别是只有两个州).转换表定义了三个功能:

• 下一状态(当前状态,当前符号)

• 下一个符号(当前状态,当前符号)

• 方向(电流状态时,电流 - 符号)

这就是递归神经网络可以执行此任务的方式(只是一个非常原始的草图):

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

根据权利要求是,其对于每一个图灵机有这样的回归神经网络.

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

Answer 3

当现代计算机被称为图灵完成时,图灵所描述的无限存储设备有一个未说出口的例外,这显然对有限物理计算设备来说是不可能的.如果计算设备可以完成图灵机可以做的所有事情(无限存储),那么图灵完成所有实际意图和目的.通过对图灵完整性的这种不那么严格的定义,是的,许多神经网络可能是图灵完成的.

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

Answer 4

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

神经网络具有通用逼近器的特性 - 也就是说,它们可以将任何函数逼近任意精度.正是"精确度"部分使神经网络无需无限.

Answer 5

常规的前馈神经网络并不完整.实际上,它们相当于单个复杂的数学函数,可以进行大量的计算,但没有任何能力执行循环或其他控制流操作.

但是,如果您通过某种方式连接神经网络来访问有状态环境,那么它可以被制作成图灵完整的机器.

作为一个最简单的例子,您可以重新创建一个经典风格的图灵机,其中:

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

然后,您可以训练神经网络模拟任何所需的图灵机状态表/配置的动作(可能通过监督学习另一个图灵机的动作？)

注意:使用某种形式的状态反馈重复运行前馈网络的想法基本上等同于递归神经网络.所以你可以想到一个递归的神经网络加上反复运行它的逻辑,因为图灵完成了.您需要额外的逻辑(超出网络本身)以确保图灵完整性,因为有必要处理终止,重复和IO等事情.

Answer 6

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

相反,它的目的是判断特定语言是否能够表达特定任务.也就是说,我说它实际上是关于表达不执行它的算法.

由于神经网络没有语言,因此根据神经网络而不是网络的能力来表达算法是一个问题.所以我不知道你问题最后一点的答案!

Answer 7

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

图灵完整性

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

递归神经网络（RNN）

关于神经网络的计算能力

经常被引用的论文是《关于神经网络的计算能力》，Siegelmann＆Sonntag，1992年，该论文指出RNN是图灵完备的。本文假设我们在分母/分母中有无限制的有理数，即无限内存被编码为有理数或无限精度的浮点数。另请参阅此处。通常，我们不会以有理数（无限制）的方式对NN进行建模。当我们将自己限制为具有有限精度权重和激活的（R）NN时，本文中的证明就适用了，不再适用。因此，本文不那么相关。

Weiss等人在2018年发表了一篇名为《有限精确RNN对语言识别的实用计算能力》的论文，该论文正好解决了这一问题。

通用逼近器

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

没有外部存储器

因此，要明确指出：没有外部存储器，标准的RNN和LSTM 都不是图灵完整的。定义RNN的概念也没有直接方法，您可以在其中按需添加内存。RNN的内存是最新的隐藏激活。添加更多的内存意味着更改NN，即添加新的神经元，从而增加其内部功能。这就像更改程序本身一样。

带外部存储器

有神经图灵机（NTM）和一些类似的模型，它们具有某种外部存储器。在这里，直接考虑一下NTM的概念，您可以根据需要添加内存。因此，我们可以说NTM的概念已经完成了。

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

学习/培训

我们主要讨论了理论计算能力。一个非常不同的问题是NN是否可以学习这种功能。也就是说，训练（梯度搜索）是否会导致NN学习了可计算功能。

人脑

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

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