<p>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 </p>

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

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

<p>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.</p>

<p><a href="http://www1.maths.leeds.ac.uk/~pmt6sbc/" rel="nofollow">Barry Cooper</a> and colleges have been interested in these sets and the notion of computability in limit. You may want to check his <a href="http://arxiv.org/abs/1109.1416" rel="nofollow">"Definability in the Real Universe"</a> article from <a href="http://books.google.ca/books?id=48rfPEiv9eIC&amp;lpg=PA61&amp;ots=Zl1g9L9D2Q" rel="nofollow">"Computability In Context: Computation and Logic in the Real World"</a>.</p>

CC BY-SA 3.0
2013-05-03T15:18:24.157Z
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?
Peter
CC BY-SA 3.0
2013-05-03T15:43:33.593Z
@Peter, the difference of two c.e. sets is an $n$-c.e. set (for any $n\geq 2$).
Kaveh
CC BY-SA 3.0
2013-05-03T16:14:39.187Z
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.
Peter
CC BY-SA 3.0
2013-05-03T17:00:44.113Z
@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.
Kaveh
CC BY-SA 3.0
2013-05-03T17:40:48.660Z
Ah, I see the problem now. Thanks for your patience.
Peter
CC BY-SA 3.0
2013-05-03T01:44:38.120Z
2013-05-03T01:50:16.860Z
2013-05-03T01:50:16.860Z
Kaveh
<p>I came across the following definition in <a href="http://scholar.google.com/scholar?hl=en&amp;q=Nonapproximability+of+the+normalized+information+distance&amp;btnG=&amp;as_sdt=1%2C5&amp;as_sdtp=" rel="nofollow">a paper</a>:</p>

<blockquote>
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) &lt; 0$ is bounded by $n − 1$. That is, $n − 1$ is a bound on the number of fluctuations of the approximation. 
<br/><br/>
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.
</blockquote>

<p>I have two questions. </p>

<ul>
<li>Is this a commonly used principle? Google didn't give me any relevant results.</li>
<li>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) &lt; \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.</li>
</ul>

<p>So the definition doesn't seem to make sense. Am I missing something?</p>

<computability><approximation>
n-approximable functions
Peter
# n-approximable functions

(Asked by: username_0 on 2013-05-02)

I came across the following definition in [a paper](http://scholar.google.com/scholar?hl=en&q=Nonapproximability+of+the+normalized+information+distance&btnG=&as_sdt=1%2C5&as_sdtp=):

> 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?

**Tags:** computability, approximation


---

## 1 answers

### Answer by username_1 on 2013-05-03. Score: 3 | Accepted answer

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](http://www1.maths.leeds.ac.uk/~pmt6sbc/) 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"](http://arxiv.org/abs/1109.1416) article from ["Computability In Context: Computation and Logic in the Real World"](http://books.google.ca/books?id=48rfPEiv9eIC&lpg=PA61&ots=Zl1g9L9D2Q).

> **Comments:**
> **username_0**: 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?  
> **username_1**: @username_0, the difference of two c.e. sets is an $n$-c.e. set (for any $n\geq 2$).  
> **username_0**: 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.  
> **username_1**: @username_0, 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.  
> **username_0**: Ah, I see the problem now. Thanks for your patience.  

---

