Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?)

share|improve this question
The third paragraph seems to indicate that you view the first paragraph as a definition. Then what's the meaning of the second paragraph? What does it mean to show why a definition is the case? –  joriki Mar 3 '13 at 7:58
@joriki removed definition. Oh well. my mistake. –  user64765 Mar 3 '13 at 8:00
OK, if it's not a definition, it would make sense to provide the definition of computable number that you're using, because it sure looks like one possible definition of that term. Have you looked at the definitions in the Wikipedia article? –  joriki Mar 3 '13 at 8:21
what does it mean "can compute"? Because I can compute 0 and than I can add $2^{-n}$ as many times as I need. So every real number would be computable. –  tom Mar 3 '13 at 8:34
How do you know when to stop? –  Zhen Lin Mar 3 '13 at 9:01

1 Answer 1

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.