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 ?

  • 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
    !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