Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation
For graph database users and language designers, this establishes the theoretical expressive power of Cypher, resolving a long-standing open question.
The paper proves that Cypher 25 is Turing-complete by simulating a 2-counter machine using a single RETURN statement with reduce(), CASE, and list comprehensions, and also via quantified path patterns. All constructions were verified on Neo4j Aura.
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.