Abundance all around: Substrate, object, undecidable, inexhaustible

Jochen Szangolies, Gödel’s Proof and Einstein’s Dice: Undecidability in Mathematics and Physics – Part II, 3 Quarks Daily, March 6, 2023.

ONE:

Thus, undecidability seems to emerge whenever a theory’s substrate—the axioms of number theory, Turing’s A- and O-Machines—becomes the theory’s own object. The analogy to physics is immediate. Many theories are such that they apply to a limited set of phenomena. Maxwell’s theory of electromagnetism describes phenomena concerning the behavior of charges in electric and magnetic fields—a comprehensive, but clearly delineated subset of the (physical) universe. These can be studied ‘from the outside’: the theory has a limited scope.

TWO

The connection is made by means of the results of Argentine-American mathematician Gregory Chaitin, one of the main architects of the field of algorithmic information theory. The central object of this theory is the eponymous algorithmic information—also known as Kolmogorov complexity, after Russian mathematician and founder of modern-day probability theory Andrey Kolmogorov. Loosely speaking, the amount of algorithmic information contained in an object is the shortest possible description needed for a computer to reproduce it. So, for something highly regular, like a sequence containing only the number 1 ten billion times, a short description (like ‘the number 1 ten billion times’) is sufficient, while a sequence with ten billion random digits will typically have to be written out in full—signaling a much higher algorithmic information content.

This already hints at an important result: random sequences have maximal algorithmic information content. In fact, this is so fundamental as to be a useful definition of randomness: a sequence is (algorithmically) random if it cannot be compressed—if we can find no significantly shortened description causing a computer to reproduce the sequence.

Moreover, it establishes a direct line from mathematical undecidability to randomness. Indeed, for infinite random sequences, it turns out that only the values of finitely many digits can be decided—thus making each further digit an undecidable proposition! Translated into the physical realm, this finally yields the principle of finiteness.

Returning to the arc traced by TWA 702 between New York and London, at any given instant, only a finite amount of information is available to describe its state—its precise location and speed must thus be subject to an irreducible uncertainty, and its future course ever so slightly indeterminate. If sufficiently amplified, this uncertainty then might make questions about its future state—whether it is rocked by a patch of turbulence, say—just as undecidable as the state of the cat in the box.

THREE:

Likewise, the limitations placed upon our theories by results of a Gödelian nature provide an ‘epistemic horizon’, a horizon of our knowledge, regarding any physical system. This horizon is captured in the principle of finiteness above: there is a boundary to the information available regarding any physical system. That the system is not exhausted by this knowledge yields the principle of inexhaustibility.