# Prove that the Kolmogorov complexity function cannot be approached from below

How would one go about proving that Kolmogorov function $K(x)$ cannot be approached from below by any computable function?

After some research it seems I must show the function $K(x)$ is not lower semi-computable.

Instead, I can do this by showing $-K(x)$ is not upper semi-computable

Intuitively it seems that $K(x)$, the length of the smallest program computing $x$, can always get smaller, but could be approached using a convergent function... but this is clearly not the case, so I'm obviously a bit lost.

I would be very grateful if someone could explain how I might approach such a proof. I'm more interested in the approach, I might encounter similar questions in an upcoming exam.

Thanks a lot.

• Attend classes, do the homework, and you'll be fine, assuming you have enough mathematical experience behind you. – Yuval Filmus Mar 25 '16 at 21:27

We can computably approach $K(x)$ from above by trying all programs. Since $K(x)$ is not computable, we cannot computably approach it from below — otherwise it would have been computable.
• I understand your logic. However, I believe we don't yet know this fact that $K(x)$ is not computable. In saying that, it might be easier for me to prove $K(x)$ is not computable and then use that to show $K(x)$ is not approachable. Unless one uses the other? – Greg Peckory Mar 25 '16 at 21:33
• Since it is trivial to see that $K$ is upper semi-computable, proving that $K$ is not lower semi-computable and proving that it is not computable are at the same level of difficulty. The proof uses diagonalization and is pretty standard, and I'm sure you will see it soon enough if you haven't seen it already. – Yuval Filmus Mar 25 '16 at 21:35