An Experiment on the Simulation of Deterministic Turing Machines by Large Language Models

• Guilherme Lima PUC-Rio
• Cleyton Slaviero UFMT
• Edward H. Haeusler PUC-Rio

DOI: https://doi.org/10.5753/eniac.2026.30248

Resumo

Recent studies have shown that the use of chain-of-thought (CoT) under suitable assumptions enables large language models (LLMs) and transformers in general to achieve Turing completeness. In this paper, we put this claim to the test. We evaluate empirically the feasibility of using state-of-art LLMs with zero-shot CoT prompting to simulate arbitrary deterministic Turing machines. We tested four flagship models (DeepSeek V4 Pro, Gemini 2.5 Pro, GPT 5.4 and 5.2) over 116 randomly generated Turing machines with varying configurations. As expected, accuracy drops as the number of transitions of the simulated machine grows, but some models/modes of operation perform notably better than others, which corroborates the results of a related benchmark.

Referências

Hua, Z., Zhang, W., Lyu, C., Gu, Y., Gao, S., Liu, K., Lin, D., and Chen, K. (2026). The imitation game: Turing machine imitator is length generalizable reasoner. In Proc. ICLR 2026.

Jiang, H., Hahn, M., Zetzsche, G., and Lin, A. W. (2026). Softmax transformers are Turing-complete. In Proc. ICLR 2026.

Li, Z., Liu, H., Zhou, D., and Ma, T. (2024). Chain of thought empowers transformers to solve inherently serial problems. In Proc. ICLR 2024.

Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C. (2023). Transformers learn shortcuts to automata. In Proc. ICLR 2023.

Malfa, E. L., Weinhuber, C., Torre, O., Lin, F., Marro, S., Cohn, A., Shadbolt, N., and Wooldridge, M. (2024). Code simulation challenges for large language models. [link].

Merrill, W. and Sabharwal, A. (2024). The expressive power of transformers with chain of thought. In Proc. ICLR 2024.

Papadimitriou, C. H. (1994). Computational Complexity. Addison-Wesley, USA. Post, E. L. (1943). Formal reductions of the general combinatorial decision problem. Am.

J. Math., 65(2):197–215. Pérez, J., Barceló, P., and Marinkovic, J. (2021). Attention is Turing complete. J. Mach.

Learn. Res., 22(1). Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc., 2(42):230–265.

Wang, P.-Y., Liu, T.-S., Wang, C., Li, Z., Wang, Y., Yan, S., Jia, C., Liu, X.-H., Chen, X., Xu, J., and Yu, Y. (2026). A survey on large language models for mathematical reasoning. ACM Comput. Surv., 58(8).

Wu, H., Han, Z., Zhou, J. T., Huang, H., and Zhang, C. (2025). Computational reasoning of large language models. [link].

Zhou, H., Bradley, A., Littwin, E., Razin, N., Saremi, O., Susskind, J. M., Bengio, S., and Nakkiran, P. (2024). What algorithms can transformers learn? A study in length generalization. In Proc. ICLR 2024.