How Real is Incomputability in Physics?

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 law of the system can be coded into a computer program, then given the system’s initial conditions of the system, one can compute the system’s evolution. This scenario is tacitly taken for granted. But is this reasonable? The answer is negative, and a straightforward example is when the initial conditions or equations use irrational numbers, like Chaitin’s Omega Number: no program can deal with such numbers because of their “infinity”. Are there incomputable physical systems? This question has been theoretically studied in the last 30–40 years. This article presents a class of quantum protocols producing quantum random bits. Theoretically, we prove that every infinite sequence generated by these quantum protocols is strongly incomputable – no algorithm computing any bit of such a sequence can be proved correct. This theoretical result is not only more robust than the ones in the literature: experimental results support and complement it.