Mixing
Is there a useful notion of being “approximately computableâ€Â
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
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_ntoinfty 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.
reference-request computability
asked Aug 23 at 3:11
Stella Biderman
580212
add a comment |Â
up vote
5
down vote
favorite
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_ntoinfty 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.
reference-request computability
asked Aug 23 at 3:11
Stella Biderman
580212
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$...
– usul
Aug 24 at 14:28
@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
Aug 25 at 19:08
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
Aug 25 at 23:31
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
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_ntoinfty 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.
reference-request computability
asked Aug 23 at 3:11
Stella Biderman
580212
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_ntoinfty 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.
reference-request computability
asked Aug 23 at 3:11
Stella Biderman
580212
edited Aug 29 at 13:22
asked Aug 23 at 3:11
Stella Biderman
580212
asked Aug 23 at 3:11
Stella Biderman
580212
asked Aug 23 at 3:11
Stella Biderman
580212
580212
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$...
– usul
Aug 24 at 14:28
@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
Aug 25 at 19:08
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
Aug 25 at 23:31
add a comment |Â
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$...
– usul
Aug 24 at 14:28
@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
Aug 25 at 19:08
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
Aug 25 at 23:31
1
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$...
– usul
Aug 24 at 14:28
"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
Aug 24 at 14:28
@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
Aug 25 at 19:08
@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
Aug 25 at 19:08
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
Aug 25 at 23:31
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
Aug 25 at 23:31
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
10
down vote
accepted
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.
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.
answered Aug 23 at 3:22
Bjørn Kjos-Hanssen♦
2,9921630
2
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?
– Stella Biderman
Aug 23 at 3:54
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
10
down vote
accepted
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.
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.
answered Aug 23 at 3:22
Bjørn Kjos-Hanssen♦
2,9921630
2
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?
– Stella Biderman
Aug 23 at 3:54
add a comment |Â
up vote
10
down vote
accepted
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.
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.
answered Aug 23 at 3:22
Bjørn Kjos-Hanssen♦
2,9921630
2
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?
– Stella Biderman
Aug 23 at 3:54
add a comment |Â
up vote
10
down vote
accepted
up vote
10
down vote
accepted
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.
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.
answered Aug 23 at 3:22
Bjørn Kjos-Hanssen♦
2,9921630
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.
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.
answered Aug 23 at 3:22
Bjørn Kjos-Hanssen♦
2,9921630
edited Aug 23 at 5:27
answered Aug 23 at 3:22
Bjørn Kjos-Hanssen♦
2,9921630
answered Aug 23 at 3:22
Bjørn Kjos-Hanssen♦
2,9921630
answered Aug 23 at 3:22
Bjørn Kjos-Hanssen♦
2,9921630
2,9921630
2
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?
– Stella Biderman
Aug 23 at 3:54
add a comment |Â
2
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?
– Stella Biderman
Aug 23 at 3:54
2
2
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?
– Stella Biderman
Aug 23 at 3:54
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?
– Stella Biderman
Aug 23 at 3:54
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcstheory.stackexchange.com%2fquestions%2f41424%2fis-there-a-useful-notion-of-being-approximately-computable%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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$...
– usul
Aug 24 at 14:28
@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
Aug 25 at 19:08
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
Aug 25 at 23:31