按年被提到
20192023 · 4 次2026
机器学习与深度学习›神经科学启发的 AI·arXiv:1901.03429 · cs.LG

On the Turing Completeness of Modern Neural Network Architectures

论现代神经网络架构的图灵完备性
Jorge Pérez, Javier Marinković, Pablo Barceló · 2019

证明 Transformer 与 Neural GPU 都是图灵完备的

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 9 人首次 2019-05-02 · 最近 2025-02-04
9不同的人
9活跃月份
10讨论串
90被引(OpenAlex)

论文研究 Transformer 和 Neural GPU 这两种基于注意力和卷积的代表性架构的计算能力,证明二者仅凭计算和访问内部稠密表示的能力就是图灵完备的,不需要外部存储器。研究还找出了获得这些完备性结果所需的最小元素集合。

HN 为什么提它

评论者用它反驳「Transformer 做不了通用计算」的说法,但也有人补充:证明依赖任意精度算术,实际有限精度的实现并不满足这一条件。

其他难度 5 / 5约 40 分钟经得起时间
读之前最好知道
1图灵机与可计算性理论
2Transformer 与位置编码
3Neural GPU
4任意精度与有限精度算术

学习路径

读这篇之前,按顺序读书架上的 4 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

先看带外部记忆和栈的神经网络,再看 Transformer 与 Universal Transformer,就能理解为什么需要研究这些架构的计算能力,以及目标论文的图灵完备性证明。

  1. 1
    Neural Turing Machines神经图灵机 · 2014

    神经图灵机是最早讨论神经网络与图灵机类比的工作,给出了计算能力问题的背景。

    读可微外部记忆与读写头的设计,以及它学会的简单算法任务。

  2. 2
    Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets用栈增强的循环网络推断算法模式 · 2015

    给循环网络配上可微栈来学习算法模式,是扩展网络计算能力的同类尝试。

    读栈增强循环网络的结构,以及它能处理哪类形式语言。

  3. 3
    Attention Is All You Need注意力就是你所需要的一切 · 2017

    目标论文要证明的对象之一就是 Transformer,需要先熟悉其结构。

    读自注意力、位置编码和编码器-解码器结构;证明里要用到注意力如何取值。

  4. 4
    Universal Transformers通用 Transformer · 2018

    Universal Transformer 引入循环结构,与目标论文关于 Transformer 计算能力的讨论直接相关。

    读跨深度共享参数的循环式 Transformer,以及它与普通 Transformer 的区别。

  5. 5
    On the Turing Completeness of Modern Neural Network Architectures论现代神经网络架构的图灵完备性 · 2019 · 就是这篇

    目标论文:证明 Transformer 与 Neural GPU 在能够计算和访问内部稠密表示的前提下都是图灵完备的。

    读证明的构造思路:用注意力读取内存、用层的堆叠或循环模拟图灵机的步骤。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐bhntr3 · 2020-07

“Here's an interesting paper on the topic.”

推荐这篇相关论文,讨论哪些神经网络架构是图灵完备的
Is This a Turing Machine?原评论 ↗
引用riku_iki · 2020-09

“and per this article is turing complete: On the Turing Completeness of Modern Neural Network Architectures”

引用它说明 Transformer 是图灵完备的
Graph Representations for Higher-Order Logic and Theorem Proving (2019)原评论 ↗
引用tsimionescu · 2022-06

“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).”

贴出论文,证明 Transformer 可模拟图灵机,与 GPT-3 相关
LaMDA is not sentient原评论 ↗
引用ly3xqhl8g9 · 2022-09

“it seems that there are some architectures for Turing complete neural networks [1]”

指出已有图灵完备的神经网络架构
Ladybird: A new cross-platform browser project原评论 ↗
引用fasterik · 2023-01

“Modern neural network architectures are Turing complete [1].”

引用它证明现代神经网络架构是图灵完备的
Petals: Run 100B+ language models at home bit-torrent style原评论 ↗
引用naasking · 2023-03

“On the Turing Completeness of Modern Neural Network Architectures, On the Turing Completeness of Modern Neural Network Architectures”

直接贴出论文,说明现代神经网络架构图灵完备
Caricaturing Noam Chomsky原评论 ↗
看全部 9 条 →
引用naasking · 2023-03

“This is a common misunderstanding. Transformers are actually Turing complete:”

纠正常见误解,引用论文说明 Transformer 实际是图灵完备的
引用MacsHeadroom · 2023-04

“Transformers are turing complete: On the Turing Completeness of Modern Neural Network Architectures”

引用它说明 Transformer 是图灵完备的
There Is No A.I原评论 ↗
引用rlupi · 2025-02

“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).”

吹毛求疵:Transformer 仅在任意精度下才图灵完备,实际并非如此
Efficient Reasoning with Hidden Thinking原评论 ↗
被提交为 story · 1 次