Path: utzoo!utgpu!news-server.csri.toronto.edu!csri.toronto.edu!blaak
Newsgroups: comp.compression
From: blaak@csri.toronto.edu (Raymond Blaak)
Subject: Re: Another naive question
Message-ID: <1991Apr10.152617.14042@jarvis.csri.toronto.edu>
References: <14292@helios.TAMU.EDU>
Date: 10 Apr 91 19:26:18 GMT
Lines: 40

byron@archone.tamu.edu (Byron Rakitzis) writes:
 
>Just thinking about it in the shower, it occurs to me that one might be
>able to take any given binary string, and say, "this turing machine foo
>can print this string bar". If foo's number (you can enumerate all turing
>machines) has a smaller number of digits than the original string bar, then
>you've just shown something interesting about bar, namely that it has a more
>compact representation in the form of a turing machine foo.

>Byron.
>---
>char*c,q[512],m[256],*v[99],**u,*i[3];f[2],p;main(){for(m[m[60]=m[62]=32]=m...
...lots of stuff deleted...
>2):6;}e(x){x<0?write(2,"?\n$ "-x/4,2),x+1||exit(1):5;}z(i){close(i);}
>				(by Byron Rakitzis and Sean Dorward)

First off, what does your signature do? I am afraid to run it on my machine.

About the entropy of data:

You are right. If you can find a program whose representation is smaller than
that of the string it generates, then you have a more compact representation.

But in order for this to happen their must be some regularity or pattern in
the string. If the string is totally random, the most compact representation
of the string is itself.

Another consideration is: even if there is a turing machine whose "number"
has less digits than the string it prints, how can you find it? There is no
universal algorithm for such a thing.

What compression algorithms do is just try a finite number of techniques
(often just 1) a choose the one that works the best. Even then the result may
be no where near perfect. Consider the digit string that represents pi. It is
infinitely long. Any frequency count method used will still result in an
infinitely long string. However, the program that generates pi is pretty
short (mind you, it takes infinitely long to run).

Cheers,
Ray