complexity

Day 38: Algorithmic complexity

I’ve had an interest in Kolmogorov complexity for a long time, ever since I was first introduced to the minimum description length principle through the work of Peter Grünwald and Jorma Rissanen. The idea is deceptively simple. The inherent complexity of any given string is the length of the shortest program that is guaranteed to produce that string and then stop. So for instance, a string like this abbabbabbabbabbabbabbabbabbabb" can be produced with a very short R program: