Towards Training Transformers as a Universal Computer
cs.AI
Submitted: 2026-04-28
Updated: 2026-10-29
Comments: Findings of EMNLP 2026. 22 pages, 5 figures, 3 tables. Project page: https://www.micropy.org
Journal ref: Findings of the Association for Computational Linguistics: EMNLP 2026, pages 48933-48954
Code: https://github.com/karpathy/nanochat
License: http://creativecommons.org/licenses/by/4.0/
The gist: We demonstrate that a small transformer can learn to execute programs in MicroPy, a simplified yet computationally universal programming language.
Terminology
Abstract
We demonstrate that a small transformer can learn to execute programs in MicroPy, a simplified yet computationally universal programming language. Given procedure definitions together with an expression to evaluate, the transformer predicts small-step execution using PENCIL scaffolding for space-efficient execution within a bounded context window. After training on randomly generated, semantically arbitrary MicroPy programs, the learned transformer generalizes to held-out human-written programs including bit copying and flipping, binary addition and multiplication, and SAT verification and solving. The trained model exhibits out-of-distribution generalization: it correctly evaluates programs drawn from a substantially different distribution than the one used to generate its training data. Since MicroPy can express any computation, our results provide empirical evidence that a standard transformer can be trained to act as a universal computer when paired with PENCIL scaffolding. Project page: https://www.micropy.org
Sources
- How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad
- Making Neural Programming Architectures Generalize via Recursion
- Position Coupling: Improving Length Generalization of Arithmetic Transformers Using Task Structure
- Faith and Fate: Limits of Transformers on Compositionality
- Looped Transformers as Programmable Computers
- Universal Length Generalization with Turing Programs
- Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
- COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
- Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks
- Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
- Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
- Code Execution with Pre-trained Language Models
- Transformers Can Do Arithmetic with the Right Embeddings
- The Expressive Power of Transformers with Chain of Thought
- Show Your Work: Scratchpads for Intermediate Computation with Language Models
- Learning Compositional Neural Programs with Recursive Tree Search and Planning
- Neural Programmer-Interpreters
- Sudoku-Bench: Evaluating creative reasoning with Sudoku variants
- PENCIL: Long Thoughts with Short Memory
- Transformer-Based Models Are Not Yet Perfect At Learning to Emulate Structural Recursion
Related papers
- Multi-Objective Structured Pruning of LLMs for Latency and Model Size Optimization
- MAVEN-T: Reinforced Heterogeneous Distillation for Real-Time Multi-Agent Trajectory Prediction
- Model Discovery Agent: LLM-assisted Bayesian experiment design for data-efficient discovery of mechanistic world models
- Embeddings for Preferences, Not Semantics
- Can We Trust Item Response Theory for AI Evaluation?
- Diagnosing Task Insensitivity in Language Agents