Lower semicomputable function

A function $f:X\to \mathbf{R}$ is lower semicomputable iff there exists a computable function $g:X\times \mathbf{N}\to \mathbf{Q}$ such that:

• for all $x\in X$ and all natural numbers $n$, we have $g(x,n+1)\ge g(x,n)$
• for all $x\in X$ we have $\underset{n\to \mathrm{\infty }}{lim}g(x,n)=f(x)$

The way to think of this is that given some fixed $x\in X$, the values $g(x,0),g(x,1),g(x,2),\dots$ are successive approximations of the value $f(x)$, and we have $g(x,0)\le g(x,1)\le g(x,2)\le \cdots \le f(x)$.

The definition says nothing about the rate of convergence, so for instance if we want $g(x,n)$ to be within $1/1000$ of the value of $f(x)$, there is not in general some way to find a large enough $n$.

If we do not know the value of $f(x)$ in advance, it is not possible to tell in general how far away $g(x,n)$ is from $f(x)$. We would know that $g(x,1000)$ is at least as close to $f(x)$ as $g(x,100)$, but it's not clear how much closer. In contrast, if a function is both lower and upper semicomputable, then we would have an approximation from above, say $h(x,n)$. Then $g(x,n)\le f(x)\le h(x,n)$, so we have an estimate that is off by at most $h(x,n)-g(x,n)$.

Lower semicomputability can be characterized using the idea of recursive enumerability as follows: $f:X\to \mathbf{R}$ is lower semicomputable if and only if the set $\{(x,q)\in X\times \mathbf{Q}:f(x)>q\}$ is recursively enumerable.

Examples:

• Every computable function is lower semicomputable (Why?)
• Kolmogorov complexity?