Conference noted::hackers_v1

103.0. "Practical Kolmogorov Complexity" by RANI::LEICHTERJ () Tue Mar 26 1985 21:39

[Kolmogorov Complexity measures the difficulty of a problem by the length of
the shortest program that solves it.]

In recent weeks, I've come across two amusing "real-world" (though hacky)
Kolmogorov complexity like challenges:

1.  Reported to me by Larry Carter of IBM Watson Labs.  They had a challenge
going for a while:  WRite the shortes program to translate EBCDIC to ASCII.
If you look at EBCDIC, you'll see that the translation is quite irregular,
so you have a lot to play with.  An obvious thing to use is the IBM 370
Translate instruction, which will do the actual translation in one instruction.
But, you then need a 256-byte translation table.  The table is bigger than
some complete programs.  "Solution":  Somewhere in memory, someone is almost
certain to have a copy of the table.  Search for it.  To search efficiently
in a small amount of space, what you actually use is a hash coding scheme -
you compute (say) 64-bit signatures of successive 256-byte blocks starting at
every memory location until one gives you the pre-computed right value.  Then
use that block.  With a properly chosen random signature scheme, the chance of
a false match is extremely small - smaller than the chance of a couple of
undetected memory errors while you are running.

2.  A context at CMU:  Write the shortest program that, when run, prints the
words in a given dictionary (some 90,000 English words).  (And no others, of
course.)  Obviously, any data files count against the size of your program
(for simplicity, they made you include all your data in-line and forbade the
use of any additional files.)  So, the whole game is clever compression of the
words in the dictionary.

The winning program got something on the order of an 11-fold compression over
the original dictionary (straight ASCII text).
							-- Jerry