6

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."?

Nikolaj-K
  • 12,249

3 Answers3

5

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.

Anthony Carapetis
  • 35,361
  • Okay yeah the second linked article also clears the quote-part of the question. It says "...however, if the sequence itself is definable in the sense that we can specify a single formula for all its terms, then its limit will necessarily be a definable number." – Nikolaj-K Sep 06 '13 at 19:22
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.

André Nicolas
  • 507,029
2

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.

Archimondain
  • 918
  • Thanks for the reply. The first sentence speaks exactly of the Dedekind cuts, right? Also, if a number is left-computable, and the oracle says the algorithm doesn't halt, in what sense then does the oracle enable us to compute it? Lastly, it appreas to me that if I have an algorithm of which I know it's a left-computable number, then I should somehow be able to identify that algorithm with the number it would compute. – Nikolaj-K Sep 08 '13 at 11:35
  • Yes I guess the first sentence is related to the Dedekind cut. I am not sure to understand what you then ask. An algorithm 'is not' a number. It can compute a sequence converging to a left computable number which is not computable. The idea is that even if you know that your algorithm approach your non computable-number more and more, you never know how far from it the approximation is. – Archimondain Sep 08 '13 at 13:05
  • What I want to say is this: We can state rational numbers easily by writing down two integers. And we can write down non-rational numbers like $\mathrm{e}$ via representing them by some string like "$\sum_{k=0}^\infty \frac{1}{k!}$". Now nobody can know then completed infinite string which lies behind $\mathrm{e}$, but we can still use $\mathrm{e}$ in calculation. Now if going on, if we have the program which does compute a sequence of numbers (e.g. converging against the number which we call non-computable), then why not identify this program with that number, just like we do with $\sum...$. – Nikolaj-K Sep 08 '13 at 14:17
  • Sure, you can identify the program computing the converging sequence with the limit of the sequence, but that does not not make the limit computable. However, you can consider left-computable number as 'almost computable' I guess. – Archimondain Sep 08 '13 at 15:15