# Are some numbers more computable than others?

As I understand it (layman alert), the definition of computable numbers is binary: either a number is or is not computable.

Is it meaningful to imagine a function telling how computable (or accessible) a number is ? Maybe such a function could be related to number of steps that are needed to compute it.

If so, which number is the least accessible, though computable ?

-
Are you looking for complexity theory? – Peter Taylor Feb 13 '12 at 11:10
@PeterTaylor The study of computability (what it is possible to compute) is conceptually distinct from the study of computational complexity (how long it takes to compute something known to be computable), although maybe complexity theory could be a useful angle into how computable a number is. My first thought was that the question is similar to the question of how infinite a certain set is, e.g. $\mathbb{N}$ and $\mathbb{R}$ are both infinite, but $\mathbb{R}$ is more infinite... In the same way, are some numbers more incomputable than others? – Chris Taylor Feb 13 '12 at 11:28
@Chris Taylor: some numbers are definitely more incomputable than other numbers. We can measure incomputability by saying that $\alpha$ is "at least as incomputable as" $\beta$ if there is an algorithm that computes $\beta$ given $\alpha$ as an oracle. Thus any process which is able to produce $\alpha$, and which is closed under the application of total algorithms, is also able to produce $\beta$. This leads the the study of Turing degrees. en.wikipedia.org/wiki/Turing_degree But all computable numbers are equivalent in this setting, none is strictly "more computable" than another. – Carl Mummert Feb 13 '12 at 13:32
@ChrisTaylor, I took the question as looking for distinctions among computable numbers because of the way it was phrased, but I left a comment rather than an answer because I wasn't certain what the OP really had in mind. You may be right that he's really interested in distinctions among uncomputable numbers, but that's hard to square with the last paragraph. (BTW, FWIW I'm actually a compsci rather than a mathmo). – Peter Taylor Feb 13 '12 at 22:35

The notion you seem to want is Kolmogorov complexity, which informally speaking measures the size of the smallest program needed to compute an object.

-

There is also the useful notion of left-computability and right-computability. i A real number $x$ is left-computable if for any computable real $a$ you can answer YES within finite time to the question : is $x$ greater than $a$ ?

A real number $x$ is right-computable if $-x$ is left-computable.

A real number $x$ is computable if and only if it is left and right-computable.

A real number $x$ is left-computable if and only if an algorithm can give you a non-decreasing sequence of rational numbers which tends to $x$.

For example, given a polynomial with real computable coefficients. Then its largest root is not a computable function of the coefficients. However, it is right-computable.

Following the friendly controversy with Carl Mummert, I realized that I was unclear.

As an example, consider the polynomial $f(x)=(x+1)x^2-\epsilon$, with $\epsilon$ a small computable real number. The largest root of $f$ is near $\sqrt\epsilon$ if $\epsilon\geq 0$, and near $-1$ if not.

Given the information that $\epsilon=0$ or not, this root is computable. However, as a function of $\epsilon$, it is not. If it were, it would imply that we are able to decide if $\epsilon\geq 0$ or not. But we can't : if you make run the Turing machine which approximate $\epsilon$ and it gives you only zero, you will never be able to state after a finite number of steps that $\epsilon$ is positive, or negative, or null.

This problem is quite general, and in fact, the Grzegorczyk states that a computable function from real numbers to real numbers is continuous. And obviously the function of $\epsilon$ "largest root of f" is not.

However, this largest root is right-computable : the algorithm answer zero as long as it as not enough precision to disprove $\epsilon=0$, and then it is able chose the correct location. But if the algorithm answers zero, you can never be sure that there is indeed a root near zero.

Carl Mummert, please correct me if I'm wrong.

-
Every root of a polynomial $f(x)$ over $\mathbb{R}$ with computable coefficients is computable. For example, let $\alpha$ be a root. There are rationals $p < q$ such that $\alpha$ is the only root in the interval $[p,q]$ and $f(p)$ has opposite sign from $f(q)$. Then we can use trisection: at most one of $f(p+(q-p)/3)$ and $f(p+2(q-p)/3)$ is 0, and in finite time we can effectively (as a function of $p,q$) approximate both values of $f$ until we know for sure that one is nonzero, at which point we can narrow down the interval $[p,q]$. This gives an iterative method to approximate $\alpha$. – Carl Mummert Feb 13 '12 at 13:41
And how do you find $p$ and $q$, especially if $\alpha$ is a double root ? What if $f$ is always positive ? Such an algorithm is impossible because a calculable functions from calculable real numbers to calculable real numbers needs to be continuous ! (Grzegorczyk's theorem) Whereas it is evident that the function "largest real root" is not a continuous function of the coefficients. – Lierre Feb 13 '12 at 15:34
!Lierre: since they are just two rationals, the initial $p$ and $q$ can be hard-coded into the algorithm to compute the real. The claim is just that every root of every real polynomial with computable coefficients is computable. – Carl Mummert Feb 13 '12 at 16:48
I think your claim is false. Take $f(x)=x^2$. How could you have $f(p)f(q) < 0$ ? Do you agree with the Grzegorczyk's continuity theorem ? – Lierre Feb 13 '12 at 16:53
Of course ;) But concerning the algorithm you proposed above, you wrote "There are rationals p<q such that α is the only root in the interval [p,q] and f(p) has opposite sign from f(q)", this is clearly false, isn't it ? However, I agree that roots where the sign of f changes are computable. Here is a counter-example : $f(x) = x^2 + e$, with $e$ a computable real number. To decide if $f$ has a root, you have to decide if $e$ is greater of equal to zero, right ? But if $e=0$, you can't... – Lierre Feb 13 '12 at 17:15