前馈神经网络的图灵完备性？

Question

我读到 RNN 是图灵完备的，但前馈神经网络 (FFN) 不是。 但是基于万能逼近定理，FFN可以在给定足够节点的情况下模拟任意函数，而且我们也知道lambda Church演算（基于无状态函数）相当于图灵机，为什么FFN不能通过模拟任意函数来实现图灵完备在教堂微积分中？

谢谢！

Answer 1

我认为你在这里做出了错误的假设，因此存在明显的悖论。 通用逼近定理指出，具有包含有限数量神经元的单个隐藏层的前馈网络可以在紧凑子集上逼近连续函数（wiki）。图灵机定理涵盖了更广泛的函数，包括“离散”函数。 据我所知，没有证据表明 FFN 是或不是图灵完备的（很高兴在这里得到纠正）。尽管存在一个

证明

，RNN 是图灵完备的（正如你所说）。

Answer 2

我认为很明显，FFNN 还可以实现任何离散函数（给定足够的宽度和深度），因此更大的 FFNN 可以实现任何图灵机的转换函数。

我也没有看到正式的证明，但它似乎直接来自 1989 年的论文。