On 30 Dec 2013, at 09:01, meekerdb wrote:
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?
I am talking about string of digits (naming or not numbers). Sometimes
I call them number, as all strings on a fixed alphabet can be seen as
a number written in the base defined by that alphabet. But compression
is a notion concerning strings of symbols.
Bruno
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 everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/groups/opt_out.
http://iridia.ulb.ac.be/~marchal/
--
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 everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/groups/opt_out.
