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.

Improve this question
$\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$
    – Stella Biderman
    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

Reset to default
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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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