Are there any examples of non-computable real numbers?

Question

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 to any of them. Right?

Answer 1

Chaitin's constant is an example (actually a family of examples) of a non-computable 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.

Answer 2

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.

Answer 3

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.

Answer 4

I usually consider the function $f(n)=1$ if the $n^{th}$ computer program halts with input $0$ and $f(n)=0$ otherwise. The real number $r=\sum_{n\in \mathbb{N}} f(n)\times 2^{-n}$ must be non-computable, otherwise you would be able to solve the halting problem.

Note: in order to accept this argument you must accept that there is a bijection between natural numbers and computer programs, which can be easily done by assigning values to the symbols used to write programs.

Answer 5

Examples of uncomputable numbers, like the one clearly presented by Luis Fonsera, seem to assume that the halting of any particular Turing machine can be determined (by some other Turing machine ?). Is this always true? It not then for some values of n, Fonsera's function f(n) might not be determined and so the uncomputable number r is undetermined. An example might be a Turing machine that searches for violations of the Goldbach conjecture. Another could be a Turing machine, T, that searches through ratios of two rational numbers to see if it can find one that is squareroot of 2. We know that this programme wil never halt but I am at a loss to see how a Turing machine could come to show this just by examining the programme of machine T. Are some mathematical truths like the irrationality of squareroot 2 uncomputable?

Answer 6

Most finite strings of digits have high Kolmogorov complexity (Li & Vitanyi, 1997). This means they can not be produced by a Turing machine much smaller than the length of the string itself. There is a counting argument for this, which (overly simplified) says that there are less strings with length n-1 than there are with length n. If this is also the case for infinite strings (which I assume, but don't remember) it follows that most real numbers are uncomputable.

Li, Ming; Vitányi, Paul (1997). An Introduction to Kolmogorov Complexity and Its Applications. Springer.