On 29 Dec 2013, at 23:42, meekerdb wrote:

## Advertising

On 12/29/2013 2:08 PM, Jason Resch wrote:On Sun, Dec 29, 2013 at 4:51 PM, meekerdb <meeke...@verizon.net>wrote:On 12/29/2013 1:28 PM, Jason Resch wrote:On Sun, Dec 29, 2013 at 2:25 PM, meekerdb <meeke...@verizon.net>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 generatecomputationally a random number, and that is right, if we wantgenerate only that numbers. but a simple counting algorithmgenerating all numbers, 0, 1, 2, .... 6999500235148668, ...generates all random finite incompressible strings,How can a finite string be incompressible? 6999500235148668 inbase 6999500235148669 is just 10.You can define a finite string as incompressible when the shortercombinators to generate it is as lengthy as the string itself.This definition is not universal for a finite amount of shortsequences which indeed will depend of the language used (herecombinators).Then you can show that such a definition can be made universal byadding 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 somebase, but if you allow change of base, you will need to send thebase with the number in the message. If you fix the base, thenindeed 10 will be a compression of that particular number base,for that language, and it is part of incompressibility theorythat no definition exist working for all (small) numbers.Since all finite numbers are small, I think this means the theoryonly holds in the limit.Brent Brent,It is easy to see with the pigeon hole principal. There are more2 digit numbers than 1 digit numbers, and more 3 digit numbersthan 2 digit numbers, and so on. For any string you can representusing a shorter string, another "shorter string" must necessarilybe displaced. You can't keep replacing things with shorterstrings because there aren't enough of them, so as a side-effect,every compression strategy must represent some strings by largerones. In fact, the average size of all possible compressedmessages (with some upper-bound length n) can never be smallerthan the average size of all uncompressed messages.The only reason compression algorithms are useful is because theyare tailored to represent some class of messages with shorterstrings, while making (the vast majority of) other messagesslightly larger.A good explanation. Thanks.But just because you cannot compress all numbers of a given sizedoesn't imply that any particular number is incompressible.That is true if you consider the size of the compression program tobe of no relevance. In such a case, you can of course have anumber of very small strings map directly to very large ones.So isn't it the case that every finite number string iscompressible in some algorithm? So there's no sense to saying6999500235148668 is random, but 11111111111111 is not, exceptrelative to some given compression algorithm.Right, but this leads to the concept of Kolmogorov complexity. Ifyou consider the size of the minimum string and algorithm together,necessary to represent some number, you will find there are somepatterns of data that are more compressible than others. In yourprevious example with base 6999500235148668, you would need toinclude both that base, and the string "10" in order to encode6999500235148669.But that seems to make the randomness of a number dependent on thebase used to write it down? Did I have to write down "And this is inbase 10" to show that 6999500235148668 is random? There seems to bean equivocation here on "computing a number" and "computing arepresentation of a number".

`Only for the numbers or strings with size similar to the size of the`

`universal number use for the compression. This means it works for`

`almost all numbers (= all except a finite number of exception).`

For the majority of numbers, you will find the Kolmogorovcomplexity of the number to almost always be on the order of thenumber of digits in that number. The exceptions like 1111111111are few and far between.111111111 looks a lot messier in base 9.

Sure. Bruno 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.