# Are some real numbers “uncomputable”?

Is there an algorithm to calculate any real number. I mean given $a \in \mathbb{R}$ is there an algorithm to calculate $a$ at any degree of accuracy ?

I read somewhere (I cannot find the paper) that the answer is no, because $\mathbb{R}$ is not a recursive set since it's not a countable set.

But I'm missing something... can someone explain me in detail why so ?

Moreover it means that there exist real number that are uncomputable, and that you cannot neither write down nor express... it's like they don't exist.

-
Your problem starts with "Given $a\in R$. There, how do you give $a$? You cannot give most real numbers explicitly. That's the whole point. –  lhf Aug 17 '11 at 12:41
Thanks a lot for all your answers, it raises very interesting concepts and notions. –  Ricky Bobby Aug 17 '11 at 20:33

As you have observed yourself, $\mathbb{R}$, the set of real numbers, is uncountable, but every recursively enumerable set is necessarily countable. This immediately implies that there exist uncomputable real numbers. The same argument shows that there are (formally) indescribable real numbers. Indeed, almost all real numbers are indescribable, and a fortiori, uncomputable. There is nothing wrong about this, though it may be disturbing.

Do uncomputable/indescribable real numbers ‘exist’? Well, that's a philosophical question. A Platonist might say that they exist, even though we have no means of naming them specifically. A finitist might say they don't exist, precisely because we have no algorithm to compute or even recognise such a number.

Does this impact the way we do mathematics? Not really. So what if the vast majority of real numbers are uncomputable? By and large we deal with generic real numbers, not specific ones. For example, the fact that every non-zero real number $x$ has an inverse does not rely on the computability properties of $x$.

-
Could you please be more explicit about what "formally indescribable" means? As I'm sure you know, there are issues formalizing (set-theoretically) the notion of definability, so I wonder what notion you intend. Of course this doesn't affect the conclusion that there are real numbers which aren't computable. –  user83827 Aug 17 '11 at 13:48
I was trying to avoid having to be precise—by ‘there are formally indescribable real numbers’, of course what I mean is that for any fixed formal language over a finite alphabet, under any fixed interpretation, there are real numbers which are not the interpretation of an expression in that language—by the same counting argument. –  Zhen Lin Aug 17 '11 at 14:09
Thanks for clarifying; it is a bit of a pet peeve of mine when people understate the delicacy of reasoning about definability. I've noticed a tendency to make false conclusions like "there exists a real number which does not uniquely satisfy a formula of set theory" which mix up external and internal countability. If, as you've done, you ensure everything lives in a single universe I'm sure you avoid problems (and I understand the desire to leave things a bit imprecise -- it was the word "formal" that threw me). Sorry if I'm being nitpicky! –  user83827 Aug 17 '11 at 14:25
Ah, but that's a perfectly good reason to nitpick. If I'm to be honest, I wasn't thinking at that level at all! But now that you bring it up, I feel what I said is still imprecise, because it does not emphasise that the language must be internal to the universe. Otherwise, as you imply, if it's the external language, we could well exhaust all the internal real numbers! (This, I suppose, connects to the philosophical question of whether these ‘indescribable’ real numbers actually ‘exist’.) –  Zhen Lin Aug 17 '11 at 14:37
Well, such nitpickery is only useful if it increases understanding rather than leading away from the core issue (as I fear this is, but I was too blinded by my pet peeve to hold back). Anyway, if you haven't yet read it, there's a quite comprehensive answer on MO by JDH to which Qiaochu linked last time I was being fussy about this very issue: mathoverflow.net/questions/44102/… –  user83827 Aug 17 '11 at 15:12

Most real numbers are not computable. Informally speaking, a real number is computable if there is a machine or algorithm that computes its decimal expansion, one digit at a time, that is, you can ask for the $n$-th digit. Once you formalize machines and algorithms, which are finite animals, you see that there are only a countable number of them and so there are only a countable number of computable real numbers. Since the real numbers are not countable, most real numbers are not computable.

-

I think you are talking of computable numbers. You can read more about it on Wikipedia. Unfortunately, what I know regarding this is only a very little subset of what Wikipedia has. A relatively famous example for a non-computable number is the Chaitin's constant.

-

Yes, you may calculate $a$ up to an arbitrarily small error. But if you want to find the exact description, you will be able to do this only for a countable set of numbers. For instance, every description of a number contains a finite set of words, and thus the set of all such descriptions is countable. Since the set of all real numbers is not countable, many real numbers cannot be described, we only know that they exist.

-
Even if you want arbitrarily close approximations, there are still only countably many that are computable. –  Michael Hardy Aug 17 '11 at 12:26
Perhaps frog just meant you can pick a rational close by. –  Carl Mummert Aug 17 '11 at 12:28
@Carl, even so, it's not possible because you cannot decide nearby algorithmically for most real numbers. –  lhf Aug 17 '11 at 12:39
I meant the trivial fact that, say, you may find a natural $n$ and a rational $q$ such that the given number is in a $1/n$-neighbourhood of $q$. –  frog Aug 17 '11 at 12:45
@lhf: frog did not say the calculation was uniform. –  Carl Mummert Aug 17 '11 at 13:34

Precisely, a real number $x$ is computable if there is a total computable function $\varphi_{e}$ such that $|x-q_{\varphi_{e}(n)}|<2^{-n}$, where $\langle q_i \rangle_{i \in \omega}$ is an effective numbering of the rationals. So $\varphi_{e}$ picks out a computably-fast converging sequence of rationals whose limit is $x$. Note that one can then compute the decimal expansion of $x$ to any desired precision (and know when that precision has been reached).

Since each $\varphi_{e}$ corresponds to at most one computable real and there are only countably many such $\varphi_{e}$'s, there can be at most countably many computable reals. Of course, each rational is computable, so there are a countable infinity of computable reals.

Regarding your comment: "...it's like they don't exists". Here you have to understand what it means for something to exist in mathematics or—even better—in first-order logic. The point is that once you know the set of computable numbers is countable, Cantor's diagonal argument can be carried out in ZFC to show that there is no surjection from the computable numbers onto all the reals; i.e. noncomputable numbers must "exist".

-