On 29 Dec 2013, at 22:51, meekerdb wrote:

## Advertising

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 theory thatno 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 more 2digit numbers than 1 digit numbers, and more 3 digit numbers than 2digit numbers, and so on. For any string you can represent using ashorter string, another "shorter string" must necessarily bedisplaced. You can't keep replacing things with shorter stringsbecause there aren't enough of them, so as a side-effect, everycompression strategy must represent some strings by larger ones.In fact, the average size of all possible compressed messages (withsome upper-bound length n) can never be smaller than the averagesize 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. But just because you cannot compress allnumbers of a given size doesn't imply that any particular number isincompressible. So isn't it the case that every finite numberstring is compressible in some algorithm? So there's no sense tosaying 6999500235148668 is random, but 11111111111111 is not, exceptrelative to some given compression algorithm.

`It works up to a constant related to the choice of the universal base`

`to do the compression. "11111111111111" is probably random in the SK`

`combinator language. But for strings which are greater than the`

`description of the universal bases used, the same strings will be`

`random or not.`

Bruno

Brent --You received this message because you are subscribed to the GoogleGroups "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.