# Computability of Kolmogorov Complexity

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$?

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.
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.