7
$\begingroup$

This question arises from a comment I recently read in another question.

My question is whether we can represent every real number using only finite memory. I will clarify what I mean by represent using only finite memory by use of examples:

  • $5$ can be represented in finite memory simply by itself as a one-character string.
  • Similarly for $1.234583$, which can also be represented by a string of finite length.
  • $\pi$ can also be adequately represented in finite memory: it is the ratio of any circle's circumference to its diameter.
  • $e$ we can represent as $\displaystyle\lim_{n \rightarrow \infty} \left(1+\frac1n\right)^n$
  • $0.818181\ldots$ can be represented as $0.\overline{81}$ or $\frac{9}{11}$.
  • $0.010011000111\ldots$ can be represented as the sum of some sequence $a_n$ as $n\rightarrow \infty$.

For all the examples above, an adequate representation of the given real is possible using only finite memory, because we can describe/define exactly the given real using a string of finite length.

So do any reals that cannot be described/represented in finite memory exist? For which their only closed-form expression requires a string of infinite length? (Infinitely many digits?)

Relevant Reading Material Includes:

Is it possible to represent every huge number in abbreviated form?

Every Number is Describable?

$\endgroup$
6
  • $\begingroup$ I found it difficult to tag this question appropriately. Please feel free to re-tag. $\endgroup$
    – Newb
    Dec 25, 2013 at 1:01
  • 1
    $\begingroup$ I don't understand the question $\endgroup$
    – Ethan Splaver
    Dec 25, 2013 at 1:11
  • $\begingroup$ A real number that can be expressed can be defined as that expression. We can say that if a number is not possible to express (in a finite length description) then it is unreachable. Do you mean to store also unreachable numbers? Any number that can be calculated can be measured by the code that calculates it. That string of code needs to be finite for the number to be practically calculable anyway. $\endgroup$
    – mathreadler
    Apr 16, 2016 at 12:25
  • $\begingroup$ There is this concept in information theory "shortest program length" for a computer program to calculate something. I have forgotten it's name right now. We could maybe say that the size of the number is the shortest possible program able to calculate it. $\endgroup$
    – mathreadler
    Apr 16, 2016 at 12:28
  • $\begingroup$ @mathreadler are you talking about Kolmogorov Complexity? $\endgroup$
    – Newb
    Apr 17, 2016 at 1:23

3 Answers 3

Reset to default
12
$\begingroup$

There are in fact indefinable real numbers. If you have a language with a countable number of symbols, then any formula $P(x)$ defining a real number will have, at best, a countable number of symbols. By a Cantor-style diagonal argument, you can only define a countable number of reals.

To elaborate: working in standard first-order logic with a given set theory, you can call $r$, a real number, to be definable if there is a formula $P(x)$ such that $r$ is the only real number such that $P(r)$ is true. However, note that the collection of formulas with one free variable is countable, whereas the collection of reals is uncountable; hence there are uncountably many undefinable real numbers.

For more information, see this wiki page; Timothy Gowers also has a good expository article that may be of interest.

(So the answer is no, you can't represent every real number in finite memory, so to speak, if you assume that every description can be represented as a formula in first order logic.)

$\endgroup$
1
  • $\begingroup$ The question of whether there are indefinable reals was necessarily impllied. Superb. Thanks! I think this answers my question, but I'll not 'accept' your answer yet --- I want to leave the discussion open for the moment, to see what other people might have to say. $\endgroup$
    – Newb
    Dec 25, 2013 at 6:19
3
$\begingroup$

So do any reals that cannot be described/represented in finite memory exist? For which their only closed-form expression requires infinitely many digits?

Yes, the fact that transcendentals are uncountable implies that there is no finite or even countably infinite way to represent them all. ( Assuming memory is discrete and therefor countable).

Further more, there are numbers that can not be computed, so how does one stores an uncomputable number? ( like the Chaitin's $\Omega$ constant)

$\endgroup$
2
  • 1
    $\begingroup$ The fact that a given number is uncomputable does not mean that we cannot represent it in finite memory. I am not familiar with Chaitin's $\Omega$ constant, but it appears that we can describe $\Omega_F = \sum\limits_{p \in P_F} 2^{-|p|}$. So we can represent it with a string of finite length --- we don't have to compute it for it to be representable. $\endgroup$
    – Newb
    Dec 25, 2013 at 1:20
  • 2
    $\begingroup$ Descriptions of real numbers are countably infinite. Every real in $[0, 1)$ is describable as a countably infinite sequence of binary digits. Every real in $(-\infty, \infty)$ is describable as a real from $[0, 1)$ plus a finitely-describable integer. You need to replace "no finite or even countably infinite way" with "no finite way". $\endgroup$
    – MJD
    Dec 25, 2013 at 3:07
1
$\begingroup$

With $b$ bits of information, you can represent at most $2^b$ numbers. So that excludes any infinite set $(\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\cdots$).

You might be tempted to say that this can be worked around by changing the encoding at will, i.e. the interpretation rule of the expression, after you have exhausted all expressions. But this doesn't work, as you will need more bits to specify which encoding rule holds.

There is no escape, $b$ bits represent at most $2^b$ numbers.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .