# GPT is becoming a Turing machine: Here are some ways to program it

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 51 references that are in the map.
- First posted on arXiv 25 Mar 2023.

## Builds on (most cited first, 30 of 38)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models](https://mlsanity.com/paper/2206.04615/) (2022)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Rethinking the Role of Demonstrations: What Makes In-Context Learning Work?](https://mlsanity.com/paper/2202.12837/) (2022)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [Calibrate Before Use: Improving Few-Shot Performance of Language Models](https://mlsanity.com/paper/2102.09690/) (2021)
- [Scaling Language Models: Methods, Analysis & Insights from Training Gopher](https://mlsanity.com/paper/2112.11446/) (2021)
- [What Makes Good In-Context Examples for GPT-3?](https://mlsanity.com/paper/2101.06804/) (2021)
- [Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivity](https://mlsanity.com/paper/2104.08786/) (2021)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [STaR: Bootstrapping Reasoning With Reasoning](https://mlsanity.com/paper/2203.14465/) (2022)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Large Language Models Can Be Easily Distracted by Irrelevant Context](https://mlsanity.com/paper/2302.00093/) (2023)
- [PAL: Program-aided Language Models](https://mlsanity.com/paper/2211.10435/) (2022)
- [Decomposed Prompting: A Modular Approach for Solving Complex Tasks](https://mlsanity.com/paper/2210.02406/) (2022)
- [Augmented Language Models: a Survey](https://mlsanity.com/paper/2302.07842/) (2023)
- [Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoning](https://mlsanity.com/paper/2205.09712/) (2022)
- [The Impact of AI on Developer Productivity: Evidence from GitHub Copilot](https://mlsanity.com/paper/2302.06590/) (2023)
- [TALM: Tool Augmented Language Models](https://mlsanity.com/paper/2205.12255/) (2022)
- [ART: Automatic multi-step reasoning and tool-use for large language models](https://mlsanity.com/paper/2303.09014/) (2023)
- [Unsupervised Commonsense Question Answering with Self-Talk](https://mlsanity.com/paper/2004.05483/) (2020)

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

- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [PromptAgent: Strategic Planning with Language Models Enables Expert-level Prompt Optimization](https://mlsanity.com/paper/2310.16427/) (2023)
- [Leak, Cheat, Repeat: Data Contamination and Evaluation Malpractices in Closed-Source LLMs](https://mlsanity.com/paper/2402.03927/) (2024)
- [AutoFlow: Automated Workflow Generation for Large Language Model Agents](https://mlsanity.com/paper/2407.12821/) (2024)
- [Evaluating Cognitive Maps and Planning in Large Language Models with CogEval](https://mlsanity.com/paper/2309.15129/) (2023)
- [Self-Verification Improves Few-Shot Clinical Information Extraction](https://mlsanity.com/paper/2306.00024/) (2023)
- [Universal Length Generalization with Turing Programs](https://mlsanity.com/paper/2407.03310/) (2024)
- [Code Simulation Challenges for Large Language Models](https://mlsanity.com/paper/2401.09074/) (2024)
- [Autoregressive Large Language Models are Computationally Universal](https://mlsanity.com/paper/2410.03170/) (2024)
- [AIOS Compiler: LLM as Interpreter for Natural Language Programming and Flow Programming of AI Agents](https://mlsanity.com/paper/2405.06907/) (2024)
- [Code Simulation as a Proxy for High-order Tasks in Large Language Models](https://mlsanity.com/paper/2502.03568/) (2025)
- [Autonomous Tree-search Ability of Large Language Models](https://mlsanity.com/paper/2310.10686/) (2023)
- [Rule Learning as Machine Translation using the Atomic Knowledge Bank](https://mlsanity.com/paper/2311.02765/) (2023)
- [LaPuda: LLM-Enabled Policy-Based Query Optimizer for Multi-modal Data](https://mlsanity.com/paper/2403.13597/) (2024)
- [AutoGRAMS: Autonomous Graphical Agent Modeling Software](https://mlsanity.com/paper/2407.10049/) (2024)
- [PrimeScientist: Strategic Allocation of Research Effort in Autonomous Research](https://mlsanity.com/paper/2609.17846/) (2026)

## Abstract (arXiv)

We demonstrate that, through appropriate prompting, GPT-3 family of models can be triggered to perform iterative behaviours necessary to execute (rather than just write or recall) programs that involve loops, including several popular algorithms found in computer science curricula or software developer interviews. We trigger execution and description of Iterations by Regimenting Self-Attention (IRSA) in one (or a combination) of three ways: 1) Using strong repetitive structure in an example of an execution path of a target program for one particular input, 2) Prompting with fragments of execution paths, and 3) Explicitly forbidding (skipping) self-attention to parts of the generated text. On a dynamic program execution, IRSA leads to larger accuracy gains than replacing the model with the much more powerful GPT-4. IRSA has promising applications in education, as the prompts and responses resemble student assignments in data structures and algorithms classes. Our findings hold implications for evaluating LLMs, which typically target the in-context learning: We show that prompts that may not even cover one full task example can trigger algorithmic behaviour, allowing solving problems previously thought of as hard for LLMs, such as logical puzzles. Consequently, prompt design plays an even more critical role in LLM performance than previously recognized.