Wikipedia's definition of a computable numbers

282 Views Asked by At

According to Wikipedia,

computable numbers are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm.

I'm somewhat confused here. I always thought that given some fixed number of decimal places $n$, one can compute any number up to at least that precision.

Do they mean that for computability of a given number ('described' in some way, just not necessarily by an algorithm, e.g. Chaitin's constant), there needs to be a fixed finite, terminating algorithm which works for any $n$?

But once we have chosen some $n$, we can still compute up to that precision, just not necessarily by the initially picked algorithm anymore?

1

There are 1 best solutions below

0
On

Yes, your understanding is correct. For a real number $x$ to be computable you need to have a fixed algorithm that, given $n$, outputs the $n$-th decimal digit of $x$. It is true that for every real $x$ and every $n$, there is an algorithm that outputs exactly the first $n$ decimal digits of $x$, but there are real numbers s.t. no single algorithm works for every $n$.

As an additional note, the description of the real number $x$ plays an important role here. The idea of "being able to produce the $n$-th decimal digit" is essentially formalized by saying that, for every $n$, you can produce a rational number $q$ s.t. $|x-q| \le 2^{-n}$. This is the so-called Cauchy representation of $x$. However, this is not the only way to represent a real. For example, you can identify $x$ with a monotonically increasing sequence of rational numbers $(q_n)_{n\in\mathbb{N}}$ s.t. $\sup_n q_n = x$. This is the so-called left-cut representation of $x$. The set of Cauchy-computable real numbers is strictly smaller than the set of left-computable real numbers.