Take the 2-minute tour ×
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.

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|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
add comment

2 Answers

up vote 6 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|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
add comment

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|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
add comment

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.