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.