Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910234183729152 |
|---|---|
| author | Halftermeyer, Pierre |
| author_facet | Halftermeyer, Pierre |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_18757 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation Halftermeyer, Pierre Computational Complexity Formal Languages and Automata Theory Logic in Computer Science Programming Languages 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. |
| title | Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation |
| topic | Computational Complexity Formal Languages and Automata Theory Logic in Computer Science Programming Languages |
| url | https://arxiv.org/abs/2605.18757 |