---

  新智元报道  

1996年的8月19日至23日，芬兰的瓦萨举行了由芬兰人工智能协会和瓦萨大学组织的芬兰人工智能会议。

会议上发表的一篇论文证明：图灵机就是一个循环神经网络。

没错，这是在26年前！

让我们来看一看，这篇发表于1996年的论文。

1.1 神经网络分类

长期以来，人们都知道单层前馈网络只能用于对线性可分的模式进行分类，即连续层越多，类的分布就越复杂。

当在网络结构中引入反馈时，感知器输出值被循环利用，连续层的数量原则上变为无限大。

算力有没有质的提升？答案是肯定的。

例如，可以构造一个分类器来判断输入整数是否为素数。

事实证明，用于此目的的网络大小可以是有限的，即使输入整数大小不受限制，可以正确分类的素数数量也是无限的。

在本文中，「由相同计算元素组成的循环网络结构」可用于完成任何（算法上的）可计算功能。

定义程序语言。该语言有四种基本操作：

这里，V代表任何具有正整数值的变量，j代表任何行号。

可以证明，如果一个函数是图灵可计算的，则可以使用这种简单的语言对其进行编码（有关详细信息，请参见[1]）。

2.1 递归神经网络结构

其中，当前时刻的感知器输出（用表示）是使用n输入计算的。

非线性函数f现在可定义为

这样函数就可以简单地「切断」负值，感知器网络中的循环意味着感知器可以以复杂的方式组合。

图1 递归神经网络的整体框架，结构自主无外部输入，网络行为完全由初始状态决定

在图1中，递归结构显示在一个通用框架中：现在和n是感知器的数量，从感知器p到感知器q的连接由（1）中的标量权重表示。

即给定初始状态，网络状态会迭代到不再发生变化，结果可以在该稳定状态或网络的「固定点」下读取。

2.2 神经网络建构

接下来阐述该程序如何在感知器网络中实现。该网络由以下节点（或感知器）组成：

• 对于程序中的每个变量V，都有一个变量节点。
• 对于每个程序行i，都有一个指令节点。
• 对于第i行上的每个条件分支指令，另外还有两个转移节点和。

语言程序的实现包括感知器网络的以下变化：

• 对于程序中的每个变V，使用以下链接扩充网络：

• 如果程序代码的第i行没有操作()，则使用以下链接扩充网络（假设该节点存在：

• 如果第i行有增量操作()，则按如下方式扩充网络：

• 如果第i行有递减操作()，则按如下方式扩充网络：

• 如果第i行有条件分支()，则按如下方式扩充网络：

2.3 等效性证明

现在需要证明的是，「网络的内部状态或网络节点的内容」，可以用程序状态来标识，同时网络状态的连续性与程序流对应。

• 至所有转换节点和（如2.2中所定义）的输出为零()；
• 至多一个指令节点有单位输出()，所有其他指令节点有零输出，并且
• 变量节点具有非负整数输出值。

如果所有指令节点的输出均为零，则状态最终状态。一个合法的网络状态可以直接解释为一个程序「快照」——如果，程序计数器在第i行，相应的变量值存储在变量节点中。

接下来，详细说明指令节点。假设唯一的非零指令节点在时间k---这对应于程序计数器在程序代码中第i行。

若程序中第i行是，则网络向前一步的行为可表示为（只显示受影响的节点）

另一方面，如果程序中的第i行是，则向前一步的行为是

，网络的操作将是相同的，除了变量V的值增加。

第i行的条件分支操作（IF  GOTO j）激活更复杂的操作序列：

3.1 扩展

定义额外的流线型指令很容易，这些指令可以使编程更容易，并且生成的程序更具可读性和执行速度。例如，

• 第i行的无条件分支（GOTO j）可以实现为
• 将常量c添加到第i行的变量（）可以实现为
• 行i上的另一种条件分支（IF V=0 GOTO j ）可以实现为
• 此外，可以同时评估各种递增/递减指令。假设要执行以下操作：。只需要一个节点：

3.2 矩阵制定

上述构造也可以以矩阵的形式实现。

基本思想是将变量值和「程序计数器」存储在进程状态s中，并让状态转换矩阵A代表节点之间的链接。

矩阵结构的运算可以定义为一个离散时间的动态过程

其中非线性向量值函数现在按元素定义，如（2）中所示。

假设要实现一个简单的函数y=x，也就是说，输入变量x的值应该传递给输出变量y。使用语言可以将其编码为（让「入口点」现在不是第一行而是第三行）：

如果变量节点的值将严格保在0和1之间，则动态系统（3）的操作将是线性的，该函数根本没有影响。

事实证明，迭代总是在步骤之后收敛，其中。

5.1 理论方面

循环感知器网络（如上所示）是图灵机的（又一种）形式。

与语言相比，网络实现具有以下「扩展」：

• 变量可以是连续的，而不仅仅是整数值。实际上，呈现实数的（理论）能力使网络实现比语言更强大，所有以语言呈现的数字都是有理数。

• 可以同时存在各种「程序计数器」，并且控制的转移可能是「模糊的」，这意味着指令节点提供的程序计数器值可能是非整数。

• 一个较小的扩展是可自由定义的程序入口点。这可能有助于简化程序——例如，变量的复制在上面的三个程序行中完成，而名义解决方案（参见[1]）需要七行和一个额外的局部变量。

5.2 相关工作

中非线性函数的展望（2）使得上述「图灵网络」中可能的状态数量是无限的。