5
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ "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$... $\endgroup$
    – usul
    Aug 24, 2018 at 14:28
  • $\begingroup$ @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. $\endgroup$ Aug 25, 2018 at 19:08
  • $\begingroup$ 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. $\endgroup$
    – usul
    Aug 25, 2018 at 23:31

1 Answer 1

12
$\begingroup$

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 .

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.

$\endgroup$
0

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .