Computability of Kolmogorov Complexity

Question

Fix a universal Turing machine $M$.

Let $A^*=\{0,1\}^n$ be the set of all binary string of length $n$.

Determine the Kolmorogov complexity $K(x)$ of each $x\in A$, w.r.t. $M$.

Just for a matter of simplicity assume that $K(x)'=\min(|x|,K(x))$.

Let $B^*=\{0,1\}^n$ be the set of all programs $y\in B$ of $T$: $x= M(y)$.

Now, suppose a parallel machine $M_p$ that can run each program $y\in B$ for each element in $A$, in parallel. So we can get the length of all the programs $y$ whose machine ended with the right string $x$, and take the minimum as $K(x)'$.

So, should I assume that the non-computability is due to the fact that some machines that has not ended jet whose inputs $y$ are less than the current minimal program will eventually halt? What's the probability of this?

Also, maybe a measure of complexity should include a minimal length with a probabilistic confidence? Say $P(K(x)\geq l)\geq p$?

Answer 1

That's right. You can run all machines in parallel and you'll find shorter and shorter descriptions, but at some point there will always be a shorter program still running, for which you can't prove that it won't halt with $x$ as output.

The probability you describe (of a program not halting, assuming some distribution on inputs) is the complement to Chaitin's omega: the probability that a program will halt. Of course, Chaiting's omega is also not computable and the best way we have of approximating it, is just by running all programs in parallel and summing the probabilities for the ones we've seen halting.

If you start with a probability distribution on outputs, the probabilities have different bounds. If you take a uniform distribution on strings of length $n$, then as $n \rightarrow \infty$, the proportion of strings compressible by more than a few bits is negligible, ie. $K(x) \approx |x|$ with near certainty for large $n$. If you take the universal distribution, then every computable pattern will appear in your string with some probability.