4
$\begingroup$

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

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Why do you think that a TM which generated the first $n$ bits of $\sqrt{e}$ would need all (or any, for that matter) of the bits of $e$? What would be wrong with a program that first generated enough bits of $e$ and then invoked the usual routine to take the square root of that argument? $\endgroup$
    – Rick Decker
    Jun 10, 2014 at 19:30
  • $\begingroup$ @RickDecker hmm, i think i understand what you mean, but this would be approximate computation , no? As another example consider a periodic rational (like 1/3), this although it has infinite bits it can be compressed like this "print 0. and while(true) print 3" $\endgroup$
    – Nikos M.
    Jun 10, 2014 at 19:36
  • $\begingroup$ @RickDecker, another point is if a TM can assume the (expansion) of the number $e$ as known (and thus not requiring to be embedded in the program), then of course $\sqrt{e}$ is not alg. random. But is this so? $\endgroup$
    – Nikos M.
    Jun 10, 2014 at 19:40
  • 4
    $\begingroup$ I'd argue that writing $e$ as a summation is compressing it, and greatly so: it represents with finite information an infinite amount of information. The problem isn't so much compressing $e$ as it is decompressing it; you cannot, by its very nature, get a decompressed representation of $e$ in finite time. Any attempt to do so will be an approximation since we don't have enough time or enough tape to write all the digits down. $\endgroup$
    – Patrick87
    Jun 10, 2014 at 19:59
  • 1
    $\begingroup$ In answer to your second question, how would a TM "assume" the expansion of $e$? Perhaps by having a second (infinite) tape with the bits of $e$? Sorry, but that's not allowed in the standard definition of a TM. Your third question is similar: you can't use an "infinite power series" to generate all of $e$ or $\sqrt{e}$: all you can do with a TM is generate $n$ digits of the number, for $n$ arbitrarily large, but finite. $\endgroup$
    – Rick Decker
    Jun 11, 2014 at 0:09

3 Answers 3

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ yes i used a simpler definition (and providd the links), however even T.M.Cover in Elements of Information Theory in the chapter of Kolmogorov Compexity (available online), has an example of Kolmogorov Complexity for $\sqrt{e}$ specifically using conditionals (on the number of first n bits) similarly to the 1st comment by Rick Decker. But you miss one point which the comment by Patrick87 touched. The relation of randomness in algorithmic and probabilistic sense. But nice answer. $\endgroup$
    – Nikos M.
    Jun 10, 2014 at 21:01
4
$\begingroup$

Surprisingly, the Kolmogorov complexity of some arbitrary number is known to be uncomputable. So the general form of your question, is an arbitrary number algorithmically compressible is undecidable (i.e. the problem of computing the algorithmic complexity of a sequence). This can be proven by reduction to the Halting problem.

Problems that are known to be related to "computable analysis" (the theory of computable reals) (cf. K. Weihrauch, Computable Analysis - An Introduction) are the following:

  1. To effectively enumerate all digits of a real number, one needs an infinite time Turing machine
  2. Distinguishing two Turing machines that compute two reals is uncomputable (i.e. the machine equivalence problem is undecidable)

A consequence of 1 and 2 is that the equality operator on Turing machines is not defined (at least in terms of a Choice Axiom).

In terms of undecidability, we are typically referring to Omega-like numbers (cf. Chatin's constant for which C. Calude et al. surprisingly provided "a" computation - Exact approximations of omega numbers).

Now, $e$ and $\pi$ are computable reals. The Borwein-Bailey-Plouffe formula can even compute the $n$-th digit of $\pi$.

Computability, compressibility and decidability theories refer to metamathematics. Compressibility refers to the program description of a sequence.

So for your example, $e$ would be described by 9 symbols ($\sum$,$n$,$=$,$0$,$\infty$,$\ldots$). We are assuming that the program is defined on some Universal Turing Machine, in this case, say, a symbolic algebra system. So in this case, $9 + O(1)$ symbols since the Universal Turing Machine is considered to be $O(1)$.

The problem of enumerating all digits of $e$ is a problem distinct from the problem of representing $e$ algorithmically.

Furthermore, in computer science, we only have pseudo-randomness since any random number generator that is fully described by an algorithm is by definition pseudo-random (in contrast to a hardware random number generator).

Improve this answer
$\endgroup$
4
  • $\begingroup$ +1, nice, indeed KC is in general not-computable (although can be approximated by Shannon entropy to which is related), and it is related in some ways to notions of randmness and tests for randomality in pseudo-random generators (another test of how random a sequence is, is provided by the work of P. Diaconis et al. by studying arbitrary permutations of the sequence and their distribution using a gneralised convolution operator). Anyway i plan to post another question related specifically to algorithmic and probabilistic approaches to randomness $\endgroup$
    – Nikos M.
    Jun 11, 2014 at 18:27
  • $\begingroup$ Since you mention a formula for the nth digit of $\pi$ (which i will check out by the way). Let me give a converse example, given a decimal expansion of a number (which is $\pi$) can one infer that it is in fact $\pi$? $\endgroup$
    – Nikos M.
    Jun 11, 2014 at 18:30
  • $\begingroup$ Wolfram (of Mathematica fame) is (in-)famous for supporting a variety of cellular automata which although extremely simple to describe algorithmicaly, yet can produce completely un-predictable (random?) behaviour (not periodic) $\endgroup$
    – Nikos M.
    Jun 11, 2014 at 18:41
  • $\begingroup$ It's not at all surprising that the Kolmogorov complexity of anything is uncomputable. The definition of Kolmogorov complexity of $X$ is essentially, "The shortest program that outputs $X$". Since it's undecidable whether any given program even outputs $X$ (or anything at all!), why would you be surprised that it's undecidable whether any given program is the shortest program that outputs $X$? $\endgroup$
    – David Richerby
    Oct 24, 2014 at 21:28
1
$\begingroup$

Your statement

Also note the fact that for transcendental numbers, and irrational numbers in general, the frequency of digits is uniform

is wrong. Look at Liouville's number. It is a transcendental number, containing almost all zeros, with a sparse amount of ones added (the nth 1 is at the n! decimal position). The distribution of digits to this number is completely one sided containing only 2 different digits, and one with a dominating frequency.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I read that claim differently to you. The statement is quite true "in general". Just like how most real numbers are uncomputable (the computable numbers are countably infinite, but the real numbers are not), most real numbers are normal in the Borel sense. $\endgroup$
    – Pseudonym ♦
    Jun 11, 2014 at 23:57
  • $\begingroup$ Makes sense, I read it as since transcendentals are a subset of irrationals the "in general" merely broadened the scope of the fact. The problem with irrationals is that you cant make real generalizations about them due to their lack of real structure. I think that when you look at real numbers however the majority will not have even frequencies since that is a limiting parameter that the majority cannot possibly have. $\endgroup$
    – lPlant
    Jun 12, 2014 at 0:10
  • $\begingroup$ Of course the uniform digit distribution for irrationals holds for almost all, so this is the sense in which it is stated in the question. However (as stated) it can lead to misunderstanding if you are not familiar with this property of numbers. Still is this an answer or a comment? $\endgroup$
    – Nikos M.
    Jun 12, 2014 at 0:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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