Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:hep-th/9412048

Quantum recursion theory

Karl Svozil

Published Dec 6, 1994• 4 citations
arXivHTMLPDF

Abstract

Incompleteness and undecidability theorems have to be revised in view of quantum information and computation theory. qrt.tex 1 As has already been pointed out in Gödel’s centennial paper on the incompleteness af arithmetic [1], the classical undecidability theorems of formal logic [2] and the theory of computable functions [4, 5] are based on semantical pardoxes such as the liar [6] or Richard’s paradox. The method of diagonalization, which was first applied by Cantor for a proof of the undenumerability of real numbers [7], has been applied by Turing for a proof of the recursive undecidability of the halting problem [8]. The halting problem is the problem of whether or not an arbitrary algorithm terminates or produces a particular output and terminates. Assume that the halting problem is decidable. Turing [8] proved that this assumption yields a contradiction. To construct the contradiction, consider

Related papers

Remarks on the undecidability of the quantum halting problem

Daegene Song

The halting problem is a decision problem first posed and proved by Alan Turing in 1936. With the recent surge of interest in quantum computation, one is led to ask if the problem can also be considered for a quantum computer. It is reported that the halting problem may not be solved consistently in both the Schrodinger and Heisenberg pictures of quantum dynamics. The assumption of the existence of the quantum halting machine leads to a contradiction when a vector representing an observable is the system that is to be unitarily evolved in both pictures.

•Jan 22, 2007•1 citation

Undecidable Problems in Physics: From Computation to Quantum Fields — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: Undecidable problems extend from computation to quantum field theory and many-body physics, revealing fundamental limits on what can be known or computed about physical systems. | MATH: Halting problem: no Turing machine can decide if an arbitrary program halts (Turing 1936). Gödel incompleteness: any consistent formal system containing arithmetic has true but unprovable statements. Reducibility: problem A reduces to B if solving B solves A (A ≤ B). In QFT, spectral gap problem is undecidable (Cubitt, Perez-Garcia, Wolf 2015): no algorithm can determine if a quantum many-body system has a nonzero energy gap. | CONNECTION: Undecidability in physics often arises from encoding Turing machines into Hamiltonian lattice systems — this maps computational logic onto geometric lattice structures (e.g., 2D spin lattices with local interactions). The spectral gap problem's undecidability proof uses aperiodic tilings and translation-invariant Hamiltonians, linking to crystallographic symm Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Jul 25, 2026•0 citations

The Halting Problem's Reach: Undecidability in Quantum Verification — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: The halting problem establishes a fundamental limit on algorithmic knowledge — no finite procedure can decide whether an arbitrary program halts, a result foundational to computation and quantum-verification complexity (MIP\*=RE). | MATH: Undecidability via diagonalization; H(P,I) = {1 if P halts on I, 0 otherwise} is non-computable. Key corollary: MIP\*=RE implies the quantum commuting operator model (Tsirelson's problem) is undecidable — connecting operator algebras to computability. No new constants or ratios emerge; the structure is purely combinatorial/logical. | CONNECTION: The diagonalization argument mirrors the construction of irrational numbers (Cantor's slash) — a self-referential "gap" that resists closure. This is analogous to the golden ratio's non-repeating continued fraction [1;1,1,1,...] = φ, which also encodes an irreducible self-similarity. The halting problem's undecidability is a discrete analogue of incommensurability — a ratio (program vs. proof) that ca Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Oct 8, 2026•0 citations

GÖDEL’S INCOMPLETENESS THEOREM MAKES THE QUANTUM DOUBLE SLIT EXPERIMENT UNDECIDABLE

Susanna Tall, Arvi Hakanen

Kurt Gödel’s incompleteness theorem refers to incompleteness in the sense that there are always statements which can be formulated within a formal system, but which re-main unproved within the system. Gödel’s theorem was first connected with the theory of computability by Alan Turing. Until recently, the inconsistency that Gödel’s theo-rem tackle has not been directly shown to correspond to any physical phenomenon. A recent article showed how to apply Gödel’s theorem in the context of many-body quan-tum mechanical calculations. Even so, it is still not known whether it can be applied to the most primitive quantum physical phenomena. In the present study, we used Gödel’s incompleteness theorem in the case of the quantum double-slit experiment by applying a proof of Turing machine’s halting problem. In addition, we made an analogy between Gödel’s theorem (and Church - Turing theses of computability), and quantum compu-ting by extrapolating the term “computation” as low as to the single-quantum level.

•Mar 6, 2025•0 citations

On the Computational Power of Physical Systems, Undecidability, the Consistency of Phenomena, and the Practical Uses of Paradoxes

Karl Svozil

The classical methods used by recursion theory and formal logic to block paradoxes do not work in quantum information theory. Since quantum information can exist as a coherent superposition of the classical ``yes'' and ``no'' states, certain tasks which are not conceivable in the classical setting can be performed in the quantum setting. Classical logical inconsistencies do not arise, since there exist fixed point states of the diagonalization operator. In particular, closed timelike curves need not be eliminated in the quantum setting, since they would not lead to any paradoxical outcome controllability. Quantum information theory can also be subjected to the treatment of inconsistent information in databases and expert systems. It is suggested that any two pieces of contradicting information are stored and processed as coherent superposition. In order to be tractable, this strategy requires quantum computation.

arXiv:quant-ph/9502008•Annals of the New York Academy of Sciences•Apr 1, 1995•11 citations

Undecidability as a Structural Invariant from Computability to Quantum Physics — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: Undecidability is not a peripheral paradox but a structural invariant of formal systems, extending from classical computability (halting problem) into quantum many-body physics, where spectral gaps and ground-state properties become provably non-computable. | MATH: Halting problem: no Turing machine H exists s.t. H(P,I) halts iff P(I) halts — diagonalization proof yields contradiction via self-reference. Gödel: for any consistent, recursively axiomatizable system S containing arithmetic, ∃ sentence G with S⊬G and S⊬¬G. Quantum extension: the spectral gap problem (given a translation-invariant local Hamiltonian on a lattice, does the gap between ground and first excited state vanish in the thermodynamic limit?) is undecidable — reduction from the halting problem to 2D spin-lattice Hamiltonians (Cubitt, Perez-Garcia, Wolf, 2015). | CONNECTION: The undecidability proofs rely on encoding computation into lattice structures — the 2D square lattice (crystallographic symmetry p4m) se Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Oct 6, 2026•0 citations
Incompleteness and undecidability theorems have to be revised in view of quantum information and computation theory. qrt.tex 1 As has already been pointed out in Gödel’s centennial paper on the incompleteness af arithmetic [1], the classical undecidability theorems of formal logic [2] and the theory of computable functions [4, 5] are based on semantical pardoxes such as the liar [6] or Richard’s paradox. The method of diagonalization, which was first applied by Cantor for a proof of the undenumerability of real numbers [7], has been applied by Turing for a proof of the recursive undecidability of the halting problem [8]. The halting problem is the problem of whether or not an arbitrary algorithm terminates or produces a particular output and terminates. Assume that the halting problem is decidable. Turing [8] proved that this assumption yields a contradiction. To construct the contradiction, consider
The halting problem is a decision problem first posed and proved by Alan Turing in 1936. With the recent surge of interest in quantum computation, one is led to ask if the problem can also be considered for a quantum computer. It is reported that the halting problem may not be solved consistently in both the Schrodinger and Heisenberg pictures of quantum dynamics. The assumption of the existence of the quantum halting machine leads to a contradiction when a vector representing an observable is the system that is to be unitarily evolved in both pictures.
FINDING: Undecidable problems extend from computation to quantum field theory and many-body physics, revealing fundamental limits on what can be known or computed about physical systems. | MATH: Halting problem: no Turing machine can decide if an arbitrary program halts (Turing 1936). Gödel incompleteness: any consistent formal system containing arithmetic has true but unprovable statements. Reducibility: problem A reduces to B if solving B solves A (A ≤ B). In QFT, spectral gap problem is undecidable (Cubitt, Perez-Garcia, Wolf 2015): no algorithm can determine if a quantum many-body system has a nonzero energy gap. | CONNECTION: Undecidability in physics often arises from encoding Turing machines into Hamiltonian lattice systems — this maps computational logic onto geometric lattice structures (e.g., 2D spin lattices with local interactions). The spectral gap problem's undecidability proof uses aperiodic tilings and translation-invariant Hamiltonians, linking to crystallographic symm Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
FINDING: The halting problem establishes a fundamental limit on algorithmic knowledge — no finite procedure can decide whether an arbitrary program halts, a result foundational to computation and quantum-verification complexity (MIP\*=RE). | MATH: Undecidability via diagonalization; H(P,I) = {1 if P halts on I, 0 otherwise} is non-computable. Key corollary: MIP\*=RE implies the quantum commuting operator model (Tsirelson's problem) is undecidable — connecting operator algebras to computability. No new constants or ratios emerge; the structure is purely combinatorial/logical. | CONNECTION: The diagonalization argument mirrors the construction of irrational numbers (Cantor's slash) — a self-referential "gap" that resists closure. This is analogous to the golden ratio's non-repeating continued fraction [1;1,1,1,...] = φ, which also encodes an irreducible self-similarity. The halting problem's undecidability is a discrete analogue of incommensurability — a ratio (program vs. proof) that ca Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
Kurt Gödel’s incompleteness theorem refers to incompleteness in the sense that there are always statements which can be formulated within a formal system, but which re-main unproved within the system. Gödel’s theorem was first connected with the theory of computability by Alan Turing. Until recently, the inconsistency that Gödel’s theo-rem tackle has not been directly shown to correspond to any physical phenomenon. A recent article showed how to apply Gödel’s theorem in the context of many-body quan-tum mechanical calculations. Even so, it is still not known whether it can be applied to the most primitive quantum physical phenomena. In the present study, we used Gödel’s incompleteness theorem in the case of the quantum double-slit experiment by applying a proof of Turing machine’s halting problem. In addition, we made an analogy between Gödel’s theorem (and Church - Turing theses of computability), and quantum compu-ting by extrapolating the term “computation” as low as to the single-quantum level.
The classical methods used by recursion theory and formal logic to block paradoxes do not work in quantum information theory. Since quantum information can exist as a coherent superposition of the classical ``yes'' and ``no'' states, certain tasks which are not conceivable in the classical setting can be performed in the quantum setting. Classical logical inconsistencies do not arise, since there exist fixed point states of the diagonalization operator. In particular, closed timelike curves need not be eliminated in the quantum setting, since they would not lead to any paradoxical outcome controllability. Quantum information theory can also be subjected to the treatment of inconsistent information in databases and expert systems. It is suggested that any two pieces of contradicting information are stored and processed as coherent superposition. In order to be tractable, this strategy requires quantum computation.
FINDING: Undecidability is not a peripheral paradox but a structural invariant of formal systems, extending from classical computability (halting problem) into quantum many-body physics, where spectral gaps and ground-state properties become provably non-computable. | MATH: Halting problem: no Turing machine H exists s.t. H(P,I) halts iff P(I) halts — diagonalization proof yields contradiction via self-reference. Gödel: for any consistent, recursively axiomatizable system S containing arithmetic, ∃ sentence G with S⊬G and S⊬¬G. Quantum extension: the spectral gap problem (given a translation-invariant local Hamiltonian on a lattice, does the gap between ground and first excited state vanish in the thermodynamic limit?) is undecidable — reduction from the halting problem to 2D spin-lattice Hamiltonians (Cubitt, Perez-Garcia, Wolf, 2015). | CONNECTION: The undecidability proofs rely on encoding computation into lattice structures — the 2D square lattice (crystallographic symmetry p4m) se Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com