I came across the following definition in a paper:
We can extend the notion of an $n$-c.e. [n-computably enumerable] set to a notion that measures the number of fluctuations of a function as folows: For every $n \geq 1$, call $f : N \rightarrow R$ n-approximable if there is a rational-valued computable approximation $\varphi$ such that $\lim_{k\rightarrow \infty} \varphi(x, k) = f(x)$ and such that for every $x$, the number of $k$’s such that $\varphi(x,k + 1) − \varphi(x,k) < 0$ is bounded by $n − 1$. That is, $n − 1$ is a bound on the number of fluctuations of the approximation.
Note that the $1$-approximable functions are precisely the lower semicomputable ($\Sigma_1^0$) ones (zero fluctuations). Also note that a set $A \subseteq \mathbb N$ is $n$-c.e. if and only if the characteristic function of A is n-approximable.
I have two questions.
- Is this a commonly used principle? Google didn't give me any relevant results.
- If I have an $n$-c.e. function $\varphi(x)$, with $\varphi(x,k)$ approximating it. Couldn't I just build a Turing machine $\varphi'(x, k')$ that dovetails the computation of $\varphi(x, k)$ until it sees two consecutive halting machines with $\varphi(x, k+1) < \varphi(x, k)$, stops the dovetailing, and outputs $\varphi(x, k+1+k')$ (ie. it computes $\varphi(\cdot, \cdot)$ but starting from k+1). Then, if $\varphi(x)$ is $n-c.e.$ (and not $n+1$-c.e.), it is also $n-1$-c.e., and by induction it is just approximable.
So the definition doesn't seem to make sense. Am I missing something?