# A paradox related to computable reals?

Let O be a computable ordering of all computable reals in ⟨0,1) (eg. first by length of programs computing them and then lexicographically). (it does not matter that they appear there more than one time).
It seems to be possible to produce a computable real not in this ordering by diagonal argument, using a deterministic algorithm to produce the non-matching digit.

What is the error in this reasoning?

-
Why doesn't it matter that they appear there more than one time? Say, real $r$ is computed by programs $P$ and $Q$ and $P<Q$ according the given order, and $s$ is computed by $S$ with $P<S<Q$. Then will be $r<s$ or $s<r$?? –  Berci Mar 24 '13 at 20:49
@Berci It only matters that all of them are represented there. –  kinokijuf Mar 24 '13 at 20:51
Why? Ah, maybe you automatically choose the smallest program (according to the given order)? –  Berci Mar 24 '13 at 20:53
@Berci I think you misunderstood the question. The ordering was there only for the diagonal argument to work, but now I see that it is uncomputable (see Chris Eagle’s answer below). –  kinokijuf Mar 24 '13 at 20:55

The error is that the computable ordering you want does not exist. You can easily order programs as you suggest, but since you can't computably determine which programs actually define real numbers, that doesn't help.

-
We could interpret everything our program produces as digits. –  kinokijuf Mar 24 '13 at 20:45
@kinokijuf: So what? –  Chris Eagle Mar 24 '13 at 20:51
Ah, now I see. The program could hang (go into an infinite loop) before even printing anything. –  kinokijuf Mar 24 '13 at 20:52
So it is known/proven that there is no computable ordering of the computable reals? –  usul Apr 1 '13 at 19:11
@usul Yes. This question is the proof. –  Zakharia Stanley May 10 '13 at 21:39