$H(x)$ is the program size complexity of $x$ for some universal Turing machine $U$. $H$ is not computable, however $H$ is "computable in the limit from above".

From my notes:

i.e the set $\{(x,n) \mid x \in B^*,n \geq 0, H(x) \leq n\}$ is computably enumerable.

Can someone tell me what this means? I understand the incomputability of $H$ but the term "limit from above" is confusing me.


To quote Wikipedia/Scholarpedia,

A partial function $f$ from the rational numbers to the real numbers is upper semicomputable if it is defined by a rational-valued partial computable function $\phi(x,k)$ with $x$ a rational number and $k$ a nonnegative integer such that $\phi(x,k+1)≤ϕ(x,k)$ for every $k$ and $\lim_{k \to \infty}\phi(x,k)=f(x)$. This means that $f$ can be computably approximated from above.

Further, using the squeeze theorem, we could conclude:

If a function $f$ is both upper semicomputable and lower semicomputable on its domain, then we call $f$ computable

  • $\begingroup$ Thanks, relating the term to upper semicomputable helps a lot! Also I believe the function $H$ is related to the Kolmogorov complexity , although the prof hasn't used that term. $\endgroup$ – jkrshw Oct 23 '12 at 7:39

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.