T uring Q : Benchmarking AI Comprehension in Theory of Computation (2024)

Abstract: 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.

## introduction the reasoning and comprehension capabilities of large language models (llms) are becoming increasingly critical due to their expanding applications across complex domains @xcite . as llms continue to evolve, robust benchmarks are essential for assessing their performance, particularly in areas that require deep understanding and logical reasoning @xcite . while multi-task benchmarks like big-bench @xcite cover a variety of domains, a notable gap remains, a dedicated dataset for evaluating llm performance on theoretical concepts and problems within the domain of the theory of computation. this gap is significant, as assessing comprehension in formal languages and abstract computational problems is crucial to evaluating the true depth of an llm's reasoning capabilities. addressing this need is a key step toward transforming llms into sophisticated problem solvers in highly complex domains @xcite . turingq fills this critical gap by providing a comprehensive platform for rigorously assessing and comparing the reasoning capabilities of different llms on intricate theoretical domains. it drives advancements in enhancing their skills for tackling computationally complex concepts, contributing to the development of more reliable and capable ai systems @xcite . mastery of theory of computation principles is particularly vital, as these foundational concepts underpin modern computing systems and algorithms. improving llm comprehension in this domain could unlock new potential for reasoning about computational problems, analyzing algorithms, and even contributing to the creation of novel computational models and methodologies. figure 1 presents a complete visual overview of our work. our contributions are threefold: ## the turingq dataset turingq is a comprehensive dataset comprising 4,006 question-answer pairs covering undergraduate and graduate-level theory of computation problems, aligned with sipser's framework @xcite . the questions are categorized into four difficulty levels and seven main conceptual areas: regular languages, theoretical concepts, context-free languages, computability theory, countability concepts, complexity theory, and fundamental concepts. details are provided in appendix ## experiments for further evaluation and analysis, we employ a diverse set of language models: llama-3-8b-instruct @xcite , llama-2-7b-chat-hf @xcite , mistral-7b-instruct @xcite , gpt-4-32k (openai, 2023), gemma-7b-it, and gemma-2b-it @xcite . to assess these models, we curated a stratified sample of 500 questions from the turingq dataset, maintaining the original distribution across difficulty levels and categories. this approach ensures a representative subset for our comparative analysis. ## conclusion we introduced turingq to evaluate the reasoning capabilities of large language models (llms) in the domain of computation theory, encompassing four difficulty levels and seven core concepts. our evaluation involved various open-source llms and gpt-4, utilizing chain of thought prompting and assessments from human experts. additionally, we developed an automated evaluation system using a large language model, demonstrating both its potential and limitations. fine-tuning a llama3-8b model on turingq significantly improved its grasp of computation theory, as well as its performance on out-of-domain tasks such as algebra. this work establishes a valuable benchmark for assessing llms' understanding of computational theory. evaluating comprehension of formal languages is essential for gauging the depth of llms' reasoning abilities, marking a significant advancement toward developing llms into effective problem solvers.