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]:

$$\sum_{n=1}^\infty \frac{\epsilon}{2^n} = \epsilon$$

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:

$$x_i \sim \text{Ber}\big(\frac{1}{2}\big)$$

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.