|
|
Re: strange question about infinity (zipping an infinite file)
Posted:
Jul 29, 2001 12:04 PM
|
|
Jan Panteltje wrote:
>
> I have this strange question about infinity.
> It comes from some problem with generating random numbers discussed in
> sci.crypt.
> On a Linux system you can do cat > /dev/urandom > file
> This will (given enough disk space :-)) create an infinite long file.
>
> Someone pointed that out and said to use dd, which will copy only n bytes.
> Then I wanted to make a joke and say:
> 'Well, if the file is infinite length just zip it!'
>
I assume that to zip a file is to compress it according to a specific
algorithm (or one of a small number of specific algorithms). If one is
allowed to use any method according to the file presented, then an
infinite file (if there was such a thing) containing
012345...
could be compressed to the finite description
The natural numbers in their usual order.
If your random number generator can produce arbitrarily large numbers,
then sometimes it may produce 012345... but not often. But even if we
could handle an infinite file how would we know that it was this
particular one? urandom could perhaps be modified to tell us that its
output was the natural numbers in their usual order. And, very
appropriately, it could do so on stderr.
Though the above is not to be taken seriously; if you are interested in
randomness and compressing (or failing to compress) _finite_ sequences,
you may wish to look up Chaitin.
A further silly thought: if our modified urandom produces
0,1,2,3,4,5,6,7,8,9,10,11,12,... it will tell us that its output was the
natural numbers in their usual order. What if it produces
0,1,2,3,4,5,6,7,8,9,1,0,11,12,...? Will it tell us a convenient lie?
Here I assume that the file contains unseparated numerals, if it were to
contain binary the question can be re-phrased.
|
|
