“Here's an interesting paper on the topic.”
On the Turing Completeness of Modern Neural Network Architectures
证明 Transformer 与 Neural GPU 都是图灵完备的
论文研究 Transformer 和 Neural GPU 这两种基于注意力和卷积的代表性架构的计算能力,证明二者仅凭计算和访问内部稠密表示的能力就是图灵完备的,不需要外部存储器。研究还找出了获得这些完备性结果所需的最小元素集合。
评论者用它反驳「Transformer 做不了通用计算」的说法,但也有人补充:证明依赖任意精度算术,实际有限精度的实现并不满足这一条件。
学习路径
读这篇之前,按顺序读书架上的 4 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出先看带外部记忆和栈的神经网络,再看 Transformer 与 Universal Transformer,就能理解为什么需要研究这些架构的计算能力,以及目标论文的图灵完备性证明。
- 1
- 2
给循环网络配上可微栈来学习算法模式,是扩展网络计算能力的同类尝试。
读栈增强循环网络的结构,以及它能处理哪类形式语言。
- 3
- 4
Universal Transformer 引入循环结构,与目标论文关于 Transformer 计算能力的讨论直接相关。
读跨深度共享参数的循环式 Transformer,以及它与普通 Transformer 的区别。
- 5On the Turing Completeness of Modern Neural Network Architectures
目标论文:证明 Transformer 与 Neural GPU 在能够计算和访问内部稠密表示的前提下都是图灵完备的。
读证明的构造思路:用注意力读取内存、用层的堆叠或循环模拟图灵机的步骤。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“and per this article is turing complete: On the Turing Completeness of Modern Neural Network Architectures”
“Here is a paper [0] showing this for the Transformer architecture that is quite relevant to GPT-3 (not sure if LaMDA is also based on this).”
“it seems that there are some architectures for Turing complete neural networks [1]”
“Modern neural network architectures are Turing complete [1].”
“On the Turing Completeness of Modern Neural Network Architectures, On the Turing Completeness of Modern Neural Network Architectures”
看全部 9 条 →
“This is a common misunderstanding. Transformers are actually Turing complete:”
“Transformers are turing complete: On the Turing Completeness of Modern Neural Network Architectures”
“LLMs based on transformers are not Touring complete (nitpick: they are but only if you use arbitrary precision math, which is not the case in practical implementation On the Turing Completeness of Modern Neural Network Architectures).”
- On the Turing Completeness of Modern NN Architectures (Transformer, Neural GPU) ↗che_shr_cat · 2019-05-02 · 2 分