[Solved]: Can a transcendental number like $e$ or $\pi$ be compressed as not algorithmically random?

Problem Detail: 

The related and interesting fields of Information Theory, Turing Computability, Kolmogorov Complexity and Algorithmic Information Theory, give definitions of algorithmically random numbers.

An algorithmically random number is a number (in some encoding, usually binary) for which the shortest program (e.g using a Turing Machine) to generate the number, has the same length (number of bits) as the number itself.

In this sense numbers like $\sqrt{e}$ or $\pi$ are not random since well known (mathematical) relations exist which in effect function as algorithms for these numbers.

However, especially for $e$ and $\pi$ (which are transcendental numbers) it is known that they are defined by infinite power series.

For example $e = \sum_{n=0}^\infty \frac{1}{n!}$

So even though a number, which is the binary representation of $\sqrt{e}$, is not alg. random, a program would (still?) need the description of the (infinite) bits of the (transcendental) number $e$ itself.

Can transcendental numbers (really) be compressed?

Where is this argument wrong?

UPDATE:

Also note the fact that for almost all transcendental numbers, and irrational numbers in general, the frequency of digits is uniform (much like a random sequence). So its Shannon entropy should be equal to a random string, however the Kolmogorov Complexity, which is related to Shannon Entropy, would be different (as not alg. random)

Thank you

Asked By : Nikos M.

Answered By : Veedrac

The problem is in your poor definition of "algorithmically random number" as applied to irrational numbers. In particular:

has the same length (number of bits) as the number itself.

has no meaning if the number is of unbounded length.

Your Wikipedia link gives better definitions, which don't have this problem. For example (and paraphrasing formatting):

Kolmogorov complexity [...] can be thought of as a lower bound on the algorithmic compressibility of a finite sequence (of characters or binary digits). It assigns to each such sequence $w$ a natural number $K(w)$ that, intuitively, measures the minimum length of a computer program (written in some fixed programming language) that takes no input and will output $w$ when run. Given a natural number $c$ and a sequence $w$, we say that $w$ is $c$-incompressible if $K(w) \geq |w| - c$.

An infinite sequence $S$ is Martin-Löf random if and only if there is a constant $c$ such that all of $S$'s finite prefixes are $c$-incompressible.

This is a test passed by $\sqrt{e}$ by setting $c$ a bit larger than the program to generate $\sqrt{e}$ and including in it the length to generate.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/27578