<p>If the family function $f(x,n)=f_n(x)$ is computable then these are exactly the $\Delta^0_2$ functions, or equivalently, the functions that are Turing reducible to the halting set $0'$, which are very well studied within <a href="/questions/tagged/computability-theory" class="post-tag" title="show questions tagged &#39;computability-theory&#39;" rel="tag">computability-theory</a>.</p>

<p>There are also other, not equivalent, notions of almost computable that go by names such as generically computable and coarsely computable, see e.g.
Jockusch et al.: <a href="https://arxiv.org/abs/1610.06504" rel="noreferrer">Asymptotic Density and the Theory of Computability: A partial survey</a>.</p>

CC BY-SA 4.0
2018-08-23T03:22:20.863Z
2018-08-23T05:27:41.220Z
2018-08-23T05:27:41.220Z
Bjørn Kjos-Hanssen
<p>It seems that we can define a notion of being “approximately computable” where a set, $S$, is approximately computable if there is a family of computable functions $f_n(x)$ such that $$\lim_{n\to\infty} f_n(x)=\chi_S(x)$$ Under this definition, I believe that the halting set is approximately computable and that a set is computable if and only if it is <em>uniformly</em> approximately computable.</p>

<p>I haven’t been able to find anything online about this notion, or any other notion, of approximately computable. This doesn’t seem particularly novel, and I’m surprised I can’t find any resources on it. <strong>Has an idea of “approximately computable sets” been studied</strong>? Do they all collapse to merely computable for a reason I haven’t seen?</p>

<p>By diagonalization, there are set that aren’t approximately computable under my definition. It seems likely that any reasonable definition of “approximately computable” would similarly only apply to $\aleph_0$-many sunsets of $P(\mathbb N)$. Assuming that there is a reasonable definition, is there a criteria (perhaps a level of the arithmetic hierarchy) where all sets above that level are not approximately computable?</p>

<hr>

<p>I am thinking about this because I’ve been reading about combinatorial game theory recently, and about games with only uncomputable winning strategies. It seems plausible that a computer might be able to play a game extremely close to optimally in some sense, perhaps that they play the closest to optimally of all programs of size $\leq n$. Sets that don’t have a computable approximation seem like candidates for building games where computers can only play the game poorly. If anyone has references for investigations of this idea, I would be very interested in that as well.</p>

CC BY-SA 4.0
2018-08-24T14:28:05.083Z
"By diagonalization, there are set[s] that aren't approximately computable under my definition." Can you expand? I have trouble seeing why not all sets are approximately computable...my reasoning is that for any set $S$, we can take $f_n(x) = \chi_S(x)$ for $|x| \leq n$ and $f_n(x) = 0$ otherwise, by simply hardcoding the answers for the finitely many such $x$. All $f_n$ are computable and their limit is $\chi_S$...
usul
CC BY-SA 4.0
2018-08-25T19:08:30.547Z
@usul Yes, you’re right. I forgot to specify the additional restriction in the first sentence of Bjorn’s answer. If we don’t require that $f(x,n)$ be computable, then every set satisfies by definition. With that additional specification, you can diagonalize because the function $f(x,n)$ is a computable function that witnesses the fact that exactly one set is approximately computable.
Stella Biderman
CC BY-SA 4.0
2018-08-25T23:31:08.330Z
thanks. Another reason I asked was I also had trouble understanding that restriction and how the limit w.r.t. $n$ still makes sense, but I see now.
usul
<reference-request><computability>
Is there a useful notion of being “approximately computable”
Stella Biderman
# Is there a useful notion of being “approximately computable”

(Asked by: username_0 on 2018-08-23)

It seems that we can define a notion of being “approximately computable” where a set, $S$, is approximately computable if there is a family of computable functions $f\_n(x)$ such that $$\lim\_{n\to\infty} f\_n(x)=\chi\_S(x)$$ Under this definition, I believe that the halting set is approximately computable and that a set is computable if and only if it is *uniformly* approximately computable.

I haven’t been able to find anything online about this notion, or any other notion, of approximately computable. This doesn’t seem particularly novel, and I’m surprised I can’t find any resources on it. **Has an idea of “approximately computable sets” been studied**? Do they all collapse to merely computable for a reason I haven’t seen?

By diagonalization, there are set that aren’t approximately computable under my definition. It seems likely that any reasonable definition of “approximately computable” would similarly only apply to $\aleph\_0$-many sunsets of $P(\mathbb N)$. Assuming that there is a reasonable definition, is there a criteria (perhaps a level of the arithmetic hierarchy) where all sets above that level are not approximately computable?

---

I am thinking about this because I’ve been reading about combinatorial game theory recently, and about games with only uncomputable winning strategies. It seems plausible that a computer might be able to play a game extremely close to optimally in some sense, perhaps that they play the closest to optimally of all programs of size $\leq n$. Sets that don’t have a computable approximation seem like candidates for building games where computers can only play the game poorly. If anyone has references for investigations of this idea, I would be very interested in that as well.

**Tags:** reference-request, computability

> **Comments:**
> **username_1**: "By diagonalization, there are set[s] that aren't approximately computable under my definition." Can you expand? I have trouble seeing why not all sets are approximately computable...my reasoning is that for any set $S$, we can take $f_n(x) = \chi_S(x)$ for $|x| \leq n$ and $f_n(x) = 0$ otherwise, by simply hardcoding the answers for the finitely many such $x$. All $f_n$ are computable and their limit is $\chi_S$...  
> **username_0**: @username_1 Yes, you’re right. I forgot to specify the additional restriction in the first sentence of Bjorn’s answer. If we don’t require that $f(x,n)$ be computable, then every set satisfies by definition. With that additional specification, you can diagonalize because the function $f(x,n)$ is a computable function that witnesses the fact that exactly one set is approximately computable.  
> **username_1**: thanks. Another reason I asked was I also had trouble understanding that restriction and how the limit w.r.t. $n$ still makes sense, but I see now.  

---

## 1 answers

### Answer by username_2 on 2018-08-23. Score: 12 | Accepted answer

If the family function $f(x,n)=f\_n(x)$ is computable then these are exactly the $\Delta^0\_2$ functions, or equivalently, the functions that are Turing reducible to the halting set $0'$, which are very well studied within [computability-theory](/questions/tagged/computability-theory "show questions tagged 'computability-theory'").

There are also other, not equivalent, notions of almost computable that go by names such as generically computable and coarsely computable, see e.g.
Jockusch et al.: [Asymptotic Density and the Theory of Computability: A partial survey](https://arxiv.org/abs/1610.06504).


---

