看到另外一种“图灵完备”的解释

[James369]

在看 AI 的时候看到的：所有的图灵机都可以被一个由使用 Sigmoid 型激活函数的神经元构成的全连接循环网络来进行模拟。

完全看不懂什么意思？

[phpfpm]

1 你确定你知道什么是图灵机？
2 你确定你知道什么是激活函数，以及 sigmoid 是什么？
3 你确定你知道全连接循环网络是什么？

知道以上三个，连在一起为啥不懂呢

[liuser666]

本质上是因为 sigmoid 型激活函数的神经网络可以模拟任何函数。

[czfy]

Sigmoid 型激活函数
激活函数：节点对输入处理的规则，最简单的处理规则是 f(x)=kx+b ，神经网络里的激活函数通常是非线性的
Sigmoid 函数：有界、可微的实函数，在实数范围内均有取值，且导数恒为非负，有且只有一个拐点。在神经网络里，S 型函数通常特指 Logistic 函数

神经元：节点

全连接循环网络
全连接网络：第 n-1 层的任意节点，都和第 n 层的所有节点有连接
循环网络：Recurrent neural network ，RNN ，循环神经网络

基于这些 google 出来的信息，这句话的意思我推测大概是：
包含上面这些元素的人工神经网络，可以对图灵完备的某个东西进行模拟

[lyminghao]

这个没毛病啊

[geelaw]

单从这句话确实看不懂，至少我并不知道 RNN 和它“所计算的函数”是如何定义的（有很多细节会影响结论是否成立、结论是否令人意外）。

看这篇应该就明白了 https://www.sciencedirect.com/science/article/pii/089396599190080F

另外，这并不是 Turing 完备的“解释”，这句话是在利用 Turing 完备的词义，而不是在告诉你 Turing 完备的词义。（类比：这家火锅很辣，这句话没有在解释什么是“辣”，而是在利用“辣”的意思给那家火锅下判断。）

[ipwx]

这种结论一般都是构造法证明。

首先图灵机是什么有清晰的定义。然后就是怎么用 sigmoid + rnn 表达任意给定的图灵机了。

随便搜一下可得：

Turing Completeness of Bounded-Precision Recurrent Neural Networks
https://openreview.net/forum?id=IWJ9jvXAoVQ

这篇 2021 年的 poster 说，前人的工作需要假定无穷精度的 RNN 才能表达任意图灵机。现在他们可以用有限精度 RNN 来表达了（可喜可贺