# Are there any examples of non-computable real numbers?

Is this true, that if we can describe any (real) number somehow, then it is computable?

For example, $\pi$ is computable although it is irrational, i.e. endless decimal fraction. It was just a luck, that there are some simple periodic formulas to calcualte $\pi$. If it wasn't than we were unable to calculate $\pi$ ans it was non-computable.

If so, that we can't provide any examples of non-computable numbers? Is that right?

The only thing that we can say is that these numbers are exist in many, but we can't point any of them. Right?

• I can't be more precise since I don't know :) I agree that probably there can be some desriptions of non-computable numbers -- this is what my question about -- please provide some for me to feel... – Dims Aug 8 '13 at 13:43
• Please do not use the "number-theory" tag on questions like this, which are not about number theory. – Carl Mummert Aug 8 '13 at 19:25
• Roll a ten sided die numbered 0-9 an infinite number of times. – Michael May 20 at 3:13

Chaitin's constant is an example (actually a family of examples) of a noncomputable number. It represents the probability that a randomly-generated program (in a certain model) will halt.

It can be calculated approximately, but there is (provably) no algorithm for calculating it with arbitrary precision.

• Yes. You can obviously change the probability with which a random program halts by changing the programming language or computational model you are working in. But each language has its own associated $\Omega$. – MJD Aug 8 '13 at 13:52
• An $\Omega$ number does represent something, but not (as the WIkipedia article also says) "the probability that a randomly generated program will halt", because (1) there is not any canonical probability measure on the set of programs, and (2) the non-canonical measure used to generate a particular $\Omega$ number may not be a probability measure. I realize I am being picky about this, but it is a common point of confusion in that area. – Carl Mummert Aug 8 '13 at 19:23
• @MJD: An $\Omega$ number, relative to a universal prefix-free function $U$, is exactly the measure of the set of infinite binary sequences $f \in 2^\omega$ such that there is a finite prefix of $\sigma$ of $f$ on which $U$ will halt. The measure is the usual fair-coin probability measure on $2^\omega$, which is fixed and independent of $U$. – Carl Mummert Aug 8 '13 at 20:31
• The key points: (1) The measure is on $2^\omega$, not on $2^{<\omega}$ or on "programs". (2) There is no useful probability measure on $2^{<\omega}$ or any countable discrete set. (3) It is not even clear what a "program" for a prefix-free universal function $U$ should be, since every string is a legal input for $U$. Is a "program" then an arbitrary string (in which case the set of programs is not prefix-free, and the infinite sum of $2^{-|p|}$ over all programs $p$ diverges) or is a "program" just an input on which $U$ halts (in which case the probability a "random program" halts is 1). – Carl Mummert Aug 8 '13 at 20:35
• The idea behind the Wikipedia article's claim is that one might try to "randomly generate" a program by repeatedly flipping a fair coin to generate a sequence $f \in 2^\omega$ and looking to see if any finite prefix of that $f$ is in the domain of a fixed universal prefix-free function $U$. But not all $f$ may have a prefix in the domain of $U$, in which case the claim that the process generates a "random program" breaks down, and makes one realize the more fundamental question of what a "program" for a universal prefix-free function is supposed to be, if that process is going to generate one. – Carl Mummert Aug 8 '13 at 20:41

I haven't thought this through, but it seems to me that if you let $BB$ be the Busy Beaver function, then $$\sum_{i=1}^\infty 2^{-BB(i)}=2^{-1}+2^{-6}+2^{-21}+2^{-107}+\ ... \ \approx 0.515625476837158203125000000000006$$ should be a noncomputable real number, since if you were able to compute it with sufficient precision you would be able to solve the halting problem.

• (+1) I like this answer because it explicitly provides a great many initial digits of an uncomputable real number and has a very simple easy-to-understand definition. The current state of knowledge about the max-shifts function is that $BB(5) \ge 47176870$, so the present example is actually 0.51562547683715820312500000000000616297582203915472977912941627176741932192527428924222476780414581298828125000..., where there are at least $\lfloor 47176870 \ log_{10}2\rfloor - 107 = 14201545$ zeros after the $...8125$ and before the next positive digit. – r.e.s. May 31 '14 at 13:52
• Every finite sequence of digits is the start of the decimal expansion of an uncountable family of non-computable numbers – MJD May 31 '14 at 18:50
• That's true, of course; but it's beside the point, which is that this particular uncomputable number (viz., $\sum_{i=1}^\infty 2^{-BB(i)}$) has these particular digits. – r.e.s. Jun 1 '14 at 4:29
• I recommend to specify you refer to the "shift" function, not Rado's Sigma. Even though it does not make a difference in practice, of course. – mafu Dec 17 '14 at 15:50
• While it's true that "sufficient" is a technical term and not necessarily incorrect, I believe "arbitrary" is more appropriate here. In order for a number to be computable, it needs to be able to be specified with arbitrary precision. "Sufficient" implies some threshold that you must cross. "Arbitrary" implies that that threshold is infinite. – Tim Feb 17 '17 at 18:40

Any language can be turned into a number, by setting the $i^{th}$ decimal to 1 if the $i^{th}$ word is in the language, and to 0 otherwise. So we can build for instance the number $H$, which describes the halting problem and is therefore uncomputable.

• Would this example be more or less equivalent to the busy beaver example given by MJD? – k_g Dec 18 '14 at 3:03
• Yes it is more or less the same idea up to encoding, which is basically the reason why we can exhibit uncomputable real numbers, because a real number can encode an undecidable language. – Denis Dec 18 '14 at 13:28
• Love this answer. – charles Jan 19 '15 at 14:07
• This is hilarious and yet at the same time useless to the reader. – Mark C Oct 20 '17 at 7:25