Kolmogorov Complexity and Our Search for Meaning
While what the author says is true (and I'm sure he knows vastly more about the subject than I do), I think the way that Kolmogorov complexity is described in the article is a bit misleading to a general audience. For short strings, we often can and <i>do</i> compute the Kolmogorov complexity. See some of Hector Zenil's work, e.g. "Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines" (<a href="https://arxiv.org/abs/1211.1302" rel="nofollow">https://arxiv.org/abs/1211.1302</a>).<p>What "uncomputable" means is that for the <i>general</i> case, there cannot exist a program that is guaranteed to find the Kolmogorov complexity of a given input string. This is because as we enumerate through all Turing machines from smallest to largest, some will not halt, but we can’t know if this is because the program is just running for a very long time or if it is actually going to run forever.  In specific cases for short strings, we can often analytically determine whether the program will halt or not. This is also why we know the first few values of the Busy Beaver function, even though it is also uncomputable.