From: scerir (scerir@libero.it)
Date: Wed Dec 20 2000 - 12:26:24 MST
>> Chaitin shows that some of the deepest
>> foundations (of mathematics) are based on
>> truths which are purely random.
>
> Random, pseudorandom, where is the difference?
Of course the pseudorandom number generator is
completely determistic, so its "random" sequences
are not really random. Given the same initial state,
the algorithm will generate the same irregular
sequence.
Some sequences of bits can be compressed
into programs much shorter than they are,
because they follow a pattern or rule.
For example, a 100-bit sequence of the
form 0101010101... can be greatly compressed
by describing it as "50 repetitions of 01".
Such sequences certainly are not random.
A 100-bit sequence generated by tossing a coin,
on the other hand, cannot be compressed, since
in general there is no pattern to the succession
of 0's and 1's: it is a completely random sequence.
Of all the possible sequences of bits, most are
incompressible and therefore random. Since a sequence
of bits can be considered to be a representation of
any real number (for infinite sequences), it follows
that most real numbers are in fact random.
So, an algorithmically random number exhibits
the usual statistical properties of randomness.
(Penrose's) Hypothesis that dynamics should be
noncomputable simply means that no Turing machine
could reproduce this dynamics in the output of
a calculation.
In this regard I find Chaitin's theory much more
interesting. Chaitin's numbers are the halting
probability for a Turing machine, given certain
initial conditions.
These numbers are noncomputable,
algorithmically random, real, statistically
indistinguishable from a random series.
-scerir
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 15:32:29 MST