Drexel dragonThe Math ForumDonate to the Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: strange question about infinity (zipping an infinite file)
Replies: 14   Last Post: Aug 13, 2001 8:14 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Peter Percival

Posts: 339
Registered: 12/6/04
Re: strange question about infinity (zipping an infinite file)
Posted: Jul 29, 2001 12:04 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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


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.

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.