# The Imitation Game: Turing Machine Imitator is Length Generalizable Reasoner

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning.
- Builds on 44 of its 66 references that are in the map.
- First posted on arXiv 17 Jul 2025.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

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

- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation](https://mlsanity.com/paper/2108.12409/) (2021)
- [DeepSeek-V3 Technical Report](https://mlsanity.com/paper/2412.19437/) (2024)
- [Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models](https://mlsanity.com/paper/2305.04091/) (2023)
- [InternLM2 Technical Report](https://mlsanity.com/paper/2403.17297/) (2024)
- [Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought](https://mlsanity.com/paper/2210.01240/) (2022)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Chain-of-Thought Reasoning Without Prompting](https://mlsanity.com/paper/2402.10200/) (2024)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Take a Step Back: Evoking Reasoning via Abstraction in Large Language Models](https://mlsanity.com/paper/2310.06117/) (2023)
- [Teaching Arithmetic to Small Transformers](https://mlsanity.com/paper/2307.03381/) (2023)
- [Automatic Prompt Augmentation and Selection with Chain-of-Thought from Labeled Data](https://mlsanity.com/paper/2302.12822/) (2023)
- [Randomized Positional Encodings Boost Length Generalization of Transformers](https://mlsanity.com/paper/2305.16843/) (2023)
- [Meta-Prompting: Enhancing Language Models with Task-Agnostic Scaffolding](https://mlsanity.com/paper/2401.12954/) (2024)
- [Towards System 2 Reasoning in LLMs: Learning How to Think With Meta Chain-of-Thought](https://mlsanity.com/paper/2501.04682/) (2025)
- [The CoT Collection: Improving Zero-shot and Few-shot Learning of Language Models via Chain-of-Thought Fine-Tuning](https://mlsanity.com/paper/2305.14045/) (2023)
- [Looped Transformers for Length Generalization](https://mlsanity.com/paper/2409.15647/) (2024)
- [Transformers Can Achieve Length Generalization But Not Robustly](https://mlsanity.com/paper/2402.09371/) (2024)
- [Length Generalization in Arithmetic Transformers](https://mlsanity.com/paper/2306.15400/) (2023)
- [Positional Description Matters for Transformers Arithmetic](https://mlsanity.com/paper/2311.14737/) (2023)
- [Satori: Reinforcement Learning with Chain-of-Action-Thought Enhances LLM Reasoning via Autoregressive Search](https://mlsanity.com/paper/2502.02508/) (2025)
- [The EOS Decision and Length Extrapolation](https://mlsanity.com/paper/2010.07174/) (2020)
- [Combining Generative Artificial Intelligence (AI) and the Internet: Heading towards Evolution or Degradation?](https://mlsanity.com/paper/2303.01255/) (2023)
- [Long-Short Chain-of-Thought Mixture Supervised Fine-Tuning Eliciting Efficient Reasoning in Large Language Models](https://mlsanity.com/paper/2505.03469/) (2025)
- [Location Attention for Extrapolation to Longer Sequences](https://mlsanity.com/paper/1911.03872/) (2019)

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

- [Intern-S1-MO: Long-horizon Reasoning Agent for Olympiad?Level Mathematical Problem Solving](https://mlsanity.com/paper/2512.10739/) (2025)
- [AdvancedMathBench: A Benchmark Suite for Advanced Mathematical Proof Generation and Verification](https://mlsanity.com/paper/2607.11849/) (2026)
- [Planning with Transformers: Chain of Computation and Structured Context Windows](https://mlsanity.com/paper/2607.17710/) (2026)

## Abstract (arXiv)

Length generalization, the ability to solve problems of longer sequences than those observed during training, poses a core challenge of Transformer-based large language models (LLM). Although existing studies have predominantly focused on data-driven approaches for arithmetic operations and symbolic manipulation tasks, these approaches tend to be task-specific with limited overall performance. To pursue a more general solution, this paper focuses on a broader case of reasoning problems that are computable, i.e., problems that algorithms can solve, thus can be solved by the Turing Machine. From this perspective, this paper proposes Turing MAchine Imitation Learning (TAIL) to improve the length generalization ability of LLMs. TAIL synthesizes chain-of-thoughts (CoT) data that imitate the execution process of a Turing Machine by computer programs, which linearly expands the reasoning steps into atomic states to alleviate shortcut learning and explicit memory fetch mechanism to reduce the difficulties of dynamic and long-range data access in elementary operations. To validate the reliability and universality of TAIL, we construct a challenging synthetic dataset covering 8 classes of algorithms and 18 tasks. Without bells and whistles, TAIL significantly improves the length generalization ability as well as the performance of Qwen2.5-7B on various tasks using only synthetic data, surpassing previous methods and DeepSeek-R1. The experimental results reveal that the key concepts in the Turing Machine, instead of the thinking styles, are indispensable for TAIL for length generalization, through which the model exhibits read-and-write behaviors consistent with the properties of the Turing Machine in their attention layers. This work provides a promising direction for future research in the learning of LLM reasoning from synthetic data.