A real number being computable

184 Views Asked by At

In my text, it says that a real number $r \in \mathbb{R}$ is computable iff given $n$ one can compute $q \in \mathbb{Q}$ such that $\left|r-q\right| \leq 2^{-n}$.

Can anyone show why it is the case?

(Another version of this is $r = \lim_n q_n$ for a computable sequence $(q_n)_{n \in \mathbb{N}}$ of rationals such that $\left|r-q\right| \leq 2^{-n}$ for each $n$. If possible, can anyone also show how these two are equal?)

1

There are 1 best solutions below

0
On

As mentioned in the comments, your first question seems to be unanswerable without a definition of computable (for real numbers). So I will just show you why the two conditions you provided for $r \in \mathbb{R}$ being computable are equivalent.

Suppose that given $n$, one can compute $q \in \mathbb{Q}$ such that $|r-q| \leq 2^{-n}$. There is actually a slight subtlety here: it must also be assumed that this ability to compute $q$ is uniform in $n$; that is, there must be a single algorithm that given $n$, produces $q$. With this in mind, the equivalence of the definitions becomes clear. Since $q$ depends upon $n$ we should really call it $q_{n}$. And there you have it!: the sequence $(q_{n})_{n \in \mathbb{N}}$ is computable, $r = \lim q_{n}$ and $|r-q_{n}| \leq 2^{-n}$.

(The converse direction is (or at least, should be) even clearer. But let me know if it's not.)

You should convince yourself that the abovementioned uniformity really is necessary.