TuringQ: Benchmarking AI Comprehension in Theory of Computation
On the map: LLM reasoning → Mathematical reasoning
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.
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.
Builds on
17 of 27 references.
Closest ancestors · 1
Same direction, newest first
Other references · 16
- 2020Language Models are Few-Shot Learnerscited by 32,419
- 2024The Llama 3 Herd of Modelscited by 14,715
- 2021LoRA: Low-Rank Adaptation of Large Language Modelscited by 14,380
- 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 13,028
- 2023Judging LLM-as-a-Judge with MT-Bench and Chatbot Arenacited by 8,626
- 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,371
- 2023QLoRA: Efficient Finetuning of Quantized LLMscited by 3,418
- 2022Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language modelscited by 1,998
- 2023Evaluating Large Language Models: A Comprehensive Surveycited by 202
- 2024Who Validates the Validators? Aligning LLM-Assisted Evaluation of LLM Outputs with Human Preferencescited by 144
- 2023Domain Specialization as the Key to Make Large Language Models Disruptive: A Comprehensive Surveycited by 135
- 2024Calibrating the Confidence of Large Language Models by Eliciting Fidelitycited by 47
4 more
- 2024Can Large Language Models be Trusted for Evaluation? Scalable Meta-Evaluation of LLMs as Evaluators via Agent Debatecited by 41
- 2023GraphReason: Enhancing Reasoning Capabilities of Large Language Models through A Graph-Based Verification Approachcited by 21
- 2024Self-Evaluation of Large Language Model based on Glass-box Featurescited by 5
- 2024Human-AI Collaboration Increases Skill Tagging Speed but Degrades Accuracycited by 4
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.
Similar, not cited
Close in wording, no citation either way
- 2024CLR-Bench: Evaluating Large Language Models in College-level Reasoning
- 2025Human-Level Reasoning: A Comparative Study of Large Language Models on Logical and Abstract Reasoning
- 2025Evaluating Mathematical Reasoning Across Large Language Models: A Fine-Grained Approach
- 2024Assessing the Emergent Symbolic Reasoning Abilities of Llama Large Language Models
- 2025Computational Reasoning of Large Language Models
- 2024CLR-Fact: Evaluating the Complex Logical Reasoning Capability of Large Language Models over Factual Knowledge
- 2023Have LLMs Advanced Enough? A Challenging Problem Solving Benchmark For Large Language Models
- 2026The IOL-AI Challenge: An Open Challenge towards Advancing Linguistic Reasoning