2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Attend classes, do the homework, and you'll be fine, assuming you have enough mathematical experience behind you. $\endgroup$
    – Yuval Filmus
    Mar 25 '16 at 21:27
3
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ 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? $\endgroup$
    – Greg Peckory
    Mar 25 '16 at 21:33
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Mar 25 '16 at 21:35
  • $\begingroup$ Why can't non-computable functions be approached from below? But they can from above? $\endgroup$
    – Greg Peckory
    Mar 29 '16 at 11:07
  • $\begingroup$ I'm not claiming anything about all functions, only about this specific function (Kolmogorov complexity). $\endgroup$
    – Yuval Filmus
    Mar 29 '16 at 11:18
  • $\begingroup$ Oh, apologies. Well in this specific case, why does non-computability imply it can't be approached from below? Thanks for the help btw. $\endgroup$
    – Greg Peckory
    Mar 29 '16 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.