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中定义）输出为零（）;在大多数指令节点都有一个单位输出ut()，所有其他指令节点的输出为零，变量节点的输出值为非负整数。如果所有指令节点的输出都为零，则状态为最终状态。一个合法的网络状态可以直接解释为一个程序“快照”——如果程序计数器在第i行，则相应的变量值存储在变量节点中。网络状态的变化由非零节点激活。首先关注变量节点，结果发现它们表现为积分器，节点之前的内容循环回到同一个节点。从可变节点到其他节点的唯一连接具有负权重-这就是包含零的节点不会改变的原因，因为非线性原因(2)。接下来，指定指令节点。假设时间k的唯一非零指令节点---这对应于程序代码行i中的程序计数器。如果程序中的第i行是，则网络向前一步的行为可以表示为（只显示受影响的节点）结果新的网络状态再次合法。与程序代码相比，这对应于程序计数器被转移到第i+1行。另一方面，如果程序中的第i行是，向前一步的行为是这样的，除了将程序计数器转移到下一行之外，变量V的值也减少了。如果第i行，网络的操作将是相同的，只是变量V的值增加了。第i行的条件分支操作(IFGOTOj)激活了一个更复杂的操作序列：最后，事实证明，在这些步骤之后，网络状态可以再次被解释为另一个程序快照。变量值发生了变化，代币被转移到新的位置，就好像相应的程序行已经被执行了一样。如果令牌消失，网络状态不再改变——这只有在程序计数器“超过程序代码”时才有可能，这意味着程序终止。网络的运行类似于相应程序的运行，并且3修改3.1扩展很容易定义额外的精简指令，可以使编程更容易，生成的程序可读性更强，执行速度更快。例如，第i行的无条件分支(GOTOj)可以实现为将常量c添加到第i行的变量()可以实现为第i行的另一个条件分支(IFV=0GOTOj)可以实现为此外，可以同时评估各种递增/递减指令。假设您要执行以下操作：.只需要一个节点：上述方法绝不是实现图灵机的唯一方法。这是一个简单的实现，在应用程序中可能不一定是最佳的。3.2矩阵的制定上述构造也可以用矩阵的形式来实现。基本思想是在进程状态s中存放变量值和“程序计数器”，让状态转移矩阵A表示节点间的链接。矩阵结构上的操作可以定义为离散时间动态过程，其中非线性向量值函数现在按元素定义，如(2)中所示。状态转移矩阵A的内容很容易从网络公式中解码出来——矩阵元素是节点之间的权重。该矩阵公式类似于[3]中提出的“概念矩阵”框架。4例子假设要实现一个简单的函数y=x，即将输入变量x的值传递给输出变量y。使用语言可以将其编码为（让“入口点”现在不是第一行而是第三行）：生成的感知器网络如图2所示。实线表示正连接（权重1），虚线表示负连接连接（权重-1）。与图1相比，通过在节点中加入延迟元件，重新绘制并简化了网络结构。图2一个简单程序的网络实现在矩阵形式中，上面的程序看起来像矩阵A中的前两行/列对应于指向代表两个变量Y和X的节点的链接，接下来的三行代表三个程序行(1,2,和3)，最后两个表示分支指令所需的附加节点（3'和3''）。那么初始（迭代前）和最终（迭代后，找到不动点时）状态如果变量节点的值将严格保持在0和1之间，则动力系统（3）的运行将是linear，函数完全没有影响。原则上，然后可以在分析中使用线性系统理论。例如，在图。图3显示了状态转移矩阵A的特征值。即使上例中单位圆外有特征值，但非线性使得迭代总是稳定的。事实证明迭代总是在步骤where之后收敛。图3一个简单程序的“特征值”5讨论5.1理论方面事实证明，图灵机可以编码为感知器网络。根据定义，所有可计算函数都是图灵可计算的——在可计算性理论的框架内不存在更强大的计算系统。这就是为什么可以得出结论-循环感知器网络（如上所示）是（又一种）图灵机形式。这种等价的好处是可计算性理论的结果很容易获得——例如，给定一个网络和一个初始状态，就不可能判断这个过程是否最终会停止。上述理论等价性并没有说明计算效率。网络中发生的不同机制可以使某些功能在此框架中比在传统的图灵机实现（以及今天的计算机）中更好地实现。至少在某些情况下，例如，可以通过在快照向量中允许多个“程序计数器”来并行化算法的网络实现。网络的操作严格是局部的，而不是全局的。一个有趣的问题出现了，例如，是否可以在网络环境中更有效地攻击NP完全问题！与语言相比，网络实现具有以下“扩展”：变量可以是连续的，而不仅仅是整数值。事实上，（理论上）表示实数的能力使得网络实现比语言更强大，所有用语言表示的数字都是有理数。各种“程序计数器”可以同时存在，控制权的转移可以是“模糊的”，即指令节点提供的程序计数器值可能是非整数。次要扩展是可自由定义的程序入口点。这可能有助于简化程序-例如，变量的复制是在上面的三行程序中完成的，而名义解决方案（参见[1]）需要七行和一个额外的局部变量。与原始程序代码相比，矩阵公式显然是比程序代码更“连续”的信息表示——参数可以（经常）修改，而迭代的结果不会突然改变。这种“冗余”在某些应用中可能很有用。例如，当使用遗传算法(GA)进行结构优化时，可以使遗传算法中使用的随机搜索策略更有效：在系统结构发生变化后，连续成本函数的局部最小值可以是使用一些传统技术进行搜索（参见[4]）。通过示例学习有限状态机结构，如[5]中所述，可以学习：在这种更复杂的情况下，也采用迭代增强网络结构的方法。不仅神经网络理论可以从上述结果中获益——只要看看动力系统方程（3），很明显，在可计算性理论领域发现的所有现象也以简单的形式存在——寻找非线性动力过程。例如，停机问题的不可判定性是系统论领域的一个有趣的贡献：对于任何表示为图灵机的决策过程，都存在违反该过程的形式(3)的动力系统——例如，它不可能构建通用的稳定性分析算法。5.2相关工作所呈现的网络结构与递归派生的Hopfield神经网络范式之间存在一些相似之处（例如，参见[2]）。在这两种情况下，“输入”都被编码为网络中的初始状态，而“输出”则在迭代后从网络的最终状态中读取。Hopfield网络的固定点是一个预编程的模式模型，输入是一个“噪声”模式——网络可以用来增强损坏的模式。(2)中非线性函数的前景使得上述“图灵网络”中可能的状态数无限多。与单元输出始终为-1或1的Hopfield网络相比，可以看出，理论上，这些网络结构有很大不同。例如，虽然Hopfield网络中的稳定点集是有限的，但以图灵网络为代表的程序通常具有无限多的可能结果。Hopfield网络的计算能力在[6]中进行了讨论。Petri网是建模基于事件和并发系统的强大工具[7]。Petri网由位和转换以及连接它们的弧组成。每个地方可能包含任意数量的代币，代币的分布称为Petri网的代币。如果转换的所有输入位置都被标记占用，转换可能会触发，从每个输入位置移除一个标记并向其每个输出位置添加一个标记。可以证明，具有附加抑制弧的扩展Petri网也适用于图灵机（参见[7]）。上述图灵网与Petri网的主要区别在于Petri网的框架更为复杂，具有专门定制的结构，不能用简单的一般形式（3）来表达。参考1Davis,M.和Weyuker,E.：可计算性、复杂性和语言——理论计算机科学基础。学术出版社，纽约，1983.2Haykin,S.：神经网络。综合基础。MacmillanCollegePublishing，纽约，1994.3Hy?tyniemi,H.：相关性——智力的基石？In?lynulottuvuudetjaoppihistoria（智能的历史和维度），芬兰人工智能协会，1995年，第199--226.4页Hy?tyniemi,H.和Koivo,H.：基因、代码和动态系统。在第二届北欧遗传算法研讨会(NWGA'96)的记录中，芬兰瓦萨，1996年8月19--23日。5Manolios,P.和Fanelli,R.：一阶递归神经网络和确定性有限状态自动机。神经计算6,1994,pp.1155--1173.6Orponen,P.：具有隐藏单元的离散Hopfield网络的计算能力。神经计算8,1996,pp.403--415.7Peterson,J.L.：Petri网理论和t系统建模。Prentice--Hall，新泽西州恩格尔伍德悬崖，1981年。参考资料：http://users.ics.aalto.fi/tho/stes/step96/hyotyniemi1/
