Example of uncomputable but definable number

Question

Every computable number is definable. However, the converse is not true. What is an example of a real number that is definable but that is NOT computable? I guess if it is there, we can "define" (describe) it, can't we?

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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!

Answer 5

If we consider an enumeration of all possible pairs of turing machines and inputs, then we can let $S$ denote the set of those positive integers $n$ for which the $n$th pair halts. Now this number $x$ will be well-defined but uncomputable:

$$x = \frac 1 3 + 4\sum_{n \in S} 10^{-n}$$

$x$ will consist of a sequence of decimals all of which are either 3 or 7. The $n$th decimal will be 7 if the $n$th pair of turing machine and input halts, and 3 otherwise. In other words computing a decimal of $x$ is equivalent to solving an instance of the halting problem.

What is also interesting about $x$ is that there is a simple constructive algorithm to produce a sequence of rational numbers, that converge towards $x$.

• Initialize $a := \frac 1 3$
• For $i \in \mathbb{N}$ do:
  • Simulate the first $i$ turing machines for the first $i$ steps.
  • For each turing machine $n$ which halted and did not halt for any lower $i$:
    • $a := a + 4 \cdot 10 ^{-n}$
    • Output $a$

This shows that it possible for a computable sequence of rational numbers to converge on a non-computable number. This is a bit more than what you asked for, but to me this particular example gave me a better feeling for what the boundary of compatibility looks like.

Answer 6

The simplest is perhaps the uncomputable real number whose binary expansion is $$0.x_1x_2x_3...$$ where $$x_i = \begin{cases} 1 & \text{if }T_i\text{ eventually halts}\\ 0 & \text{otherwise} \end{cases} $$ and $T_i$ is the $i$th Turing machine (in some chosen ordering) with an initially blank tape.