Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!umriscc!maverick.ksu.ksu.edu!iowasp.physics.uiowa.edu!ns-mx!pyrite.cs.uiowa.edu
From: jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879)
Newsgroups: comp.compression
Subject: Hard to compress string (Was: theoretical compression factor)
Message-ID: <5299@ns-mx.uiowa.edu>
Date: 5 Apr 91 14:50:38 GMT
References: <1991Apr4.230820.3941@bingvaxu.cc.binghamton.edu>
Sender: news@ns-mx.uiowa.edu
Lines: 24

In article <VICTOR.91Apr4102353@irt.watson.ibm.com>
victor@watson.ibm.com writes:

>people thinking is from a paper of Ziv and Lempel:  Construct a
>sequence of bits as follows: first write down in order all 1 digit
>binary numbers (with leading zeroes if they are there), then all two
>digit, etc.  The surprising fact that they prove is that this sequence
>is incompressible by ANY finite-state compressor ...

On a similar line, the sequence of decimal digits below will pass most
tests for randomness.  I first encountered this sequence as an example
of a patently non-random digit stream that passes essentially every test
for randomness you can devise (short of knowing the algorithm).  Indeed,
as Ziv and Lempel point out, it would be quite hard to compress, although
a locally adaptive compressor might be able to adapt to the locally
periodic behavior this string exhibits.

  01234567891011121314151617181920212223242526272829303132333435363738394...

If you didn't catch on, the string consists of the decimal integers, with
no leading zeros except for zero itself, concatenated into an infinite
string.
					Doug Jones
					jones@cs.uiowa.edu