Does the set of computable numbers get bigger if we strengthen our language?

Question

This might be a silly question, but can one given an example for a number, which is not computable?

I want to get a mental picture of what these real numbers are, which you can't write down. At the end of this Wikipedia article en.wikipedia.org/wiki/Computable_number it says

To actually develop analysis over computable numbers, some care must be taken. For example, if one uses the classical definition of a sequence, the set of computable numbers is not closed under the basic operation of taking the supremum of a bounded sequence (for example, consider a Specker sequence). This difficulty is addressed by considering only sequences which have a computable modulus of convergence. The resulting mathematical theory is called computable analysis.

So does this say that one has identified something uncomputable here? But if this is so, doesn't a description of such a thing give us a way of compute it or the object it represents?

If we step by step forever strengthen our language, do we somehow obtain more numbers out of the set or $\mathbb R\setminus\mathrm{computable numbers}$? Or is it that we can say "once we've got a process of this and that computing power, we can compute certain numbers and never more."?

Answer 1

Any real number is the limit of a strictly increasing sequence of rational (as those are dense) in the reals.

Now when the sequence $\{q_n\}_{n \in \omega}$ itself is computable (there is a program which take $n$ as input and output $q_n$), the limit is still not necessarily computable.

We call those numbers "left-computable". All the left-computable numbers can be computed assuming we have the "halting problem" as an oracle. Actually when we remove the requirement of being strictly increasing for $\{q_n\}_{n \in \omega}$ , the limit numbers of such sequences are exactly the numbers one can compute using the halting problem as an oracle.

Equivalently they are the numbers which are $\Delta^0_2$, meaning that for $X$ such a number, there is two computable functions $f$ and $g$ such that

the predicate "|X - q| < p" for $q$ and $p$ rationals is equivalent to $\forall n\ \exists m\ f(n, m, q, p)\ \downarrow$, but also equivalent to $\exists n\ \forall m\ g(n, m, q, p) \ \uparrow$.

So yes the limit of the "Specker sequence" is an example of left-computable but not computable number.

I am not sure I understand your last question.

Answer 2

A non-computable (real) number can be obtained from any undecidability result, for example from the Halting Problem. As an example, there is a polynomial $P(y,x_1,\dots,x_n)$, with integer coefficients, such that there is no algorithm that will determine, given a non-negative integer $y$ as input, whether or not there are non-negative integers $x_1,\dots,x_n$ such that $P(y,x_1,\dots,x_n)=0$. The real number with decimal expansion $0.a_0a_1a_2\dots$ where $a_i=5$ if $P(a_i,x_1,\dots,x_n)=0$ has a solution in non-negative integers, and $a_i=6$ if it doesn't, is not computable. Modification of language will not alter that.

Answer 3

I think you're somewhat conflating definable and computable numbers. Having an "accurate description" of a number means it is definable, but not necessarily computable - the supremum of a Specker sequence and Chaitin's constant(s) are examples of definable but non-computable numbers.

The question of "strengthening our language" has some relevance to definability - see Wikipedia's brief discussion on definability vs unambiguous description.

In terms of computability things are pretty clearly cut - either there's an algorithm that will compute the number to arbitrary precision or there isn't. Changing your encoding of the algorithm is irrelevant.