Data Science PT 5: Kolmogorov Complexity

Is there an “ultimate” complexity? The Minimum description length calls for  0.5log2(N)+O(1) bits per parameter with lots of higher-order bounds. What if there's no parametric model? 

Kolmogorov complexity helps to come up with the shortest program that generates data X at output. After this, it halts. It relies on Turing Machines, or computers that halt. The pro for this is that up to constant term, Kolmogorov complexity is optimal. The constant term is the length of the compiler to translate between machines. We can ask, "What is the shortest program that accesses X, generates Y, then stops?" 

The con for this is that this complexity is more theoretical based and not computable. We would need to evaluate all programs with length up to K(X). Some of these program's don't halt, and Turing proved that some problems are infinite to solve or unsolvable. There are, however, ways to get close to this complexity, and this could be expressed in a Turing framework. Any modern device can simulate Turing Machines, and vice versa. 

Just some food for thought.