多年以来,让我自己来回答这个问题。
图灵完备性
- 和图灵机一样强大。
- 需要无限的内存。也就是说,在实践中,没有任何物理设备可以成为图灵完备。
- 考虑一个普通的个人电脑:
- 一个特定的物理实例不是图灵完备,因为它有有限的内存。
- 但是,考虑将PC的概念视为可以根据需要添加内存的东西。当您添加更多内存时,所有程序仍将以相同的方式工作。对于任何给定的输入和任何给定的程序,都存在最大数量的内存,使其应该工作。(现在让我们不要在
int64
内存地址限制或类似事情上卖弄。这些是技术限制,可以通过大整数等解决。)因此,我们可以说 PC的概念是图灵完备的。这也被称为抽象机器。
因此,区分特定的机器或设备(PC、RNN、人脑)和编程语言或编程语言的抽象机器。编程语言通常没有使用内存的限制,因此编程语言可以是图灵完备的。请参见官方C语言标准定义,它使用抽象机器来定义语义。主要问题是,这些特定类别(PC、RNN、人脑)允许制定抽象机器变体,并且这些抽象机器变体是否图灵完备?
- 图灵完备性实际上主要涉及内存概念。考虑任何有限状态机/自动机(FSA),以及对外部内存的某些访问。根据内存类型,您将进入不同的Chomsky层次类别:
循环神经网络(RNN)
关于神经网络的计算能力
一篇经常被引用的论文是On the computational power of neural nets, Siegelmann & Sonntag, 1992,它指出RNNs是图灵完备的。
该论文假设我们有没有限制的分子/分母有理数,即无限内存被编码为有理数或无限精度的浮点数。也可以参见here。通常我们不会以操作有理数(无限制)的方式对NN进行建模。当我们将自己限制为具有有限精度权重和激活的(R)NN时,论文中的证明就会破裂,不再适用。因此,这篇论文并不那么相关。
还有一篇较新的论文On the Practical Computational Power of Finite Precision RNNs for Language Recognition, Weiss et al, 2018,它正好解决了这个问题。
通用逼近器
众所周知,大多数标准NN都是
通用逼近器。这意味着,对于任何函数(非常数、有界和连续),只要给定一些允许的阈值,就可以构建一个NN,使其在允许的阈值内逼近该函数。
这是关于有限维向量空间的。当我们谈论可计算性时,我们谈论序列,因此我们有一个无限维向量空间。因此,这个属性并不那么相关。
没有外部记忆
问题是如何定义
标准RNN的概念。在上述论文中,它假设激活具有无限精度。但我认为这不是一个合理的RNN概念,因为你永远不会有这个。而且由于受到限制,因此没有其他方法可以使标准RNN具有无限记忆。
因此,明确说明:
没有外部记忆,标准RNN,以及
LSTM 不是图灵完备的。
也没有直接的方法可以定义可以根据需要添加内存的
RNN概念。
RNN的记忆是最近的隐藏激活。增加更多的内存意味着改变NN,即添加新的神经元,从而添加其内部工作。这就像改变程序本身。
有外部记忆
有
神经图灵机(NTM)和一些类似的模型,它们具有某种外部存储器。在这里,我们可以直接考虑一个
NTM的概念,其中您可以按需添加内存。因此,我们可以说
NTM的概念是图灵完备的。
有一些细节需要适应头部使用的注意力类型。该模型的后续是
可微分神经计算机(DNC),它明确解决了这个问题,并且还具有一些显式的机制来添加内存。
学习/训练
我们主要讨论了理论计算能力。一个非常不同的问题是NN是否可以学习这样的功能。即是否训练(梯度搜索)会导致NN学习到可计算的函数。
人脑
我们可以将人类大脑(或任何大脑)解释为一种复杂的神经网络。我们也可以问一个问题,即人类大脑(模型)是否是图灵完备的。参见
这里。这个问题很棘手。直觉会说我们能够执行任何类型的计算,因此人类大脑是图灵完备的。然而,我们在这里概述的论点表明RNN不是图灵完备的。重要的是记忆效应。在某些输入上,人类大脑的记忆容量已经不足以操作。因此,我们需要外部记忆。因此,人类大脑加上外部存储器是图灵完备的,显然。但这可能不是有趣的问题(也假设人类大脑可以尽可能大地编码任何图灵机程序,因此没有人类大脑的上限大小,这实际上并不正确)。更有趣的是仅考虑人类大脑本身,没有任何外部存储器。或者基本上,如何定义
抽象机器或
人类大脑的概念?这个概念是否允许无限的内存?这个定义是否很简单?
在人脑中,记忆的某个方面与标准循环神经网络不同:它可以高度概括,并且访问特定激活的寻址机制也不同。此外,它具有某种自适应权重(但仅能存储有限信息)。因此,考虑到这一点,它实际上已经比普通循环神经网络更类似于神经图灵机。人脑中有许多不同类型的记忆。有些像循环神经网络一样静态(例如当前激活),而其他类型允许进行联想记忆,就像神经图灵机一样。因此,人脑也类似于个人电脑,后者也具有有限的内存,而个人电脑的概念具有无限的内存。
因此,也许我们可以说人脑的概念也具有无限的内存,由于联想记忆,也可以足够大以编码任何程序,因此人脑的概念是图灵完备的。也许应该称之为“抽象人脑”(抽象机的一个实例)。