# TuringQ: Benchmarking AI Comprehension in Theory of Computation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Mathematical reasoning, one of 17 directions in LLM reasoning.
- Builds on 17 of its 27 references that are in the map.
- First posted on arXiv 9 Oct 2024.

## Placed in

- LLM reasoning / [Mathematical reasoning](https://mlsanity.com/lr/mathematical-reasoning/)

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [QLoRA: Efficient Finetuning of Quantized LLMs](https://mlsanity.com/paper/2305.14314/) (2023)
- [Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models](https://mlsanity.com/paper/2206.04615/) (2022)
- [Evaluating Large Language Models: A Comprehensive Survey](https://mlsanity.com/paper/2310.19736/) (2023)
- [Who Validates the Validators? Aligning LLM-Assisted Evaluation of LLM Outputs with Human Preferences](https://mlsanity.com/paper/2404.12272/) (2024)
- [Domain Specialization as the Key to Make Large Language Models Disruptive: A Comprehensive Survey](https://mlsanity.com/paper/2305.18703/) (2023)
- [Calibrating the Confidence of Large Language Models by Eliciting Fidelity](https://mlsanity.com/paper/2404.02655/) (2024)
- [Evaluating Mathematical Reasoning of Large Language Models: A Focus on Error Identification and Correction](https://mlsanity.com/paper/2406.00755/) (2024)
- [Can Large Language Models be Trusted for Evaluation? Scalable Meta-Evaluation of LLMs as Evaluators via Agent Debate](https://mlsanity.com/paper/2401.16788/) (2024)
- [GraphReason: Enhancing Reasoning Capabilities of Large Language Models through A Graph-Based Verification Approach](https://mlsanity.com/paper/2308.09267/) (2023)
- [Self-Evaluation of Large Language Model based on Glass-box Features](https://mlsanity.com/paper/2403.04222/) (2024)
- [Human-AI Collaboration Increases Skill Tagging Speed but Degrades Accuracy](https://mlsanity.com/paper/2403.02259/) (2024)

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

- [Three tiers of computation in transformers and in brain architectures](https://mlsanity.com/paper/2503.04848/) (2025)
- [Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks](https://mlsanity.com/paper/2601.13392/) (2026)

## Abstract (arXiv)

We present TuringQ, the first benchmark designed to evaluate the reasoning capabilities of large language models (LLMs) in the theory of computation. TuringQ consists of 4,006 undergraduate and graduate-level question-answer pairs, categorized into four difficulty levels and covering seven core theoretical areas. We evaluate several open-source LLMs, as well as GPT-4, using Chain of Thought prompting and expert human assessment. Additionally, we propose an automated LLM-based evaluation system that demonstrates competitive accuracy when compared to human evaluation. Fine-tuning a Llama3-8B model on TuringQ shows measurable improvements in reasoning ability and out-of-domain tasks such as algebra. TuringQ serves as both a benchmark and a resource for enhancing LLM performance in complex computational reasoning tasks. Our analysis offers insights into LLM capabilities and advances in AI comprehension of theoretical computer science.