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

I was wondering whether non-computable numbers are ever of "direct" use ? I understand they are immensely useful indirectly, because we need them to do analysis in the real numbers for instance. However what I mean by "direct" is some use, where one would for instance want to actually give some non-computable number a name ?

I don't really understand non-computable numbers well enough yet to make my question any clearer, but I think there are instances of mathematical objects that we don't construct directly, but we can show their existence, and may want to give names to specific instances (take sigma-algebras for instance right ?)

So in a similar way, even though we cannot directly get at a non-computable number, is it conceivable to show existence of a specific non-computable, and to actually want to use it in a specific context ?

share|cite|improve this question
It is useful to know that there is no general algorithm for a certain class of problems. One will not waste time trying to produce one! Apart from that, there may not be direct practical uses. – André Nicolas Feb 27 '12 at 23:11

Some examples of "direct use" exist in algorithmic randomness, especially where computable analysis is concerned. For example, classical analysis tells us that a function $f:[0,1]\to \mathbb{R}$ of bounded variation is differentiable almost everywhere, but doesn't say anything about the points of differentiability. However, if $f$ is also assumed computable, then it has been proven that every ML-random (a specific type of algorithmically randomness) real number (including Chaitin's $\Omega$) is a point of differentiability of $f$. Since all algorithmically random reals are incomputable, this gives more information (albeit with stronger hypotheses).

Results of this type abound in computable analysis/algorithmic randomness. Here is another example.

share|cite|improve this answer
I'd never heard of that differentiability result before! Very cool. – Steven Stadnicki Feb 28 '12 at 2:20

One example is Chaitin's constant, and for a bit more discussion you can see this similar question on MO.

share|cite|improve this answer
is Chaitin's constant actually of any direct use, or is it just constructed to exhibit an uncomputable number ? In the later case it's not really what I m after. – Beltrame Feb 27 '12 at 23:02
Chaitin's constant is not a single number, it is really a collection of similar numbers. To get a single number you have to make some non-canonical choice of which one you mean. – Carl Mummert Feb 28 '12 at 2:30

Yes, there are many non-computable real numbers that are important enough to have names. However, they are more naturally considered as sets of integers or infinite sequences of integers, rather than as points on the real number line. There are simply definable correspondences between integer sequences and real numbers, so in some contexts the "information content" is considered to be the same and some of us like to abuse notation by calling them all "reals."

Examples would be $0'$ (zero-jump), which is the halting problem, and $0^\sharp$ (zero-sharp), which is not only non-computable, but also non-constructible. Then there's $0^\dagger$ (zero-dagger) and zero-pistol (which I don't know how to write in $\TeX$.) Such objects are studied in recursion theory and set theory.

Notice that although we can identify these "numbers" with points on the real number line, the identification is not sufficiently canonical that it makes sense to ask, for example, whether $0^\sharp$ is greater than 37. What is important is the "information content," for example, $0'$ tells you whether a Turing machine halts, and $0^\sharp$ tells you what sentences are true in Goedel's constructible universe.

share|cite|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.