Lesson 3

Let \(x \in \mathbb{R}\). Consider the problem \(\mathcal{P}_{x}\): given a number \(n \in \mathbb{Z}_{>0}\), output the number \(x\) with precision up to \(n\) decimal places. For example, a program for the problem \(\mathcal{P}_{\pi}\) with input \(n=6\) should output \(3{,}141592\), and a program for the problem \(\mathcal{P}_{\sqrt 2}\) with input \(n=4\) should output \(1{,}4142\). It is clear that there exists \(x \in \mathbb{R}\) for which \(\mathcal{P}_{x}\) is undecidable: simply because there are more real numbers than integers, while the number of different programs is exactly the same as the number of integers. However, this does not particularly hinder us in practice: first, not all real numbers are of interest to compute with arbitrary precision, and second, we do not even specify a concrete number for which no program exists.

As we see, it does not matter much how exactly we intend to compute a real number (for example, in which programming language). If a program exists, it is a finite description of that number. And we already know that not all real numbers have finite descriptions.