Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
    
I found it difficult to tag this question appropriately. Please feel free to re-tag. – Newb Dec 25 '13 at 1:01
    
I don't understand the question – Ethan Dec 25 '13 at 1:11
    
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. – mathreadler Apr 16 at 12:25
    
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. – mathreadler Apr 16 at 12:28
    
@mathreadler are you talking about Kolmogorov Complexity? – Newb Apr 17 at 1:23
up vote 9 down vote accepted

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.)

share|cite|improve this answer
    
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. – Newb Dec 25 '13 at 6:19

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)

share|cite|improve this answer
1  
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. – Newb Dec 25 '13 at 1:20
1  
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". – MJD Dec 25 '13 at 3:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.