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.

  • 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 '18 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$ – Stella Biderman Aug 25 '18 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 '18 at 23:31

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.

  • 2
    $\begingroup$ Thank you for the reply! I had meant to conjecture that my definition was equivalent to $\Delta^0_2$, but I seem to have cut that line at some point. My question isn’t about this definition in particular though, it’s about conceptions of “approximately computable” (with this as a proposed illustrative definition). Is $\Delta^0_2$ considered to correspond to the set of problems that are approximately computable? $\endgroup$ – Stella Biderman Aug 23 '18 at 3:54

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.