Newsgroups: comp.compression
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!sarah!bingnews!kym
From: kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell)
Subject: Re: Please take the recreational math articles elsewhere Re: Program for Calculating PI
Message-ID: <1991Apr6.153042.25090@bingvaxu.cc.binghamton.edu>
Organization: State University of New York at Binghamton
References: <1991Apr4.150053.29873@linus.mitre.org> <1991Apr5.064220.18509@dde.dk> <1991Apr6.080615.23197@zorch.SF-Bay.ORG>
Date: Sat, 6 Apr 1991 15:30:42 GMT

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