Читать книгу Chance, Calculation and Life - Группа авторов - Страница 21

We already summarized some of the connections between quantum and algorithmic unpredictability. The issue is increasingly in the limelight since there is a high demand for “random generators” in computing. Computers generate “random numbers” produced by algorithms and computer manufacturers took a long time to realize that randomness produced by software is only pseudo-random, that is, the generated sequences are perfectly computable, with no apparent regularity.

This form of randomness mimics the human perception of randomness well, but its quality is rather low because computability destroys many symptoms of randomness, e.g. unpredictability¹⁵. One of the reasons is that pseudo-random generators “silently fail over time, introducing biases that corrupt randomness” (Anthes 2011, p. 15).

Although, today, no computer or software manufacturer claims that their products can generate truly random numbers, these mathematically unfounded claims have re-appeared for randomness produced with physical experiments. They appear in papers published in prestigious journals, like Deutsch’s famous paper (Deutsch 1985), which describes two quantum random generators (3.1) and (3.2) which produce “true randomness” or the Nature 2010 editorial (titled True Randomness Demonstrated (Pironio et al. 2010)). Companies market “true random bits” which are produced by a “True Random Number Generator Exploiting Quantum Physics” (ID Quantique) or a “True Random Number Generator” (MAGIQ). “True randomness” does not necessarily come from the quantum. For example, “RANDOM.ORG offers true random numbers to anyone on the Internet” (Random.Org) using atmospheric noise.

Evaluating the quality of quantum randomness can now be done in a more precise framework. In particular, we can answer the question: is a sequence produced by repeated outcomes of measurements of a value indefinite observable computable? The answer is negative, in a strong sense (Calude and Svozil 2008; Abbott et al. 2012):

THEOREM 1.6.– The sequence obtained by indefinitely repeating the measurement of a value indefinite observable, under the conditions of Theorem 1.1, produces a bi-immune sequence (a strong form of incomputable sequence for which any algorithm can compute only finitely many exact bits).

Incomputability appears maximally in two forms:

 – Individualized: no single bit can be predicted with certainty (Theorem 1.4), i.e. an algorithmic computation of a single bit, even if correct, cannot be formally certified;

 – asymptotic (Theorem 1.6): only finitely many bits can be correctly predicted via an algorithmic computation.

It is an open question whether a sequence (such as Theorem 1.6) is Martin-Löf random or Schnorr random (Calude 2002; Downey and Hirschfeldt 2010).