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.
Now, some scientists are hoping to revive the theory in that context — to make it relevant to areas in both biology and computer science.