During a discussion today about artificial intelligence, I had an odd thought.
People who study computer science know that any algorithm takes a certain minimum amount of space to write. Beyond that, you just can’t make the algorithm any smaller. Some algorithms are very simple and take up little space, whereas others are huge and complex, yet the description of any given algorithm can only be compressed so much, and no more.
But what if you used people to compress algorithms? Instead of writing out the algorithm in a formal program, so that a computer can execute it step by step, suppose you just describe the algorithm to another person, and then let them write the computer code?
The resulting description might be a lot smaller. Of course it’s not the same — we are now relying on human brains to fill in the missing bits. Fortunately, there are about seven billion human brains in the world, and many of them are quite good at this sort of thing.
For example, here is how I might describe a bubble sort to a friend: “Repeatedly go down a list, swapping pairs of items that are not in order. Stop when nothing is swapped.”
If my friend knows how to program, she can turn that description into code. She would need to add in lots of bothersome details (loop constructs, iterating variables, conditionals, array declaration, etc) — none of which were in my original description. But any decent programmer would know how to do that.
Wouldn’t it be cool if this leads to a simpler way to describe algorithms?
By this standard, the prompt given to an improv theater troupe as the basis for their performance is actually a highly compressed form of the performance they end up creating. A revolution in text compression algorithms!
So would you consider rent-acoder.com to be an implementation of this compression method?
Rent-acoder might be an implementation of this. I’d need to look into it more.
But the improv theater example definitely doesn’t fit the bill, since the prompt given to the troupe is not a description of an algorithm. Each time the troupe performs, it creates a different result.
One may consider this a lossy compression scheme for algorithms.
Joe: It would be interesting to see what the result is if you try to frame it to be truly lossless. For example, you and I could come up with some conventions, after which I could write:
Repeat
go through list
swap adjacent items in wrong order
Until no swaps
You would understand that “pseudo-code” perfectly, but a computer couldn’t. So here we have a lossless compression scheme for algorithms — as long as a human programmer is interpreting it and turning it into code.