Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation

Read full text Summarise with VIRAT
Authors: Pierre Halftermeyer
Cited by: 0

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

We prove that Cypher 25, the graph query language of Neo4j, is Turing-complete. The proof shows that a single RETURN statement using reduce(), CASE expressions, and list comprehensions can simulate any 2-counter machine (Minsky 1967). We address the bounded-step objection via two complementary resolutions and present a third graph-native simulation using quantified path patterns (QPP) with allReduce. All three constructions were verified on a live Neo4j Aura instance.

Fields of Study & Subjects

Logic programming and type systems Computability AI Algorithms semigroups and automata theory

Publication details

Journal / source
arXiv (Cornell University)
Publication date
24 March 2026
Language
EN
Document type
Preprint