💻 computer science

Training Transformers as a Universal Computer

本文证明，在随机生成的 MicroPy 程序上训练的小型 Transformer 能够泛化以执行复杂的人类编写算法，从而提供了经验证据，表明标准 Transformer 可以作为通用计算机运行。

原作者： Ruize Xu, Chenxiao Yang, Yanhong Li, David McAllester

发布于 2026-04-29

📖 1 分钟阅读☕ 轻松阅读

原作者： Ruize Xu, Chenxiao Yang, Yanhong Li, David McAllester

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你有一个非常聪明但短期记忆稍显不足的机器人助手。你想教它如何运行复杂的计算机程序。问题在于，这个机器人一次只能“思考”有限数量的步骤，之后就会忘记故事的开头。如果程序太长，机器人就会迷失方向。

本文提出了解决该问题的方案。研究人员构建了一种名为MicroPy的微型简化编程语言，并训练一个标准人工智能模型（Transformer）充当通用计算机，使其能够运行用该语言编写的任何程序，甚至是它从未见过的程序。

以下是他们如何做到的，借助一些日常类比：

1. 语言：MicroPy（“乐高套装”）

请将MicroPy想象成并非像 Python 或 C++ 那样的完整编程语言，而是一套非常严格、简化的乐高积木指令。

它包含用于执行诸如“如果这样，就那样”、“查找此值”或“更改此对象”等任务的基础积木块。
由于它是“通用”语言（理论上可执行任何计算）的简化版本，如果人工智能学会了理解这些特定的乐高积木，理论上它就能构建任何东西。

2. 问题：“长故事”难题

通常，当人工智能尝试解决数学问题或逐步运行代码（这种方法称为“思维链”）时，它会写下每一个步骤。

类比：想象你在读一本书，但你只能在脑海中保留最后 10 页的内容。如果这本书有 1000 页长，当你读到结尾时，你已经忘记了开头。你无法解开谜团，因为你忘了第一章里的反派是谁。
用计算机术语来说，随着长计算的进行，“上下文窗口”（人工智能的短期记忆）会过快被填满。

3. 解决方案：PENCIL（“清洁小队”）

研究人员使用了一种名为PENCIL的特殊技巧。将 PENCIL 想象成一个神奇的“清洁小队”，帮助人工智能管理其记忆。

工作原理：当人工智能完成一个小子任务（例如计算一个数字或完成一个函数）时，PENCIL 小队会立即从人工智能的记忆中擦除杂乱的中间步骤，仅保留最终结果。
类比：想象你在烹饪一顿复杂的饭菜。与其让所有脏锅、平底锅和食材包装纸都堆在操作台上（最终会占满整个厨房），不如在使用后立即清洗餐具并收好。你只把做好的菜留在操作台上。这样，你就可以在小厨房里烹饪盛大的宴席，而不会空间不足。
这使得人工智能能够运行比其训练数据长60 倍的程序，因为它从不让它的“厨房操作台”变得杂乱无章。

4. 训练：随机练习与真实测试

研究人员并非通过向人工智能展示著名的人类编写代码来训练它。相反，他们生成了数百万个随机的、无意义的 MicroPy 程序。

类比：这就像教学生下棋，方法是让他们与一个会做出随机、荒谬走法的计算机对弈。学生学会的是棋子如何移动以及如何吃子的规则，而不是死记硬背特定的著名棋局。
一旦人工智能从随机练习中掌握了这些规则，研究人员就用真实的、人类编写的程序来测试它，这些程序执行实际任务，例如：
- 复制和翻转位（二进制数据）。
- 对大型二进制数进行加法和乘法运算。
- 解决逻辑谜题（SAT 问题）。

5. 结果：通用计算机

结果令人惊讶且完美。

人工智能在所有人类编写的测试中达到了100% 的准确率。
尽管测试程序比人工智能在训练期间见过的任何程序都更长、更复杂，但它完美地处理了它们。
该论文声称，这证明了一个标准人工智能模型可以被训练成充当通用计算机。它不仅仅是死记硬背答案，而是学会了执行指令的逻辑，使其能够泛化到完全新的、未见过的程序。

总结

简而言之，这篇论文表明，如果你给一个标准人工智能一种简化的语言来学习，并提供一个“记忆清洁器”（PENCIL）来帮助它管理长任务，它就能学会充当通用计算机。它能够执行从未见过的指令并完美执行，证明这些模型确实能够学会“思考”和计算，而不仅仅是预测下一个词。

以下是论文《将 Transformer 训练为通用计算机》的详细技术总结。

1. 问题陈述

尽管理论研究表明，增强思维链（CoT）的 Transformer 具有计算通用性（能够模拟图灵机），但在表达能力（它们理论上能表示什么）与可学习性（它们实际上能通过基于梯度的优化学到什么）之间存在显著差距。

当前的挑战包括：

泛化失败：模型在长度泛化（例如，对训练集中未见过的更长数字进行加法）和组合泛化（解决原语的新颖组合）方面表现困难。
上下文瓶颈：标准 CoT 需要 $O(T)$ 的上下文长度，其中 $T$ 是任务的时间复杂度。这使得在有限的上下文窗口内对长而复杂的程序进行训练和推理变得不可行。
缺乏通用学习：以往训练神经解释器的尝试通常依赖于特定的、预先设计的函数或专用架构，未能证明标准 Transformer 能够学习解释一种通用的、图灵完备的语言。

本文解决的核心问题是：能否训练一个标准 Transformer 充当通用计算机，使其能够泛化到未见过的程序和长度？

2. 方法论

作者提出了一个框架，结合了一种新的编程语言、一种内存高效的执行脚手架以及特定的训练方案。

A. MicroPy：一种可计算的通用语言

作者设计了 MicroPy，这是一种简化但图灵完备的面向对象编程语言。

语义：它依赖于一组有限的检索和重写规则。
- 检索：从上下文（栈帧或状态）中查找函数定义、变量绑定或属性值。
- 重写：根据当前状态将原语（例如 IF、SEQ、LookupAttr）简化为更简单的表达式。
结构：程序由过程定义和表达式组成。执行涉及表达式的逐步简化，管理可变状态（对象的属性）和栈帧（用于局部变量）。
目标：通过学习这些有限规则，模型能够解释任何 MicroPy 程序，从而有效地充当通用解释器。

B. PENCIL 脚手架：有界上下文执行

为了解决上下文长度瓶颈（ $O(T)$ ），作者利用了 PENCIL（来自 Yang 等人，2025）。

机制：PENCIL 引入了一条重写规则，用于回收已完成的中间计算。当一个子计算（一个栈帧）完成时，中间推理步骤会被擦除，仅保留最终结果。
复杂度：这将上下文长度限制为 $O(S)$ （空间复杂度），而不是 $O(T)$ （时间复杂度）。
类比：它的作用类似于编程语言中的栈规范：一旦函数返回，其局部栈帧就会被弹出，即使对于长时间运行的程序，也能保持上下文窗口大小可控。

C. 训练数据生成

该模型在由随机生成的 MicroPy 程序生成的执行轨迹上进行训练。

两个采样器：
1. 程序级采样器：通过概率上下文无关文法生成多样化的句法结构。
2. 计划采样器：通过采样目标“计划”（栈结构）并编译程序以实现该计划，确保覆盖罕见的运行时配置（特定的栈骨架和检索模式）。
监督：训练目标是对逐步执行轨迹进行下一个 token 预测。给定当前上下文，模型预测下一个重写步骤（检索或局部简化）。
约束：训练程序被限制在 128 行轨迹以内，以确保多样性而不使模型不堪重负，而评估则测试更长的程序。

D. 模型架构

架构：一个仅解码器的 Transformer（5950 万参数），带有 RoPE（旋转位置嵌入）。
优化：对嵌入使用 AdamW，对二维矩阵参数使用 Muon。
输入：过程定义 + 待评估表达式 + 当前状态/栈。
输出：执行轨迹中的下一步（逐 token）。

3. 主要贡献

MicroPy 语言设计：创建了一种图灵完备的语言，其语义基于一组有限的检索和重写规则，促进了组合学习。
通用学习的实证证据：首次证明，仅通过在通用语言的随机轨迹上进行训练，标准 Transformer 就能泛化以执行其从未见过的复杂、人类编写的程序。
PENCIL 集成：成功应用 PENCIL 脚手架，使 Transformer 能够在固定上下文窗口内执行轨迹长度高达训练所见长度60 倍的程序。
完美泛化：在涉及位操作、算术和逻辑求解的保留任务上实现了 100% 的准确率，证明了强大的组合泛化和长度泛化能力。

4. 实验结果

该模型在保留的、人类编写的 MicroPy 程序上进行了评估，这些程序比训练数据更长且语义更丰富。

评估任务：
- 位操作：复制和翻转链表中的位。
- 算术：二进制加法和乘法（使用位串表示）。
- 逻辑：SAT 验证和 SAT 求解（使用回溯搜索）。
性能：
- 准确率：在测试的上下文窗口内，模型在所有任务上均实现了100% 的 token 级准确率。
- 长度泛化：尽管训练程序被限制在 128 行，该模型成功执行了长达 7,552 行轨迹的程序。
- 分布差距：训练程序分布与测试套件之间几乎没有重叠，证实模型学习的是执行的规则，而非死记硬背特定程序。
操作覆盖：训练生成器涵盖了测试套件中使用的每种操作类型（例如 If、LookupVar、TailApp），确保模型在训练期间看到了所有必要的原语。

5. 意义与启示

通用计算是可学习的：本文提供了强有力的实证证据，表明计算通用性不仅是 Transformer 的理论属性，而且是通过在合适语言上进行标准下一个 token 预测训练即可获得的能力。
组合性的归纳偏置：结果表明，当与上下文管理脚手架（如 PENCIL）配对时，Transformer 具有非常适合短语结构和组合语义的归纳偏置。这反映了编程语言和自然语言的结构。
弥合差距：这项工作弥合了“神经计算机”（学习 I/O 轨迹）与形式解释器之间的差距，表明单个模型可以学习执行一种形式的、图灵完备的语言。
未来方向：作者指出，使学习编程语言解释器成为可能的相同机制，可能解释了 Transformer 为何在自然语言任务中如此有效，因为两者都依赖于组合语义。未来的工作可以将此扩展到更丰富的语言以及无需显式执行轨迹的推理。

总之，本文证明，只要执行过程经过脚手架管理以高效处理上下文，标准 Transformer 就可以被训练为通用计算机，能够以完美的准确率执行图灵完备语言中的任意程序。