Uncomputable Numbers and Rational Approximations

[Pikkugnome]

TL;DR Summary

How does an uncomputable number and its rational approximation go together?

Digits of an uncomputable number, as I understand, can't be produced. However all real numbers have rational approximations. Does it mean that there exists a bound for the rational approximation. It is odd to talk about rational approximations in a non-contructive sense, but I am ok with it. I guess the most uncomputable number would the one, which none of its digts can be calculated. That is strange, since then we can't even find its lower and upper bounds, as then we would know one of its digits. I am guessing this is true, it seems obvious. On the otherhand, if the bounds themselves are uncomputable numbers...

 

[FactChecker]

TL;DR Summary: How does an uncomputable number and its rational approximation go together?

An uncomputable number has infinitely many rational approximations, depending on how close you want the approximations to be.

Digits of an uncomputable number, as I understand, can't be produced.

It's more accurate to say that the exact number can not be produced, not that any particular digit or finite set of digits can not be produced.

However all real numbers have rational approximations

Yes.

. Does it mean that there exists a bound for the rational approximation.

A bound in what sense? You can always produce a rational approximation within any desired accuracy.

It is odd to talk about rational approximations in a non-contructive sense, but I am ok with it. I guess the most uncomputable number would the one, which none of its digts can be calculated.

Is there such a thing? Do you have an example in mind?

That is strange, since then we can't even find its lower and upper bounds, as then we would know one of its digits. I am guessing this is true, it seems obvious. On the otherhand, if the bounds themselves are uncomputable numbers...

I think you are letting your imagination get out of hand here.

 

[fresh_42]

TL;DR Summary: How does an uncomputable number and its rational approximation go together?

Digits of an uncomputable number, as I understand, can't be produced.

That depends on what you mean by uncomputable. E.g. the digits of $\sqrt{2}$ can be computed, just not all of them, or not within a finite time. I assume you mean the absence of an algorithm that comes to a hold. But that leaves the question, of whether you consider $1/3$ as uncomputable.

However all real numbers have rational approximations. Does it mean that there exists a bound for the rational approximation.

Usually, yes. It depends on how the real number is described. We have good knowledge about $p,q,n$ in $\left|\sqrt{2}-\frac{p}{q}\right|< \frac{1}{n}$ or $\left|\pi-\frac{p}{q}\right|< \frac{1}{n}.$ I could imagine that there were real numbers that weren't defined by an algebraic rule like $x^2-2=0$ or $\pi=4\tan^{-1}(1)$ or any other constructive way. But I can hardly imagine that we can define such a real number in a way so that we both mean the same number without any form of construction rule. The definition itself is limited to a language, and a language obeys rules. The question of which of them are decidable, recursive countable, context-free, etc. leads us directly into the theory of formal languages.

It is odd to talk about rational approximations in a non-contructive sense, but I am ok with it.

I think this would be close to impossible. What does it mean, a real number that cannot be constructed?

I guess the most uncomputable number would the one, which none of its digts can be calculated.

Yes, but how would you define such a number so that we can at least speak about it and both mean the same number?

There is a finite natural number $G_{64},$ Graham's number, we don't know all digits from. We know the last 500 or so, we know the construction, but we cannot write it down since it is too big. This number is formally computable, but factually uncomputable. The difference to a particular rational number is zero.

That is strange, since then we can't even find its lower and upper bounds, as then we would know one of its digits. I am guessing this is true, it seems obvious. On the otherhand, if the bounds themselves are uncomputable numbers...

No, it is not. A real number is per definition the limit of a rational Cauchy sequence. This alone is a construction principle and a possibility to define lower and upper bounds of approximations to any given degree of accuracy.

It is only strange if a) you do not define uncomputable, b) you do not define what a real number is, c) you ignore the Cauchy sequence, d) you do not even name the formal language class we can use to describe a real number. Digits are not an appropriate way to deal with such questions.

 

[Petek]

This is way out of my comfort zone, but perhaps this Wikipedia article on Chaitin's constant is relevant.

 

[BWV]

FWIW the Leading digits of some large rational numbers, such as Graham’s number cannot be computed (but the ending digits can), but this is a computational limit not a mathematical one