# What does 'computable in the limit from above' mean?

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

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.
If a function $f$ is both upper semicomputable and lower semicomputable on its domain, then we call $f$ computable
• 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. – jkrshw Oct 23 '12 at 7:39