#algorithmic complexity

Computer Science and Biology Explore Algorithmic Evolution | Quanta Magazine

Algorithmic information theory essentially says that the probability of producing some types of outputs is far greater when randomness operates at the level of the program describing it rather than at the level of the output itself, because that program will be short. In this way, complex structures — fractals, for instance — can be more easily produced by chance.

But a problem with that approach quickly emerged: Mathematicians learned that the algorithmic complexity (also known as Kolmogorov complexity, after Andrey Kolmogorov, one of the theory’s founders) of a given output — the length of the shortest possible program needed to specify it — is not computable. Computer scientists therefore couldn’t determine the ideal way to compress a string or other object.

As a result, algorithmic information theory was mostly relegated to the realm of pure mathematics, where it’s used for exploring related theorems and defining the concepts of randomness and structure. Practical uses seemed out of reach. “Mathematically, it’s a simple, beautiful measure of complexity,” said the noted mathematician Gregory Chaitin, formerly at the IBM Thomas J. Watson Center and the Federal University of Rio de Janeiro, and another of the theory’s founders. “But it looked unapproachable for real-world applications.”

That didn’t stop him from trying. He hoped the theory could be used to formalize the idea that DNA acts as software. In 2012, he published a book describing how evolution could be seen as a random walk through software space. The mutations along that walk, he argued, do not follow a statistically random probability distribution; instead, they follow a distribution based on Kolmogorov complexity. But he had no way to test it.

That's exponential growth. If you have four time travellers, each of whom would have, alone, needed about 10 tries to make their thing happen, a bystander would live through about ten thousand iterations before they can move on. If you have six time travellers, that number becomes one million iterations. And so on.

so, if there are five people going to the party, each will have to shake hands with four other people, for a total of ten handshakes. if a sixth person shows up, another five handshakes will have to happen, for a total of fifteen. and so forth.

thus, the total number of handshakes increases quadratically, according to the formula (n²-n)/2. this is still within the realm of "feasible" complexity, according to the usual standard; it's polynomial. but it's superlinear, so it quickly leaves the zone where you can just throw more effort at the problem and expect to overpower it.