kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) (04/06/91)
In article <1991Apr6.080615.23197@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: [complains about sci.match & sci.crypt-related articles] >This group is targeted toward advancing the state of data compression, >and it is going to be a hard enough task without having to dodge lots of >noise postings. Well I can understand this point of view, but with reservations I should point out that number representation, cryptography and compression are intimately related. For a nice survey (although a little mathematical) see Report CS-R8813, Centrum voor Wiskunde en Informatica (don't worry, it's in English) the Kolmogorov memorial issue. Some very nice things. F'rinstance (glad you asked me) they discuss the so-called ``number of wisdom'' (Omega) which is the probability a random Turing-machine will halt (including ones trying to, e.g., verify Fermat's conjecture). We can see Omega is in (0,1) and is a little tricky to compute (i.e. it is random in the strong Kolmogorov sense). One use of this number is to verify whether a given program will halt. Let p be the (Turing) program with its length in bits |p|=n. This program has probability of 2^-n of being generated at random (by fair coin tosses). If we know the first n bits of Omega (Omega_n) then we have Omega_n < Omega < Omega_n+2^-n Now we can timeshare or interleave the running of all Turing programs so we obtain an approximation of Omega (Omega') such that Omega' > Omega_n If p is NOT one of the halted programs found in this approximation process then it will never halt (since otherwise it would contribute 2^-n and Omega > Omega'+2^-n which is a contradiction). Thus we have a case of a Kolmogorov random number, supposedly not compressible, that can be compressed (approximated) in some sense. Wonderful stuff. -kym
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (04/07/91)
In article <1991Apr6.080615.23197@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: > This group is targeted toward advancing the state of data compression, > and it is going to be a hard enough task without having to dodge lots of > noise postings. Looks like it's already time to think about comp.compression.bul---uh, I mean, comp.compression.theory. The important discussions can go into comp.compression.practice, or perhaps comp.compression.{lossy,lossless}. ---Dan