Coins, Quantum Measurements, and Turing's Barrier
| dc.creator | Calude, Cristian S. | |
| dc.creator | Pavlov, Boris | |
| dc.date | 2001-12-15 | |
| dc.date | 2002-03-01 | |
| dc.date.accessioned | 2026-07-07T06:03:22Z | |
| dc.date.available | 2026-07-07T06:03:22Z | |
| dc.description | Is there any hope for quantum computing to challenge the Turing barrier, i.e. to solve an undecidable problem, to compute an uncomputable function? According to Feynman's '82 argument, the answer is {\it negative}. This paper re-opens the case: we will discuss solutions to a few simple problems which suggest that {\it quantum computing is {\it theoretically} capable of computing uncomputable functions}. In this paper a mathematical quantum "device" (with sensitivity $ε$) is constructed to solve the Halting Problem. The "device" works on a randomly chosen test-vector for $T$ units of time. If the "device" produces a click, then the program halts. If it does not produce a click, then either the program does not halt or the test-vector has been chosen from an {\it undistinguishable set of vectors} ${\IF}_{ε, T}$. The last case is not dangerous as our main result proves: {\it the Wiener measure of} ${\IF}_{ε, T}$ {\it constructively tends to zero when} $T$ {\it tends to infinity}. The "device", working in time $T$, appropriately computed, will determine with a pre-established precision whether an arbitrary program halts or not. {\it Building the "halting machine" is mathematically possible.} | |
| dc.description | 23 pages to appear in "Quantum Information Processing" | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0112087 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0112087 | |
| dc.identifier | Quantum Information Processing, 1, 1--2 (2002), 107--127 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/89911 | |
| dc.subject | Quantum Physics | |
| dc.title | Coins, Quantum Measurements, and Turing's Barrier | |
| dc.type | text |