0

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?

user9007131
  • 1
  • 1
    For example, the number $1/3 = 0.3333333333333...$ is computable. Indeed, there exists a fixed algorithm, that outputs its $n$-th decimal place for any input $n$. The algorithm is simply "return 3" for all $n$, which is the algorithm for the number $1/3$. – Crostul Mar 04 '21 at 09:40
  • In fact the requirement is a fixed finite terminating algorithm that can (in principle) calculate ALL the digits. If the number is uncomputable we need ever more powerful algorithms to determine more and more digits , and it is not even guaranteed that we always have such a more powerful algorithm. – Peter Mar 04 '21 at 10:06
  • 3
    @Peter indeed, the crucial point is that one finite algorithm must work for all $n$. If, on the other hand, we were allowed to choose algorithms that become longer and longer with increasing $n$, then such an algorithm trivially exists for any number: "return [first $n$ digits of that number]" – hgmath Mar 04 '21 at 11:07
  • @hgmath Technically correct , But we cannot apply this algorithm until we know the digits. So, even in principle, the pure existence of this algorithm is utterly useless. – Peter Mar 04 '21 at 11:28
  • @Peter The first part of your first comment is what I had in mind. You further wrote that 'it is not even guaranteed that we always have such a more powerful algorithm.' Is there an example of a number which we know up to a certain precision, yet for which there provably exists no algorithm to calculate more digits? – user9007131 Mar 04 '21 at 11:44
  • I am not an expert in this topic. According to the german author Joerg Resag ("Die Grenzen der Berechenbarkeit" - german text available online) we cannot determine more than a fixed number of digits of Chaitin's conatant within a fixed theory , meaning that we cannot prove or disprove most bits to be $0$. But this does not rule out stronger theories where this might be possible. I don't know it, to be honest. – Peter Mar 04 '21 at 11:52
  • An interesting question would also be "Can we (in principle) decide for an arbitary given turing machine whether it halts" ? I doubt we can always prove that the machine does not halt. But I might be wrong. – Peter Mar 04 '21 at 11:55
  • @Peter there is no algorithm that can decide (in finite time) for any given TM whether it halts -- see here: https://en.wikipedia.org/wiki/Halting_problem – hgmath Mar 04 '21 at 12:00
  • @hgmath This is not my question. I mean : Does for every non-halting turing machine exist a specific proof that this machine does not halt ? – Peter Mar 04 '21 at 12:16

1 Answers1

3

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.

Manlio
  • 3,234