How Real is Incomputability in Physics?
arXiv:2311.00908 · doi:10.1016/j.tcs.2024.114632
Abstract
A physical system is determined by a finite set of initial conditions and "laws" represented by equations. The system is computable if we can solve the equations in all instances using a "finite body of mathematical knowledge". In this case, if the laws of the system can be coded into a computer program, then given the initial conditions of the system, one can compute the system's evolution. Are there incomputable physical systems? This question has been theoretically studied in the last 30-40 years. In this paper, we experimentally show for the first time the strong incomputability of a quantum experiment, namely the outputs of a quantum random number generator. Moreover, the experimental results are robust and statistically significant.
20 pages, 3 figures, 2 tables, final submitted version
References in corpus (15)
- Charge insensitive qubit design derived from the Cooper pair box
- A Fast and Compact Quantum Random Number Generator
- Undecidability of the Spectral Gap (short version)
- Fast and Unconditional All-Microwave Reset of a Superconducting Qubit
- Strong Kochen-Specker theorem and incomputability of quantum randomness
- Quantum randomness and value indefiniteness
- Experimental Evidence of Quantum Randomness Incomputability
- Indeterminism in Physics and Intuitionistic Mathematics
- A variant of the Kochen-Specker theorem localising value indefiniteness
- Value-indefinite observables are almost everywhere
- Realization of a quantum random generator certified with the Kochen-Specker theorem
- Extracting random numbers from quantum tunnelling through a single diode
- Experimentally Probing the Algorithmic Randomness and Incomputability of Quantum Randomness
- Searching for evidence of algorithmic randomness and incomputability in the output of quantum random number generators
- A Non-Probabilistic Model of Relativised Predictability in Physics