【新智元导读】这几位科学家在1996年对图灵机进行的论证，拿到今天来看也是值得深思的。
1996年的8月19日至23日，芬兰的瓦萨举行了由芬兰人工智能协会和瓦萨大学组织的芬兰人工智能会议。
会议上发表的一篇论文证明：图灵机就是一个循环神经网络。
没错，这是在26年前！
让我们来看一看，这篇发表于1996年的论文。
1 前言
1.1 神经网络分类
神经网络可用于分类任务，判断输入模式是否属于特定的类别。
长期以来，人们都知道单层前馈网络只能用于对线性可分的模式进行分类，即连续层越多，类的分布就越复杂。
当在网络结构中引入反馈时，感知器输出值被循环利用，连续层的数量原则上变为无限大。
算力有没有质的提升？答案是肯定的。
例如，可以构造一个分类器来判断输入整数是否为素数。
事实证明，用于此目的的网络大小可以是有限的，即使输入整数大小不受限制，可以正确分类的素数数量也是无限的。
在本文中，「由相同计算元素组成的循环网络结构」可用于完成任何（算法上的）可计算功能。
1.2 关于可计算性
根据可计算性理论的基本公理，可以使用图灵机实现可计算函数，有多种方法可以实现图灵机。
定义程序语言
。该语言有四种基本操作：
这里，V代表任何具有正整数值的变量，j代表任何行号。
可以证明，如果一个函数是图灵可计算的，则可以使用这种简单的语言对其进行编码（有关详细信息，请参见[1]）。
2 图灵网络
2.1 递归神经网络结构
本文研究的神经网络由感知器组成，它们都具有相同的结构，感知器数q的运算可以定义为
其中，当前时刻的感知器输出（用
表示）是使用n输入
计算的。
非线性函数f现在可定义为
这样函数就可以简单地「切断」负值，感知器网络中的循环意味着感知器可以以复杂的方式组合。
图1 递归神经网络的整体框架，结构自主无外部输入，网络行为完全由初始状态决定
在图1中，递归结构显示在一个通用框架中：现在
和n是感知器的数量，从感知器p到感知器q的连接由（1）中的
标量权重表示。
即给定初始状态，网络状态会迭代到不再发生变化，结果可以在该稳定状态或网络的「固定点」下读取。
2.2 神经网络建构
接下来阐述该程序
如何在感知器网络中实现。该网络由以下节点（或感知器）组成：
。
对于程序中的每个变量V，都有一个变量节点。
对于每个程序行i，都有一个指令节点。
和
对于第i行上的每个条件分支指令，另外还有两个转移节点
语言
程序的实现包括感知器网络的以下变化：
对于程序中的每个变V，使用以下链接扩充网络：
存在：
)，则使用以下链接扩充网络（假设该节点
如果程序代码的第i行没有操作(
)，则按如下方式扩充网络：
如果第i行有增量操作(
)，则按如下方式扩充网络：
如果第i行有递减操作(
)，则按如下方式扩充网络：
如果第i行有条件分支(
2.3 等效性证明
现在需要证明的是，「网络的内部状态或网络节点的内容」，可以用程序状态来标识，同时网络状态的连续性与程序流对应。
定义网络的「合法状态」如下：
)；
（如2.2中所定义）的输出为零(
和
至所有转换节点)，所有其他指令节点有零输出，并且
有单位输出(
至多一个指令节点变量节点具有非负整数输出值。
如果所有指令节点的输出均为零，则状态最终状态。一个合法的网络状态可以直接解释为一个程序「快照」——如果
，程序计数器在第i行，相应的变量值存储在变量节点中。
网络状态的变化是由非零节点激活的。首先，关注变量节点，事实证明它们表现为积分器，节点的先前内容被循环回同一节点。从变量节点到其他节点的唯一连接具有负权重——这就是为什么包含零的节点不会改变，因为非线性的原因（2）。接下来，详细说明指令节点。假设唯一的非零指令节点
在时间k---这对应于程序计数器在程序代码中第i行。若程序中第i行是
，则网络向前一步的行为可表示为（只显示受影响的节点）
事实证明，新的网络状态再次合法。与程序代码相比，这对应于程序计数器被转移到第i+1行。另一方面，如果程序中的第i行是
，则向前一步的行为是
这样，除了将程序计数器转移到下一行之外，变量V的值也会递减。如果第i行是
，网络的操作将是相同的，除了变量V的值增加。第i行的条件分支操作（IF 
GOTO j）激活更复杂的操作序列：
最后，
事实证明，在这些步骤之后，网络状态可以再次被解释为另一个程序快照。变量值已更改，token已转移到新位置，就像执行了相应的程序行一样。如果token消失，网络状态不再改变——这只有在程序计数器「超出」程序代码时才会发生，这意味着程序终止。网络的运行也类似对应程序的运行，证明完成。
3 修改
3.1 扩展
定义额外的流线型指令很容易，这些指令可以使编程更容易，并且生成的程序更具可读性和执行速度。例如，
第i行的无条件分支（GOTO j）可以实现为
可以实现为）
将常量c添加到第i行的变量（
行i上的另一种条件分支（IF V=0 GOTO j ）可以实现为
：
。只需要一个节点
此外，可以同时评估各种递增/递减指令。假设要执行以下操作：
上述方式绝不是实现图灵机的唯一途径。这是一个简单的实现，在应用程序中不一定是最佳的。
