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

A Mathematical Model of Quantum Computer by Both Arithmetic and Set Theory

Vasil Dinev Penchev

A practical viewpoint links reality, representation, and language to calculation by the concept of Turing (1936) machine being the mathematical model of our computers. After the Gödel incompleteness theorems (1931) or the insolvability of the so-called halting problem (Turing 1936; Church 1936) as to a classical machine of Turing, one of the simplest hypotheses is completeness to be suggested for two ones. That is consistent with the provability of completeness by means of two independent Peano arithmetics discussed in Section I.Many modifications of Turing machines cum quantum ones are researched in Section II for the Halting problem and completeness, and the model of two independent Turing machines seems to generalize them.Then, that pair can be postulated as the formal definition of reality therefore being complete unlike any of them standalone, remaining incomplete without its complementary counterpart. Representation is formal defined as a one-to-one mapping between the two Turing machines, and the set of all those mappings can be considered as “language” therefore including metaphors as mappings different than representation. Section III investigates that formal relation of “reality”, “representation”, and “language” modeled by (at least two) Turing machines.The independence of (two) Turing machines is interpreted by means of game theory and especially of the Nash equilibrium in Section IV.Choice and information as the quantity of choices are involved. That approach seems to be equivalent to that based on set theory and the concept of actual infinity in mathematics and allowing of practical implementations.

•Jan 1, 2020•2 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
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.
A practical viewpoint links reality, representation, and language to calculation by the concept of Turing (1936) machine being the mathematical model of our computers. After the Gödel incompleteness theorems (1931) or the insolvability of the so-called halting problem (Turing 1936; Church 1936) as to a classical machine of Turing, one of the simplest hypotheses is completeness to be suggested for two ones. That is consistent with the provability of completeness by means of two independent Peano arithmetics discussed in Section I.Many modifications of Turing machines cum quantum ones are researched in Section II for the Halting problem and completeness, and the model of two independent Turing machines seems to generalize them.Then, that pair can be postulated as the formal definition of reality therefore being complete unlike any of them standalone, remaining incomplete without its complementary counterpart. Representation is formal defined as a one-to-one mapping between the two Turing machines, and the set of all those mappings can be considered as “language” therefore including metaphors as mappings different than representation. Section III investigates that formal relation of “reality”, “representation”, and “language” modeled by (at least two) Turing machines.The independence of (two) Turing machines is interpreted by means of game theory and especially of the Nash equilibrium in Section IV.Choice and information as the quantity of choices are involved. That approach seems to be equivalent to that based on set theory and the concept of actual infinity in mathematics and allowing of practical implementations.
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.