Mixing
Equipping a set with an abstract notion of computability
up vote
1
down vote
favorite
I'm curious what the right abstraction is for equipping an arbitrary set with "something kind of like computability".
Topologies don't seem to fit because the complement of an open set is not open in general.
Sigma algebras don't seem to fit because computable functions on real numbers can't "zero in" on a particular real under our intuitive notion of computability. We can construct narrower and narrower sets containing the real in question, but can't isolate the real itself.
Most of the definitions of computability that I've seen before involve defining a subset of $mathbb{N} to mathbb{N}$ or $(mathbb{N})^n to mathbb{N}$. One constructs Turing Machines and describes how to feed data in and read it back out, or considers an initial pool of functions and closes them under certain operators.
There are a couple of properties that apply to functions in $mathbb{N} to mathbb{N}$ that are vaguely computability-like.
- computability itself: corresponding to an always-halting Turing Machine / decider.
- computable in polynomial time.
- capable of being expressed in a particular total functional programming language.
Each of these properties, even though they apply to maps from $mathbb{N}$ to itself, readily give us a notion of which subsets of $mathbb{N}$ are computable, namely the preimages of $0_{mathbb{N}}$ in any of the maps.
However, for certain things like the real numbers $mathbb{R}$, I can think of two obvious ways to talk about computability, i.e. two candidates for $(mathbb{R}, sigma)$ .
1) Restrict our attention to the computable reals. Each of the sets in our collection of subsets $sigma$ is a subset of the computable reals. Not every subset of the set of computable reals is in $sigma$, however.
2) Consider "computably distinguishable" reals. Restrict our attention to the interval $[0,1]$, i.e. interpret infinite bitstrings as a real number on the unit interval. As our "basis" of sorts, consider numbers starting with the same finite sequence of 0s and 1s . Consider all finite sequences of finite bistrings. Associate each bitstring with the interval in $[0,1]$ that it corresponds to. By taking reciprocals and using negation, we can map portions of $mathbb{R}$ back to $[0,1]$ . We then say that our computable subsets in $mathbb{R}$ have to be computable in $[0,1]$ when $lambda x . -x$ or $lambda x . 1/x$ is applied and the result is intersected with $[0,1]$
Is there a kind of additional structure that we can endow a set with to "fix" our notion of computability up front?
soft-question computability
asked 2 days ago
Gregory Nisbet
334111
add a comment |
up vote
1
down vote
favorite
I'm curious what the right abstraction is for equipping an arbitrary set with "something kind of like computability".
Topologies don't seem to fit because the complement of an open set is not open in general.
Sigma algebras don't seem to fit because computable functions on real numbers can't "zero in" on a particular real under our intuitive notion of computability. We can construct narrower and narrower sets containing the real in question, but can't isolate the real itself.
Most of the definitions of computability that I've seen before involve defining a subset of $mathbb{N} to mathbb{N}$ or $(mathbb{N})^n to mathbb{N}$. One constructs Turing Machines and describes how to feed data in and read it back out, or considers an initial pool of functions and closes them under certain operators.
There are a couple of properties that apply to functions in $mathbb{N} to mathbb{N}$ that are vaguely computability-like.
- computability itself: corresponding to an always-halting Turing Machine / decider.
- computable in polynomial time.
- capable of being expressed in a particular total functional programming language.
Each of these properties, even though they apply to maps from $mathbb{N}$ to itself, readily give us a notion of which subsets of $mathbb{N}$ are computable, namely the preimages of $0_{mathbb{N}}$ in any of the maps.
However, for certain things like the real numbers $mathbb{R}$, I can think of two obvious ways to talk about computability, i.e. two candidates for $(mathbb{R}, sigma)$ .
1) Restrict our attention to the computable reals. Each of the sets in our collection of subsets $sigma$ is a subset of the computable reals. Not every subset of the set of computable reals is in $sigma$, however.
2) Consider "computably distinguishable" reals. Restrict our attention to the interval $[0,1]$, i.e. interpret infinite bitstrings as a real number on the unit interval. As our "basis" of sorts, consider numbers starting with the same finite sequence of 0s and 1s . Consider all finite sequences of finite bistrings. Associate each bitstring with the interval in $[0,1]$ that it corresponds to. By taking reciprocals and using negation, we can map portions of $mathbb{R}$ back to $[0,1]$ . We then say that our computable subsets in $mathbb{R}$ have to be computable in $[0,1]$ when $lambda x . -x$ or $lambda x . 1/x$ is applied and the result is intersected with $[0,1]$
Is there a kind of additional structure that we can endow a set with to "fix" our notion of computability up front?
soft-question computability
asked 2 days ago
Gregory Nisbet
334111
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I'm curious what the right abstraction is for equipping an arbitrary set with "something kind of like computability".
Topologies don't seem to fit because the complement of an open set is not open in general.
Sigma algebras don't seem to fit because computable functions on real numbers can't "zero in" on a particular real under our intuitive notion of computability. We can construct narrower and narrower sets containing the real in question, but can't isolate the real itself.
Most of the definitions of computability that I've seen before involve defining a subset of $mathbb{N} to mathbb{N}$ or $(mathbb{N})^n to mathbb{N}$. One constructs Turing Machines and describes how to feed data in and read it back out, or considers an initial pool of functions and closes them under certain operators.
There are a couple of properties that apply to functions in $mathbb{N} to mathbb{N}$ that are vaguely computability-like.
- computability itself: corresponding to an always-halting Turing Machine / decider.
- computable in polynomial time.
- capable of being expressed in a particular total functional programming language.
Each of these properties, even though they apply to maps from $mathbb{N}$ to itself, readily give us a notion of which subsets of $mathbb{N}$ are computable, namely the preimages of $0_{mathbb{N}}$ in any of the maps.
However, for certain things like the real numbers $mathbb{R}$, I can think of two obvious ways to talk about computability, i.e. two candidates for $(mathbb{R}, sigma)$ .
1) Restrict our attention to the computable reals. Each of the sets in our collection of subsets $sigma$ is a subset of the computable reals. Not every subset of the set of computable reals is in $sigma$, however.
2) Consider "computably distinguishable" reals. Restrict our attention to the interval $[0,1]$, i.e. interpret infinite bitstrings as a real number on the unit interval. As our "basis" of sorts, consider numbers starting with the same finite sequence of 0s and 1s . Consider all finite sequences of finite bistrings. Associate each bitstring with the interval in $[0,1]$ that it corresponds to. By taking reciprocals and using negation, we can map portions of $mathbb{R}$ back to $[0,1]$ . We then say that our computable subsets in $mathbb{R}$ have to be computable in $[0,1]$ when $lambda x . -x$ or $lambda x . 1/x$ is applied and the result is intersected with $[0,1]$
Is there a kind of additional structure that we can endow a set with to "fix" our notion of computability up front?
soft-question computability
asked 2 days ago
Gregory Nisbet
334111
I'm curious what the right abstraction is for equipping an arbitrary set with "something kind of like computability".
Topologies don't seem to fit because the complement of an open set is not open in general.
Sigma algebras don't seem to fit because computable functions on real numbers can't "zero in" on a particular real under our intuitive notion of computability. We can construct narrower and narrower sets containing the real in question, but can't isolate the real itself.
Most of the definitions of computability that I've seen before involve defining a subset of $mathbb{N} to mathbb{N}$ or $(mathbb{N})^n to mathbb{N}$. One constructs Turing Machines and describes how to feed data in and read it back out, or considers an initial pool of functions and closes them under certain operators.
There are a couple of properties that apply to functions in $mathbb{N} to mathbb{N}$ that are vaguely computability-like.
- computability itself: corresponding to an always-halting Turing Machine / decider.
- computable in polynomial time.
- capable of being expressed in a particular total functional programming language.
Each of these properties, even though they apply to maps from $mathbb{N}$ to itself, readily give us a notion of which subsets of $mathbb{N}$ are computable, namely the preimages of $0_{mathbb{N}}$ in any of the maps.
However, for certain things like the real numbers $mathbb{R}$, I can think of two obvious ways to talk about computability, i.e. two candidates for $(mathbb{R}, sigma)$ .
1) Restrict our attention to the computable reals. Each of the sets in our collection of subsets $sigma$ is a subset of the computable reals. Not every subset of the set of computable reals is in $sigma$, however.
2) Consider "computably distinguishable" reals. Restrict our attention to the interval $[0,1]$, i.e. interpret infinite bitstrings as a real number on the unit interval. As our "basis" of sorts, consider numbers starting with the same finite sequence of 0s and 1s . Consider all finite sequences of finite bistrings. Associate each bitstring with the interval in $[0,1]$ that it corresponds to. By taking reciprocals and using negation, we can map portions of $mathbb{R}$ back to $[0,1]$ . We then say that our computable subsets in $mathbb{R}$ have to be computable in $[0,1]$ when $lambda x . -x$ or $lambda x . 1/x$ is applied and the result is intersected with $[0,1]$
Is there a kind of additional structure that we can endow a set with to "fix" our notion of computability up front?
soft-question computability
soft-question computability
asked 2 days ago
Gregory Nisbet
334111
asked 2 days ago
Gregory Nisbet
334111
asked 2 days ago
Gregory Nisbet
334111
asked 2 days ago
Gregory Nisbet
334111
asked 2 days ago
Gregory Nisbet
334111
334111
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
The Blum–Shub–Smale machine is a model of computation intended to describe computations over the real numbers. See the original paper [1], but there is now a huge literature on this model.
[1] Lenore Blum, Mike Shub, and Steve Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.) 21, Number 1 (1989), 1-46.
answered 2 days ago
J.-E. Pin
18.1k21754
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
The Blum–Shub–Smale machine is a model of computation intended to describe computations over the real numbers. See the original paper [1], but there is now a huge literature on this model.
[1] Lenore Blum, Mike Shub, and Steve Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.) 21, Number 1 (1989), 1-46.
answered 2 days ago
J.-E. Pin
18.1k21754
add a comment |
up vote
1
down vote
The Blum–Shub–Smale machine is a model of computation intended to describe computations over the real numbers. See the original paper [1], but there is now a huge literature on this model.
[1] Lenore Blum, Mike Shub, and Steve Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.) 21, Number 1 (1989), 1-46.
answered 2 days ago
J.-E. Pin
18.1k21754
add a comment |
up vote
1
down vote
up vote
1
down vote
The Blum–Shub–Smale machine is a model of computation intended to describe computations over the real numbers. See the original paper [1], but there is now a huge literature on this model.
[1] Lenore Blum, Mike Shub, and Steve Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.) 21, Number 1 (1989), 1-46.
answered 2 days ago
J.-E. Pin
18.1k21754
The Blum–Shub–Smale machine is a model of computation intended to describe computations over the real numbers. See the original paper [1], but there is now a huge literature on this model.
[1] Lenore Blum, Mike Shub, and Steve Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.) 21, Number 1 (1989), 1-46.
answered 2 days ago
J.-E. Pin
18.1k21754
answered 2 days ago
J.-E. Pin
18.1k21754
answered 2 days ago
J.-E. Pin
18.1k21754
answered 2 days ago
J.-E. Pin
18.1k21754
18.1k21754
add a comment |
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3005464%2fequipping-a-set-with-an-abstract-notion-of-computability%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
