Dear Brent and Jason, I think that this is an important idea: the relationship between compression algorithms and numbers. It does not look like a simple one-to-one and onto map!
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 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. >> >> Brent >> > > > Brent, > > It is easy to see with the pigeon hole principal. There are more 2 > digit numbers than 1 digit numbers, and more 3 digit numbers than 2 digit > numbers, and so on. For any string you can represent using a shorter > string, another "shorter string" must necessarily be displaced. You can't > keep replacing things with shorter strings because there aren't enough of > them, so as a side-effect, every compression strategy must represent some > strings by larger ones. In fact, the average size of all possible > compressed messages (with some upper-bound length n) can never be smaller > than the average size of all uncompressed messages. > > The only reason compression algorithms are useful is because they are > tailored to represent some class of messages with shorter strings, while > making (the vast majority of) other messages slightly larger. > > > A good explanation. But just because you cannot compress all numbers of a > given size doesn't imply that any particular number is incompressible. So > isn't it the case that every finite number string is compressible in some > algorithm? So there's no sense to saying 6999500235148668 is random, but > 11111111111111 is not, except relative to some given compression algorithm. > > Brent > > -- > You received this message because you are subscribed to a topic in the > Google Groups "Everything List" group. > To unsubscribe from this topic, visit > https://groups.google.com/d/topic/everything-list/sqWzozazMg0/unsubscribe. > To unsubscribe from this group and all its topics, 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. > -- Kindest Regards, Stephen Paul King Senior Researcher Mobile: (864) 567-3099 stephe...@provensecure.com http://www.provensecure.us/ “This message (including any attachments) is intended only for the use of the individual or entity to which it is addressed, and may contain information that is non-public, proprietary, privileged, confidential and exempt from disclosure under applicable law or may be constituted as attorney work product. If you are not the intended recipient, you are hereby notified that any use, dissemination, distribution, or copying of this communication is strictly prohibited. If you have received this message in error, notify sender immediately and delete this message immediately.” -- 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.
