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:quant-ph/0111062

Hilbert's Incompleteness, Chaitin's ΩΩΩ number and Quantum Physics

Tien D. Kieu

Published Nov 10, 2001• 2 citations
arXivHTMLPDF

Abstract

To explore the limitation of a class of quantum algorithms originally proposed for the Hilbert's tenth problem, we consider two further classes of mathematically non-decidable problems, those of a modified version of the Hilbert's tenth problem and of the computation of the Chaitin's $Ω$ number, which is a representation of the Gödel's Incompletness theorem. Some interesting connection to Quantum Field Theory is pointed out.

DOI
10.48550/arxiv.quant-ph/0111062

Related papers

Quantum recursion theory

Karl Svozil

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

arXiv:hep-th/9412048•Dec 6, 1994•4 citations

Computing the non-computable

Tien D. Kieu

We explore in the framework of quantum computation the notion of computability, which holds a central position in mathematics and theoretical computer science. A quantum algorithm that exploits the quantum adiabatic processes is considered for Hilbert's tenth problem, which is equivalent to the Turing halting problem and known to be mathematically non-computable. Generalized quantum algorithms are also considered for some other mathematical non-computables in the same and in different non-computability classes. The key element of all these algorithms is the measurability of both the values of physical observables and the quantum-mechanical probability distributions for these values. It is argued that computability, and thus the limits of mathematics, ought to be determined not solely by mathematics itself but also by physical principles.

arXiv:quant-ph/0203034•Contemporary Physics•Jan 1, 2003•30 citations

Quantum algorithms for the Hilbert's tenth problem

Tien D. Kieu

A quantum algorithm is presented for the classically non-computable Hilbert's tenth problem, which ultimately links to the Turing halting problem.

•Oct 24, 2001•5 citations

Incompleteness theorem for physics

John M. Myers, F. Hadi Madjid

We show how Gödel's first incompleteness theorem has an analog in quantum theory. Gödel's theorem implies endless opportunities for appending axioms to arithmetic, implicitly showing a role for an agent, namely an agent that asserts an axiom. There is an analog of this theorem in physics, to do with the set of explanations of given evidence. We prove that the set of explanations of given evidence is uncountably infinite, thereby showing how contact between theory and experiment depends on activity beyond computation and measurement -- physical activity characterized as agency.

arXiv:1803.10589•Mar 27, 2018•3 citations

Quantum Measurement and Gödel's Proof

Martin Zwick

The measurement problem in quantum mechanics has the character of a fundamental incompleteness within that theory similar to the incompleteness of axiomatic systems in mathematics, discovered and elaborated by Gödel and others. The difficulty of describing the measurement process by the time-dependent Schrodinger equation may reflect the limitations of formal language , and quantum theory may thus require a formalism consisting of two levels of description, one for the dynamics and one for measurement, levels whose relationship resembles that of a calculus and meta-calculus.

Speculations in Science and Technology•Jan 1, 1978•11 citations

The quantum algorithm of Kieu does not solve the Hilbert's tenth problem

Boris S. Tsirelson

Recently T. Kieu (arXiv:quant-ph/0110136) claimed a quantum algorithm computing some functions beyond the Church-Turing class. He notes that "it is in fact widely believed that quantum computation cannot offer anything new about computability" and claims the opposite. However, his quantum algorithm does not work, which is the point of my short note. I still believe that quantum computation leads to new complexity but retains the old computability.

arXiv:quant-ph/0111009•Nov 1, 2001•12 citations
To explore the limitation of a class of quantum algorithms originally proposed for the Hilbert's tenth problem, we consider two further classes of mathematically non-decidable problems, those of a modified version of the Hilbert's tenth problem and of the computation of the Chaitin's ΩΩΩ number, which is a representation of the Gödel's Incompletness theorem. Some interesting connection to Quantum Field Theory is pointed out.
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
We explore in the framework of quantum computation the notion of computability, which holds a central position in mathematics and theoretical computer science. A quantum algorithm that exploits the quantum adiabatic processes is considered for Hilbert's tenth problem, which is equivalent to the Turing halting problem and known to be mathematically non-computable. Generalized quantum algorithms are also considered for some other mathematical non-computables in the same and in different non-computability classes. The key element of all these algorithms is the measurability of both the values of physical observables and the quantum-mechanical probability distributions for these values. It is argued that computability, and thus the limits of mathematics, ought to be determined not solely by mathematics itself but also by physical principles.
We show how Gödel's first incompleteness theorem has an analog in quantum theory. Gödel's theorem implies endless opportunities for appending axioms to arithmetic, implicitly showing a role for an agent, namely an agent that asserts an axiom. There is an analog of this theorem in physics, to do with the set of explanations of given evidence. We prove that the set of explanations of given evidence is uncountably infinite, thereby showing how contact between theory and experiment depends on activity beyond computation and measurement -- physical activity characterized as agency.
The measurement problem in quantum mechanics has the character of a fundamental incompleteness within that theory similar to the incompleteness of axiomatic systems in mathematics, discovered and elaborated by Gödel and others. The difficulty of describing the measurement process by the time-dependent Schrodinger equation may reflect the limitations of formal language , and quantum theory may thus require a formalism consisting of two levels of description, one for the dynamics and one for measurement, levels whose relationship resembles that of a calculus and meta-calculus.