No one shall expel us from the paradise which Cantor has created for us.-Hilbert

The computable reals in \([0,1]\) are countable and therefore we may denote them by the set \(R = \{r_i\}_{i=1}^{\infty} \subset [0,1]\). We’ll note that we can cover \(r_1\) with \(\frac{\epsilon}{2} > 0\), \(r_2\) with \(\frac{\epsilon}{4} > 0\), and \(r_n\) with \(\frac{\epsilon}{2^n} > 0\) so the total length of the cover is [1]:

\begin{equation} \sum_{n=1}^\infty \frac{\epsilon}{2^n} = \epsilon \end{equation}

and since \(\epsilon\) may be made arbitrarily small, the computable reals in \([0,1]\) form a set of measure zero.

The non-computable reals, on the other hand, may be constructed using an infinite sequence of coin tosses. So if we represent the non-computable real number \(x = \{x_i\}_{i=1}^\infty\) in base-2 so \(x \in \{0,1\}^\infty\), we have:

\begin{equation} x_i \sim \text{Ber}\big(\frac{1}{2}\big) \end{equation}

Now, here’s what I find both fascinating and mysterious. There is a large class of computable numbers, the irrational algebraic numbers, which are believed to be absolutely normal without exception. This means that their base-2 expansion has statistical behaviour that is indistinguishable from a binary sequence generated by coin tosses and therefore they are not finite-state compressible.

This class of numbers, the irrational algebraic numbers \(\mathcal{A}\), is of great interest to AI researchers as it implies that given \(x \in \mathcal{A}\) no machine learning system designed using any technology may be used to reliably predict the Nth bit of \(x\) given the first \(N-1\) bits of \(x\). And yet an exact formula exists for computing the Nth bit of \(x\).

References

  1. R. Courant and H. Robbins (1941), What is Mathematics?, Oxford: Oxford University Press.

  2. Gregory Chaitin. ALGORITHMIC INFORMATION THEORY. Cambridge University Press. 1987.

  3. Godofredo Iommi. BESICOVITCH FORMULA. Thermodynamic formalism and applications. 2012.