Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer
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

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.