3
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
3
$\begingroup$

This is a special case of what is called an $f$-c.e. set. A set $A$ is $f$-c.e. iff there is computable function $g$ such that

  • $\chi_A(x) = \lim_i g(x,i)$, and
  • $\forall x \ |\{s \mid g(x,i) \neq g(x,i+1) \}| \leq f(x)$.

If we consider $f(x)=n$ then we get the definition of $n$-c.e sets.

They don't need to be c.e. because c.e. is not closed under complement. Take two c.e. sets and take their difference. It is a $2$-c.e. set but it does not need to be a c.e. set.

Barry Cooper and colleges have been interested in these sets and the notion of computability in limit. You may want to check his "Definability in the Real Universe" article from "Computability In Context: Computation and Logic in the Real World".

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ As far as I can see this just says that (the characteristic sequences of) n-approximable functions and n-c.e. sets are both subsets of f-c.e. sets. n-c.e. sets are a strict superset of the c.e. sets, so f-c.e. sets are as well. Fine. But that still doesn't mean that the n-c.e. functions above are a strict superset of the c.e. functions... right? $\endgroup$ – Peter May 3 '13 at 15:18
  • $\begingroup$ @Peter, the difference of two c.e. sets is an $n$-c.e. set (for any $n\geq 2$). $\endgroup$ – Kaveh May 3 '13 at 15:43
  • $\begingroup$ I understand that, and I have no problem with the definition of n-c.e. sets. Just with the extension to n-approximable functions above. I don't (yet) see how your answer solves my objection. $\endgroup$ – Peter May 3 '13 at 16:14
  • $\begingroup$ @Peter, here is a simple example: let $g(x,k)$ be $1$ unless TM with code $x$ halts in $k$ steps. $g$ is a $2$-approximation to the complement of halting problem which is not c.e., your dove-tailing works correctly on those $x$ which halt but not those which do not halt. In other words, you don't have the exact number of changes, you only have an upper-bound on their number, and when you don't see a change your dove-tailing will continue forever without returning any answer. $\endgroup$ – Kaveh May 3 '13 at 17:00
  • $\begingroup$ Ah, I see the problem now. Thanks for your patience. $\endgroup$ – Peter May 3 '13 at 17:40

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.