mlsanityData to 7 Oct 2026

Training Transformers as a Universal Computer

arXiv 2604.25166 ↗First posted 28 Apr 2026cs.AIcited by 1

Not on the map. Why?

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.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 27 of its 34 references that are in the map. First posted on arXiv 28 Apr 2026.

Builds on

27 of 34 references.

References · 27

  1. 2017Attention Is All You Needcited by 59,932
  2. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  3. 2020Retrieval-Augmented Generation for Knowledge-Intensive NLP Taskscited by 9,160
  4. 2021RoFormer: Enhanced Transformer with Rotary Position Embeddingcited by 4,581
  5. 2022Large Language Models are Zero-Shot Reasonerscited by 4,323
  6. 2023Lost in the Middle: How Language Models Use Long Contextscited by 3,383
  7. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  8. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 496
  9. 2019Measuring Compositional Generalization: A Comprehensive Method on Realistic Datacited by 280
  10. 2020COGS: A Compositional Generalization Challenge Based on Semantic Interpretationcited by 260
  11. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 256
  12. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 198
15 more
  1. 2023Augmenting Language Models with Long-Term Memorycited by 186
  2. 2014Learning to Executecited by 105
  3. 2015Neural Programmer-Interpreterscited by 96
  4. 2022Compositional Semantic Parsing with Large Language Modelscited by 95
  5. 2024Transformers Can Achieve Length Generalization But Not Robustlycited by 82
  6. 2024Transformers Can Do Arithmetic with the Right Embeddingscited by 77
  7. 2017Making Neural Programming Architectures Generalize via Recursioncited by 35
  8. 2024How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpadcited by 35
  9. 2023Code Execution with Pre-trained Language Modelscited by 33
  10. 2025PENCIL: Long Thoughts with Short Memorycited by 31
  11. 2024Position Coupling: Improving Length Generalization of Arithmetic Transformers Using Task Structurecited by 22
  12. 2025Sudoku-Bench: Evaluating creative reasoning with Sudoku variantscited by 21
  13. 2019Learning Compositional Neural Programs with Recursive Tree Search and Planningcited by 17
  14. 2024Transformer-Based Models Are Not Yet Perfect At Learning to Emulate Structural Recursioncited by 14
  15. 2024Can Large Language Models Reason? A Characterization via 3-SATcited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Recursive Language Models Generalize Out of Domaincited by 0