Example of uncomputable but definable number

Here is a non-computable real number: $$\sum_{i=1}^\infty 2^{-\Sigma(i)}$$ where $\Sigma$ is any busy beaver function.


The point here is that definable real numbers are definable using the entire strength of might of the set theoretic universe; whereas computable real numbers are only allowed to access the natural numbers and their very very very rudimentary properties (since computable functions are only $\Sigma_1$ definable functions over $\Bbb N$).

Let $\varphi_n$ enumerate the sentences in the language of arithmetic. Now consider the real number whose $n$-th digit in the decimal expansion is $1$ if and only if $\Bbb N\models\varphi_n$, and $0$ otherwise. So it is a number in $[0,1]$.

This number is of course definable in the language of set theory, since the set of true sentences in $\Bbb N$ is definable; but it is not a computable real number since there is no computable function telling us what is true in $\Bbb N$ and what isn't (not even arithmetical, to be more accurate).


We can also take the following approach, as I suggest in the comments to the original question.

Note that every computable real lies in $L$, by absoluteness arguments (every computable functions lies there), and in $L$ there is a definable well-ordering of the reals (even with a $\Delta^1_3$ definition!), so there is a least real in the canonical well-ordering which is not definable.

Since the set "the real numbers which also lie in $L$" cannot change between models of $\sf ZF$ with the same ordinals, this set always has a canonical, definable well-ordering in any model of $\sf ZF$, and this indeed gives us a definition of a real number which is non-computable.


You can also argue that various generic reals are non-computable but definable, if you're willing to go this far as to consider different set theoretic universes (or at least one which can be seen as a nontrivial generic extension of some inner model).

For example Jensen reals are definable (they are the unique solution to a $\Pi^1_2$ predicate) but not computable.

Similarly, you can consider the iterated forcing that at the $n$-th step does the lottery sum between forcing $2^{\aleph_n}=\aleph_{n+1}$ and forcing $2^{\aleph_n}=\aleph_{n+2}$, at the limit step take a finite support limit, and consider the real number whose $n$-th decimal digit $1$ if and only if $2^{\aleph_n}=\aleph_{n+1}$, and $0$ otherwise.

This is a Cohen real which is definable, since it encodes the continuum below $\aleph_\omega$; but of course it is not computable by genericity arguments.

Note that this gives a very peculiar example of a real number, the one encoding the continuum function below $\aleph_\omega$. It is always definable, but in different models of $\sf ZFC$ it wil have different values, sometimes they will be computable (e.g. if $\sf GCH$ holds) and sometimes they could be non-computable (as above).

So this gives us a definition of a real number which is not provably computable and not provably uncomputable!


The probability that a random computer program will run forever is not computable. http://en.wikipedia.org/wiki/Chaitin%27s_constant

That some aspects of our concepts in this area are problematic is illustrated by the following example, which I learned from Hartley Rogers' book on computability: let $$ f(x) = \begin{cases} 1 & \text{if there is a sequence of }x\text{ consecutive 7s in the decimal expansion of }\pi, \\ 0 & \text{otherwise}. \end{cases} $$ This is computable! And there is an easy argument for its computability. And the algorithm for computing this function is really really simple. One can prove that easily, but no one knows, nor is it at all easy to know, which algorithm it is.


The Chaitin's constant is a well defined number in computability theory, but it is not computable. But, about the concept of definable number see the answers to Definable real numbers.