On 12/29/2013 11:42 PM, Bruno Marchal wrote:
On 29 Dec 2013, at 20:25, meekerdb wrote:
On 12/29/2013 5:56 AM, Bruno Marchal wrote:
On 28 Dec 2013, at 22:23, meekerdb wrote:
On 12/28/2013 4:09 AM, Bruno Marchal wrote:
For a long time I got opponent saying that we cannot generate computationally a
random number, and that is right, if we want generate only that numbers. but a
simple counting algorithm generating all numbers, 0, 1, 2, .... 6999500235148668,
... generates all random finite incompressible strings,
How can a finite string be incompressible? 6999500235148668 in base 6999500235148669
is just 10.
You can define a finite string as incompressible when the shorter combinators to
generate it is as lengthy as the string itself.
This definition is not universal for a finite amount of short sequences which indeed
will depend of the language used (here combinators).
Then you can show that such a definition can be made universal by adding some
constant, which will depend of the universal language.
It can be shown that most (finite!) numbers, written in any base, are random in that
sense.
Of course, 10 is a sort of compression of any string X in some base, but if you allow
change of base, you will need to send the base with the number in the message. If you
fix the base, then indeed 10 will be a compression of that particular number base, for
that language, and it is part of incompressibility theory that no definition exist
working for all (small) numbers.
Since all finite numbers are small, I think this means the theory only holds in
the limit.
The definition will work for all numbers reasonably bigger than the code of the
universal machine used. That is what determine the constant. Not all numbers are small
relatively to the size of the universal number/machine used to compress information.
Maybe you can clarify this point which seemed to arise in my discussion with JR. Are you
talking about numbers or about strings of digits that name numbers?
Brent
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/groups/opt_out.
