mauls@warwick.ac.uk (The Chief Slime Monster) (04/12/91)
With all this talk of finding strings in infinite expansions I thought I
would mention something a colleague and I thought of. I don't spose it is
original, in fact, you've probably all read it before in this newsgroup,
but here goes.
A chain function is just a function that generates a finite number of unique
values and then cycles:
i.e. f(n) = f(1), for some n, otherwise all f(i) != f(j) 1<=i<j<n.
The postulation was this:
Consider file as binary string length L. There exists a chain function
which will step uniquely through every possible binary string of length L
before repeating. Then, if the file string is equal to f(N), where f is
the chain function, and N is a number, replace the string with the binary
representation of N. To decompress, just calculate f(N).
Not surprisingly, the representation of N is not, on average, smaller than
the file string.
Slime