# Uncomputable Numbers and Rational Approximations

• B
• Pikkugnome
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...

Pikkugnome said:
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.
Pikkugnome said:
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.
Pikkugnome said:
However all real numbers have rational approximations
Yes.
Pikkugnome said:
. 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.
Pikkugnome said:
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?
Pikkugnome said:
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.

Halc
Pikkugnome said:
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.

Pikkugnome said:
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.

Pikkugnome said:
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?

Pikkugnome said:
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.

Pikkugnome said:
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.

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

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

FactChecker

Replies
6
Views
1K
Replies
35
Views
4K
Replies
3
Views
1K
Replies
4
Views
1K
Replies
85
Views
5K
Replies
1
Views
1K
Replies
4
Views
1K
Replies
13
Views
5K
Replies
8
Views
4K
Replies
29
Views
5K