# Training Transformers as a Universal Computer

arXiv: https://arxiv.org/abs/2604.25166 · HTML: https://mlsanity.com/paper/2604.25166/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 34 references that are in the map.
- First posted on arXiv 28 Apr 2026.

## Builds on (most cited first, 27 of 27)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Measuring Compositional Generalization: A Comprehensive Method on Realistic Data](https://mlsanity.com/paper/1912.09713/) (2019)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Augmenting Language Models with Long-Term Memory](https://mlsanity.com/paper/2306.07174/) (2023)
- [Learning to Execute](https://mlsanity.com/paper/1410.4615/) (2014)
- [Neural Programmer-Interpreters](https://mlsanity.com/paper/1511.06279/) (2015)
- [Compositional Semantic Parsing with Large Language Models](https://mlsanity.com/paper/2209.15003/) (2022)
- [Transformers Can Achieve Length Generalization But Not Robustly](https://mlsanity.com/paper/2402.09371/) (2024)
- [Transformers Can Do Arithmetic with the Right Embeddings](https://mlsanity.com/paper/2405.17399/) (2024)
- [How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad](https://mlsanity.com/paper/2406.06467/) (2024)
- [Making Neural Programming Architectures Generalize via Recursion](https://mlsanity.com/paper/1704.06611/) (2017)
- [Code Execution with Pre-trained Language Models](https://mlsanity.com/paper/2305.05383/) (2023)
- [PENCIL: Long Thoughts with Short Memory](https://mlsanity.com/paper/2503.14337/) (2025)
- [Position Coupling: Improving Length Generalization of Arithmetic Transformers Using Task Structure](https://mlsanity.com/paper/2405.20671/) (2024)
- [Sudoku-Bench: Evaluating creative reasoning with Sudoku variants](https://mlsanity.com/paper/2505.16135/) (2025)
- [Learning Compositional Neural Programs with Recursive Tree Search and Planning](https://mlsanity.com/paper/1905.12941/) (2019)
- [Transformer-Based Models Are Not Yet Perfect At Learning to Emulate Structural Recursion](https://mlsanity.com/paper/2401.12947/) (2024)
- [Can Large Language Models Reason? A Characterization via 3-SAT](https://mlsanity.com/paper/2408.07215/) (2024)

## Built on by (most cited first, 1 of 1)

- [Recursive Language Models Generalize Out of Domain](https://mlsanity.com/paper/2609.20831/) (2026)

## Abstract (arXiv)

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, meaningless MicroPy programs, the learned transformer generalizes to various human-written programs including bit copying and flipping, binary addition and multiplication, and SAT verification and solving. We note that the trained model can achieve out-of-distribution generalization; i.e., evaluate novel programs from distribution on programs. Since MicroPy can express any computation, our results provide empirical evidence that a standard transformer can be trained to act as a universal computer.