Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer
    
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. –  NikolajK Sep 8 '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 8 '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...$. –  NikolajK Sep 8 '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 8 '13 at 15:15

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.

share|improve this answer
    
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." –  NikolajK Sep 6 '13 at 19:22

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.