dorsal/arxiv
View SchemaComputing the Noncomputable
| Authors | Tien D. Kieu |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0203034 |
| URL | https://arxiv.org/abs/quant-ph/0203034 |
| DOI | 10.1080/00107510302712 |
| Journal | Contemporary Physics 44 (2003) 51- 71 |
Abstract
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 the Hilbert's tenth problem, which is equivalent to the Turing halting problem and known to be mathematically noncomputable. Generalised quantum algorithms are also considered for some other mathematical noncomputables in the same and of different noncomputability classes. The key element of all these algorithms is the measurability of both the values of physical observables and of 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.
{
"annotation_id": "aa60701c-0e15-43d5-80f2-ecb246428290",
"date_created": "2026-03-02T18:01:48.484000Z",
"date_modified": "2026-03-02T18:01:48.484000Z",
"file_hash": "3310558943076fcd1e1bbaccbca5eb47749703f04b21c16f68bb39305e7bab1e",
"private": false,
"record": {
"abstract": "We explore in the framework of Quantum Computation the notion of\ncomputability, which holds a central position in Mathematics and Theoretical\nComputer Science. A quantum algorithm that exploits the quantum adiabatic\nprocesses is considered for the Hilbert\u0027s tenth problem, which is equivalent to\nthe Turing halting problem and known to be mathematically noncomputable.\nGeneralised quantum algorithms are also considered for some other mathematical\nnoncomputables in the same and of different noncomputability classes. The key\nelement of all these algorithms is the measurability of both the values of\nphysical observables and of the quantum-mechanical probability distributions\nfor these values. It is argued that computability, and thus the limits of\nMathematics, ought to be determined not solely by Mathematics itself but also\nby physical principles.",
"arxiv_id": "quant-ph/0203034",
"authors": [
"Tien D. Kieu"
],
"categories": [
"quant-ph",
"cs.LO",
"math.LO"
],
"doi": "10.1080/00107510302712",
"journal_ref": "Contemporary Physics 44 (2003) 51- 71",
"title": "Computing the Noncomputable",
"url": "https://arxiv.org/abs/quant-ph/0203034"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "300e1ee8-e7a2-4b1a-96e7-c5f52bc7c72a",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}