Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation
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