TuringQ: Benchmarking AI Comprehension in Theory of Computation
<|reference_start|>TuringQ: Benchmarking AI Comprehension in Theory of Computation: 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.<|reference_end|>
@article{zahraei2024turingq:,
    title={TuringQ: Benchmarking AI Comprehension in Theory of Computation},
    author={Pardis Sadat Zahraei and Ehsaneddin Asgari},
    journal={arXiv preprint arXiv:2410.06547},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.06547},
    primaryClass={cs.CL cs.FL}
}