3
$\begingroup$

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 ?

  • 1
    Are you looking for [complexity theory](http://en.wikipedia.org/wiki/Computational_complexity_theory)?2012-02-13
  • 0
    You're in luck! We had [a question about this](http://math.stackexchange.com/q/107636/856) just a few days ago.2012-02-13
  • 0
    @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?2012-02-13
  • 0
    @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. http://en.wikipedia.org/wiki/Turing_degree But all computable numbers are equivalent in this setting, none is strictly "more computable" than another.2012-02-13
  • 0
    @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).2012-02-13
  • 0
    @CarlMummert Perhaps you could write something up as an answer? I'd be interested in reading it.2012-02-13
  • 0
    @PeterTaylor Apologies if my tone was a bit condescending - always hard to judge someone's level of knowledge. Also, I'm not sure why there are so many *emphasized words* in my comment.2012-02-13

2 Answers 2

3

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

3

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.

ADDENDUM

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.

  • 0
    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$.2012-02-13
  • 0
    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.2012-02-13
  • 0
    !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.2012-02-13
  • 0
    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 ?2012-02-13
  • 0
    Of course ;) But concerning the algorithm you proposed above, you wrote "There are rationals p$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... – 2012-02-13
  • 0
    That's an excellent point; I only proved the case where the function changes sign at an isolated root, which was my mistake. But the general result from computable analysis is that any isolated root of a computable continuous function $\mathbb{R}\to\mathbb{R}$ is computable. Each polynomial with computable coefficients gives a computable function and every root of a polynomial is isolated. See e.g. p. 5 of http://www.cs.sunysb.edu/~keriko/survey3.ps or Corollary 6.3.9 of Weihrauch *Computable Analysis*. There is no uniformity claimed here, just that each root is individually computable.2012-02-13
  • 0
    (Please ignore my now-deleted comment.) For the $x^2 + e$ example, if $e > 0$ there is no root, if $e = 0$ there is one computable root, and if $e < 0$ there are two roots, $\pm \sqrt{e}$, each of which is computable from $e$.2012-02-13
  • 0
    You've defined $\epsilon$ as a small computable real number, and you claim that we can't determine whether $\epsilon \ge 0$ or not. That contradicts the definition of "computable" you give earlier in the answer. (BTW intuitively I would have thought that the method of Sturm sequences would allow computing arbitrarily tight bounds on the real roots of a polynomial with computable coefficients).2012-02-13
  • 0
    @Peter Taylor: there is no uniform effective way, given a computable number as input (e.g. given as a Cauchy sequence that converges to the real with a fixed modulus of convergence), to determine whether the number is negative. The proof is by a sort of diagonalization: given a particular algorithm, consider a Cauchy sequence that just gives $0$ until the algorithm has committed one way or the other, and then the Cauchy sequence goes the opposite way. A more technical explanation is that "$x < 0$" is a $\Sigma^0_1$ property of a real $x$ given as above, but not a $\Delta^0_1$ property.2012-02-14
  • 0
    !Lierre: I upvoted your answer, the clarification makes sense to me. The issue I was raising is only that each root could be computable even if there was no computable function from polynomials to their maximal roots.2012-02-14