What is the difference between computably generated and computable?
$begingroup$
I was reading from these logic notes and on page 102 they define the notion of computably generated and in particular they seem to contrast it with computable functions (which they have a specific definition for that which we show later on the book that is the same as his version of the Church-Turning thesis, so I am ok with just using that to mean computable). He defines computably generated as:
which he remarks as not being exactly the same as computable. Can the difference be explained to me? What is the difference? Also, why does it matter to make the distinction. I assume that is the most important thing. I'd like understand why I need to understand the difference in the first place.
My thoughts:
I don’t quite understand or appreciate the difference between “computably generated” vs “computable”. I was comparing the definition especially comparing the definition given with ( exists x < y R(a,x) ) given on lemma 5.1.11. I notice that the main difference is the boundedness of the “search”. I also know that the reason computable functions end up being computable is by the key role R3 plays $$mu x( G(a,x) = 0 )$$ I feel these things have to be connected. But I fail to see how...
More thoughts:
Recall what Computable set is. If we have a set of natural numbers $S subseteq mathbf N$ we say its computable if there exists an procedure that terminates in finite time that determines membership of $S$. i.e. computes the characteristic function $chi_S$ in finite time. Note that I am appealing to the definition that the Church-Turning thesis as the definition of computable (because those notes define a rigorous notion of computability that one can show is equivalent to the definition they provide for the Church-Turning thesis. Perhaps this doesn't hold formally for the real Church-Turning thesis but I am happy to assume it to be true).
Lets think about what computably generated or Recursively Enumerable means. Intuitively it means that in finite time we can characterize inclusion of every element of the relation $R$. So for any $a in R$ (or $R(a)$) we can "produce it" in finite time i.e.:
$$ a in R iff exists x Q(a,x) $$
So we can enumerate all the elements and for each element we can "produce it" in finite time (i.e. I just mean if $a in R$ then since $exists x Q(a,x)$ must mean that since $x$ actually exists then we eventually find it). To this point the definitions seem identical...we can determine inclusion in finite time...so what am I missing?
logic computability
asked Nov 30 '18 at 16:58
PinocchioPinocchio
1,91041854
$endgroup$
add a comment |
$begingroup$
I was reading from these logic notes and on page 102 they define the notion of computably generated and in particular they seem to contrast it with computable functions (which they have a specific definition for that which we show later on the book that is the same as his version of the Church-Turning thesis, so I am ok with just using that to mean computable). He defines computably generated as:
which he remarks as not being exactly the same as computable. Can the difference be explained to me? What is the difference? Also, why does it matter to make the distinction. I assume that is the most important thing. I'd like understand why I need to understand the difference in the first place.
My thoughts:
I don’t quite understand or appreciate the difference between “computably generated” vs “computable”. I was comparing the definition especially comparing the definition given with ( exists x < y R(a,x) ) given on lemma 5.1.11. I notice that the main difference is the boundedness of the “search”. I also know that the reason computable functions end up being computable is by the key role R3 plays $$mu x( G(a,x) = 0 )$$ I feel these things have to be connected. But I fail to see how...
More thoughts:
Recall what Computable set is. If we have a set of natural numbers $S subseteq mathbf N$ we say its computable if there exists an procedure that terminates in finite time that determines membership of $S$. i.e. computes the characteristic function $chi_S$ in finite time. Note that I am appealing to the definition that the Church-Turning thesis as the definition of computable (because those notes define a rigorous notion of computability that one can show is equivalent to the definition they provide for the Church-Turning thesis. Perhaps this doesn't hold formally for the real Church-Turning thesis but I am happy to assume it to be true).
Lets think about what computably generated or Recursively Enumerable means. Intuitively it means that in finite time we can characterize inclusion of every element of the relation $R$. So for any $a in R$ (or $R(a)$) we can "produce it" in finite time i.e.:
$$ a in R iff exists x Q(a,x) $$
So we can enumerate all the elements and for each element we can "produce it" in finite time (i.e. I just mean if $a in R$ then since $exists x Q(a,x)$ must mean that since $x$ actually exists then we eventually find it). To this point the definitions seem identical...we can determine inclusion in finite time...so what am I missing?
logic computability
asked Nov 30 '18 at 16:58
PinocchioPinocchio
1,91041854
$endgroup$
2
$begingroup$
The remark at the end says that there are computably generated relations (see later in the book) such that their complements are not computably generated. They will thus fail to be computable. Moreover, a relation is computable iff it and its complement are both computably generated.
$endgroup$
– Berci
Nov 30 '18 at 17:11
$begingroup$
now that I read back on the notes, I think I do know what computable function is but NOT on what computable set of L-sentences is, hence my Q: math.stackexchange.com/questions/3020934/…
$endgroup$
– Pinocchio
Dec 1 '18 at 3:08
$begingroup$
Recall that computable means you can determine membership AND non membership in finite time. Computably generated just means you can ONLY determine membership in finite time (but cannot get information about non membership in finite time).
$endgroup$
– Pinocchio
Dec 2 '18 at 2:01
$begingroup$
Im also having a hard time understanding why that was the chosen name...how does it enumerate or generate stuff?
$endgroup$
– Pinocchio
Dec 2 '18 at 22:01
add a comment |
$begingroup$
I was reading from these logic notes and on page 102 they define the notion of computably generated and in particular they seem to contrast it with computable functions (which they have a specific definition for that which we show later on the book that is the same as his version of the Church-Turning thesis, so I am ok with just using that to mean computable). He defines computably generated as:
which he remarks as not being exactly the same as computable. Can the difference be explained to me? What is the difference? Also, why does it matter to make the distinction. I assume that is the most important thing. I'd like understand why I need to understand the difference in the first place.
My thoughts:
I don’t quite understand or appreciate the difference between “computably generated” vs “computable”. I was comparing the definition especially comparing the definition given with ( exists x < y R(a,x) ) given on lemma 5.1.11. I notice that the main difference is the boundedness of the “search”. I also know that the reason computable functions end up being computable is by the key role R3 plays $$mu x( G(a,x) = 0 )$$ I feel these things have to be connected. But I fail to see how...
More thoughts:
Recall what Computable set is. If we have a set of natural numbers $S subseteq mathbf N$ we say its computable if there exists an procedure that terminates in finite time that determines membership of $S$. i.e. computes the characteristic function $chi_S$ in finite time. Note that I am appealing to the definition that the Church-Turning thesis as the definition of computable (because those notes define a rigorous notion of computability that one can show is equivalent to the definition they provide for the Church-Turning thesis. Perhaps this doesn't hold formally for the real Church-Turning thesis but I am happy to assume it to be true).
Lets think about what computably generated or Recursively Enumerable means. Intuitively it means that in finite time we can characterize inclusion of every element of the relation $R$. So for any $a in R$ (or $R(a)$) we can "produce it" in finite time i.e.:
$$ a in R iff exists x Q(a,x) $$
So we can enumerate all the elements and for each element we can "produce it" in finite time (i.e. I just mean if $a in R$ then since $exists x Q(a,x)$ must mean that since $x$ actually exists then we eventually find it). To this point the definitions seem identical...we can determine inclusion in finite time...so what am I missing?
logic computability
asked Nov 30 '18 at 16:58
PinocchioPinocchio
1,91041854
$endgroup$
I was reading from these logic notes and on page 102 they define the notion of computably generated and in particular they seem to contrast it with computable functions (which they have a specific definition for that which we show later on the book that is the same as his version of the Church-Turning thesis, so I am ok with just using that to mean computable). He defines computably generated as:
which he remarks as not being exactly the same as computable. Can the difference be explained to me? What is the difference? Also, why does it matter to make the distinction. I assume that is the most important thing. I'd like understand why I need to understand the difference in the first place.
My thoughts:
I don’t quite understand or appreciate the difference between “computably generated” vs “computable”. I was comparing the definition especially comparing the definition given with ( exists x < y R(a,x) ) given on lemma 5.1.11. I notice that the main difference is the boundedness of the “search”. I also know that the reason computable functions end up being computable is by the key role R3 plays $$mu x( G(a,x) = 0 )$$ I feel these things have to be connected. But I fail to see how...
More thoughts:
Recall what Computable set is. If we have a set of natural numbers $S subseteq mathbf N$ we say its computable if there exists an procedure that terminates in finite time that determines membership of $S$. i.e. computes the characteristic function $chi_S$ in finite time. Note that I am appealing to the definition that the Church-Turning thesis as the definition of computable (because those notes define a rigorous notion of computability that one can show is equivalent to the definition they provide for the Church-Turning thesis. Perhaps this doesn't hold formally for the real Church-Turning thesis but I am happy to assume it to be true).
Lets think about what computably generated or Recursively Enumerable means. Intuitively it means that in finite time we can characterize inclusion of every element of the relation $R$. So for any $a in R$ (or $R(a)$) we can "produce it" in finite time i.e.:
$$ a in R iff exists x Q(a,x) $$
So we can enumerate all the elements and for each element we can "produce it" in finite time (i.e. I just mean if $a in R$ then since $exists x Q(a,x)$ must mean that since $x$ actually exists then we eventually find it). To this point the definitions seem identical...we can determine inclusion in finite time...so what am I missing?
logic computability
logic computability
asked Nov 30 '18 at 16:58
PinocchioPinocchio
1,91041854
asked Nov 30 '18 at 16:58
PinocchioPinocchio
1,91041854
edited Dec 2 '18 at 2:00
Pinocchio
asked Nov 30 '18 at 16:58
PinocchioPinocchio
1,91041854
asked Nov 30 '18 at 16:58
PinocchioPinocchio
1,91041854
asked Nov 30 '18 at 16:58
PinocchioPinocchio
1,91041854
1,91041854
2
$begingroup$
The remark at the end says that there are computably generated relations (see later in the book) such that their complements are not computably generated. They will thus fail to be computable. Moreover, a relation is computable iff it and its complement are both computably generated.
$endgroup$
– Berci
Nov 30 '18 at 17:11
$begingroup$
now that I read back on the notes, I think I do know what computable function is but NOT on what computable set of L-sentences is, hence my Q: math.stackexchange.com/questions/3020934/…
$endgroup$
– Pinocchio
Dec 1 '18 at 3:08
$begingroup$
Recall that computable means you can determine membership AND non membership in finite time. Computably generated just means you can ONLY determine membership in finite time (but cannot get information about non membership in finite time).
$endgroup$
– Pinocchio
Dec 2 '18 at 2:01
$begingroup$
Im also having a hard time understanding why that was the chosen name...how does it enumerate or generate stuff?
$endgroup$
– Pinocchio
Dec 2 '18 at 22:01
add a comment |
2
$begingroup$
The remark at the end says that there are computably generated relations (see later in the book) such that their complements are not computably generated. They will thus fail to be computable. Moreover, a relation is computable iff it and its complement are both computably generated.
$endgroup$
– Berci
Nov 30 '18 at 17:11
$begingroup$
now that I read back on the notes, I think I do know what computable function is but NOT on what computable set of L-sentences is, hence my Q: math.stackexchange.com/questions/3020934/…
$endgroup$
– Pinocchio
Dec 1 '18 at 3:08
$begingroup$
Recall that computable means you can determine membership AND non membership in finite time. Computably generated just means you can ONLY determine membership in finite time (but cannot get information about non membership in finite time).
$endgroup$
– Pinocchio
Dec 2 '18 at 2:01
$begingroup$
Im also having a hard time understanding why that was the chosen name...how does it enumerate or generate stuff?
$endgroup$
– Pinocchio
Dec 2 '18 at 22:01
2
2
$begingroup$
The remark at the end says that there are computably generated relations (see later in the book) such that their complements are not computably generated. They will thus fail to be computable. Moreover, a relation is computable iff it and its complement are both computably generated.
$endgroup$
– Berci
Nov 30 '18 at 17:11
$begingroup$
The remark at the end says that there are computably generated relations (see later in the book) such that their complements are not computably generated. They will thus fail to be computable. Moreover, a relation is computable iff it and its complement are both computably generated.
$endgroup$
– Berci
Nov 30 '18 at 17:11
$begingroup$
now that I read back on the notes, I think I do know what computable function is but NOT on what computable set of L-sentences is, hence my Q: math.stackexchange.com/questions/3020934/…
$endgroup$
– Pinocchio
Dec 1 '18 at 3:08
$begingroup$
now that I read back on the notes, I think I do know what computable function is but NOT on what computable set of L-sentences is, hence my Q: math.stackexchange.com/questions/3020934/…
$endgroup$
– Pinocchio
Dec 1 '18 at 3:08
$begingroup$
Recall that computable means you can determine membership AND non membership in finite time. Computably generated just means you can ONLY determine membership in finite time (but cannot get information about non membership in finite time).
$endgroup$
– Pinocchio
Dec 2 '18 at 2:01
$begingroup$
Recall that computable means you can determine membership AND non membership in finite time. Computably generated just means you can ONLY determine membership in finite time (but cannot get information about non membership in finite time).
$endgroup$
– Pinocchio
Dec 2 '18 at 2:01
$begingroup$
Im also having a hard time understanding why that was the chosen name...how does it enumerate or generate stuff?
$endgroup$
– Pinocchio
Dec 2 '18 at 22:01
$begingroup$
Im also having a hard time understanding why that was the chosen name...how does it enumerate or generate stuff?
$endgroup$
– Pinocchio
Dec 2 '18 at 22:01
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
First of all, a comment on terminology: "recursively enumerable" and "computably enumerable" are the standard terms (and I'll use the latter here); moreover, I've never heard "computably generated" used before (although the meaning is clear).
I'll give informal, "Church's thesis style" arguments below; you should understand the intuitions behind the results before diving into the formal details (which are generally tedious if the motivation isn't clear). I'll also, for simplicity, focus on unary $R$ (and unary functions).
Finally, here's the first bit of actual intuition: we generally interpret "$exists x Q(a,x)$" as "$a$ enters $R$ at stage some stage," and in particular "$Q(a,b)$" as "$a$ enters $R$ at stage $b$" (or "by stage $b$"). Specifically, to tell whether $ain R$ we check:
Is $Q(a,0)$ true?
Is $Q(a, 1)$ true?
Is $Q(a,2)$ true?
...
Now to your question. Every computable relation is computably enumerable, but the converse is not true. The classic example is the Halting Problem, which has a few essentially equivalent definitions, the most transparent in my opinion being $$H={e: Phi_e(0)downarrow}.$$ Here "$Phi_e(0)downarrow$" means "the $e$th Turing machine on input $0$ halts."
You have already seen, I suspect, the proof that $H$ is not computable. However, it is computably enumerable! To tell whether $ein H$ we just run $Phi_e(0)$ and wait for it to halt - if it does halt, we put $ein H$. This is a computable process, and enumerates $H$. Note that it does not decide $H$: if $Phi_e(0)$ never halts, we don't necessarily figure that out at any particular moment. ("Well, it's been ten billion years and $Phi_e(0)$ hasn't halted yet ... but it might tomorrow!")
We can be a bit more precise about the relationship between "computably enumerable" and "computable." Specifically, we have (focusing on sets for simplicity):
A set $X$ is computable iff both $X$ and $overline{X}$ are computably enumerable.
(Here "$overline{X}$" denotes the complement of $X$.)
For the left-to-right direction, just note that all computable sets are computably enumerable, and the complement of a computable set is again computable.
For the right-to-left direction, suppose both $X$ and $overline{X}$ are computably enumerable. Then I can compute $X$ as follows: given $n$, I simply wait to see $n$ enter $X$ or $n$ enter $overline{X}$. Exactly one of these two things will happen (since $Xsqcupoverline{X}=mathbb{N}$), and I can tell which one does (since my enumerations are computable).
The relationship between computability and computable enumerability for functions is a bit more subtle. Specifically, we have (focusing on unary functions for simplicity):
Suppose $f:mathbb{N}rightarrowmathbb{N}$ is total. Then $f$ is computable iff $f$ is computably enumerable.
(Here, I'm conflating a function with its graph: "$f$ is computably enumerable" means "${langle a, brangle: f(a)=b}$ is computably enumerable.")
The left-to-right direction is again clear: $f$ is computable if the graph of $f$ is computable (by definition), and if the graph of $f$ is computable then it's certainly computably enumerable.
The right-to-left direction is the interesting one. Suppose $Graph_f={langle a,brangle: f(a)=b}$ is computably enumerable and I want to figure out what $f(n)$ is. What I'll do is "dovetail" - run a bunch of computations in parallel until one of them halts (basically, a more complicated version of what I did in the proof of the previous claim). Specifically:
See if $langle n, 0rangle$ enters $Graph_f$ by time $1$. If so, $f(n)=0$. If not, ...
See if $langle n, 1rangle$ enters $Graph_f$ by time $2$. If so, $f(n)=1$. If not, ...
See if $langle n, 0rangle$ enters $Graph_f$ by time $2$. If so, $f(n)=0$. If not, ...
See if $langle n, 2rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=2$. If not, ...
See if $langle n, 1rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=1$. If not, ...
See if $langle n, 0rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=0$. If not, ...
...
After finitely much time, eventually we'll see $langle n,krangle$ enter $Graph_f$ for some $k$. At that point, we stop and say, "$f(n)=k$."
We've used here two properties of $f$ (beyond the computable enumerability of its graph): that it is single-valued (once we know $langle 3,17ranglein Graph_f$, we know that $langle 3, 42ranglenotin Graph_f$) and that it is defined on all of $mathbb{N}$ (if $f(12)$ weren't defined, the procedure above would never finish with $n=12$ and so would never tell us conclusively that $langle 12, 451ranglenotin Graph_f$). These turn out to be essential:
There is a function with computably enumerable domain whose graph is computably enumerable but not computable, and there is a binary relation with domain $mathbb{N}$ (= for each $a$ there is at least one $b$ with $langle a,brangle$ in the relation) which is computably enumerable but not computable.
Proving these two claims is a good exercise.
answered Nov 30 '18 at 17:08
Noah SchweberNoah Schweber
124k10150287
$endgroup$
$begingroup$
I think what is confusing me is, what does it mean for a set to be computable vs computably generated?
$endgroup$
– Pinocchio
Dec 1 '18 at 2:52
1
$begingroup$
@Pinocchio Again, the idea is that a set is computably enumerable iff we can computably get positive information about it (if $nin A$ then we eventually realize $nin A$) but don't necessarily have negative information about it. In particular, the example of $H$ above should be helpful: it's easy to tell when something is in $H$ - we just see the corresponding program halt eventually - but it's very hard to tell when something isn't in $H$.
$endgroup$
– Noah Schweber
Dec 1 '18 at 3:21
$begingroup$
Re: that specific example, do you understand why $H$ is computably enumerable but not computable? (If not, which part is unclear.)
$endgroup$
– Noah Schweber
Dec 1 '18 at 3:22
$begingroup$
fantastic! Your second comment was the most helpful. Now I see what the difference between the two is. I didn't realize $a not in R iff forall x neg Q(a,x)$. So that "for all" quantifier is what makes it "uncomputable" (or at least there is no reason to believe that in finite time we can determine $a in R$ so its characteristic function isn't guaranteed to terminate in finite time). It seems intuitively plausible that there is no mechanical way always transform a forall statement into an exists...if there was then we wouldn't have this problem in the first place. Thanks!
$endgroup$
– Pinocchio
Dec 2 '18 at 1:56
1
$begingroup$
@Pinocchio That's it exactly - glad I could help!
$endgroup$
– Noah Schweber
Dec 2 '18 at 3:02
|
show 3 more comments
$begingroup$
I think I want to emphasize what made it click to me. Computable means that one can recognize if an element is in the set and if its not in finite time. So the indicator function or characteristic function is computable (which means that in finite time we always get a positive or negative answer). While computably generated/recursively enumerable is that membership is computable. So given an element in $R$ one can find a "certificate" that it indeed is in $R$ (is the way I interpret it from the definition:
$$ a in R iff exists x Q(a,x) $$
so we can get positive information about $a$ if it happens to be in $R$ (note we assume $Q$ is computable, so every time we plug in $(a,x)$ we get an answer in finite time). Note that if $a in R$ (which we don't know a priori usually) the search for $x$ shall terminate, say by checking all $x$'s until $Q(a,x)$ returns true.
But if its not then we might not find that out ever because notice the negation:
$$ a not in R iff forall x neg Q(a,x) $$
which means you might have to potentially need to check all $x$'s. There probably isn't a standard way to convert for all statements into existence statements so this search might never terminate. Which is the key. If $a$ happens to not be in $R$ then the above might never terminate.
So we can only get positive info about $R$.
Note if both are computably enumerable, then we do get $R$ is computable, since we can find a certificate for both membership and not in finite time.
answered Dec 2 '18 at 18:18
PinocchioPinocchio
1,91041854
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f3020322%2fwhat-is-the-difference-between-computably-generated-and-computable%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
First of all, a comment on terminology: "recursively enumerable" and "computably enumerable" are the standard terms (and I'll use the latter here); moreover, I've never heard "computably generated" used before (although the meaning is clear).
I'll give informal, "Church's thesis style" arguments below; you should understand the intuitions behind the results before diving into the formal details (which are generally tedious if the motivation isn't clear). I'll also, for simplicity, focus on unary $R$ (and unary functions).
Finally, here's the first bit of actual intuition: we generally interpret "$exists x Q(a,x)$" as "$a$ enters $R$ at stage some stage," and in particular "$Q(a,b)$" as "$a$ enters $R$ at stage $b$" (or "by stage $b$"). Specifically, to tell whether $ain R$ we check:
Is $Q(a,0)$ true?
Is $Q(a, 1)$ true?
Is $Q(a,2)$ true?
...
Now to your question. Every computable relation is computably enumerable, but the converse is not true. The classic example is the Halting Problem, which has a few essentially equivalent definitions, the most transparent in my opinion being $$H={e: Phi_e(0)downarrow}.$$ Here "$Phi_e(0)downarrow$" means "the $e$th Turing machine on input $0$ halts."
You have already seen, I suspect, the proof that $H$ is not computable. However, it is computably enumerable! To tell whether $ein H$ we just run $Phi_e(0)$ and wait for it to halt - if it does halt, we put $ein H$. This is a computable process, and enumerates $H$. Note that it does not decide $H$: if $Phi_e(0)$ never halts, we don't necessarily figure that out at any particular moment. ("Well, it's been ten billion years and $Phi_e(0)$ hasn't halted yet ... but it might tomorrow!")
We can be a bit more precise about the relationship between "computably enumerable" and "computable." Specifically, we have (focusing on sets for simplicity):
A set $X$ is computable iff both $X$ and $overline{X}$ are computably enumerable.
(Here "$overline{X}$" denotes the complement of $X$.)
For the left-to-right direction, just note that all computable sets are computably enumerable, and the complement of a computable set is again computable.
For the right-to-left direction, suppose both $X$ and $overline{X}$ are computably enumerable. Then I can compute $X$ as follows: given $n$, I simply wait to see $n$ enter $X$ or $n$ enter $overline{X}$. Exactly one of these two things will happen (since $Xsqcupoverline{X}=mathbb{N}$), and I can tell which one does (since my enumerations are computable).
The relationship between computability and computable enumerability for functions is a bit more subtle. Specifically, we have (focusing on unary functions for simplicity):
Suppose $f:mathbb{N}rightarrowmathbb{N}$ is total. Then $f$ is computable iff $f$ is computably enumerable.
(Here, I'm conflating a function with its graph: "$f$ is computably enumerable" means "${langle a, brangle: f(a)=b}$ is computably enumerable.")
The left-to-right direction is again clear: $f$ is computable if the graph of $f$ is computable (by definition), and if the graph of $f$ is computable then it's certainly computably enumerable.
The right-to-left direction is the interesting one. Suppose $Graph_f={langle a,brangle: f(a)=b}$ is computably enumerable and I want to figure out what $f(n)$ is. What I'll do is "dovetail" - run a bunch of computations in parallel until one of them halts (basically, a more complicated version of what I did in the proof of the previous claim). Specifically:
See if $langle n, 0rangle$ enters $Graph_f$ by time $1$. If so, $f(n)=0$. If not, ...
See if $langle n, 1rangle$ enters $Graph_f$ by time $2$. If so, $f(n)=1$. If not, ...
See if $langle n, 0rangle$ enters $Graph_f$ by time $2$. If so, $f(n)=0$. If not, ...
See if $langle n, 2rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=2$. If not, ...
See if $langle n, 1rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=1$. If not, ...
See if $langle n, 0rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=0$. If not, ...
...
After finitely much time, eventually we'll see $langle n,krangle$ enter $Graph_f$ for some $k$. At that point, we stop and say, "$f(n)=k$."
We've used here two properties of $f$ (beyond the computable enumerability of its graph): that it is single-valued (once we know $langle 3,17ranglein Graph_f$, we know that $langle 3, 42ranglenotin Graph_f$) and that it is defined on all of $mathbb{N}$ (if $f(12)$ weren't defined, the procedure above would never finish with $n=12$ and so would never tell us conclusively that $langle 12, 451ranglenotin Graph_f$). These turn out to be essential:
There is a function with computably enumerable domain whose graph is computably enumerable but not computable, and there is a binary relation with domain $mathbb{N}$ (= for each $a$ there is at least one $b$ with $langle a,brangle$ in the relation) which is computably enumerable but not computable.
Proving these two claims is a good exercise.
answered Nov 30 '18 at 17:08
Noah SchweberNoah Schweber
124k10150287
$endgroup$
$begingroup$
I think what is confusing me is, what does it mean for a set to be computable vs computably generated?
$endgroup$
– Pinocchio
Dec 1 '18 at 2:52
1
$begingroup$
@Pinocchio Again, the idea is that a set is computably enumerable iff we can computably get positive information about it (if $nin A$ then we eventually realize $nin A$) but don't necessarily have negative information about it. In particular, the example of $H$ above should be helpful: it's easy to tell when something is in $H$ - we just see the corresponding program halt eventually - but it's very hard to tell when something isn't in $H$.
$endgroup$
– Noah Schweber
Dec 1 '18 at 3:21
$begingroup$
Re: that specific example, do you understand why $H$ is computably enumerable but not computable? (If not, which part is unclear.)
$endgroup$
– Noah Schweber
Dec 1 '18 at 3:22
$begingroup$
fantastic! Your second comment was the most helpful. Now I see what the difference between the two is. I didn't realize $a not in R iff forall x neg Q(a,x)$. So that "for all" quantifier is what makes it "uncomputable" (or at least there is no reason to believe that in finite time we can determine $a in R$ so its characteristic function isn't guaranteed to terminate in finite time). It seems intuitively plausible that there is no mechanical way always transform a forall statement into an exists...if there was then we wouldn't have this problem in the first place. Thanks!
$endgroup$
– Pinocchio
Dec 2 '18 at 1:56
1
$begingroup$
@Pinocchio That's it exactly - glad I could help!
$endgroup$
– Noah Schweber
Dec 2 '18 at 3:02
|
show 3 more comments
$begingroup$
First of all, a comment on terminology: "recursively enumerable" and "computably enumerable" are the standard terms (and I'll use the latter here); moreover, I've never heard "computably generated" used before (although the meaning is clear).
I'll give informal, "Church's thesis style" arguments below; you should understand the intuitions behind the results before diving into the formal details (which are generally tedious if the motivation isn't clear). I'll also, for simplicity, focus on unary $R$ (and unary functions).
Finally, here's the first bit of actual intuition: we generally interpret "$exists x Q(a,x)$" as "$a$ enters $R$ at stage some stage," and in particular "$Q(a,b)$" as "$a$ enters $R$ at stage $b$" (or "by stage $b$"). Specifically, to tell whether $ain R$ we check:
Is $Q(a,0)$ true?
Is $Q(a, 1)$ true?
Is $Q(a,2)$ true?
...
Now to your question. Every computable relation is computably enumerable, but the converse is not true. The classic example is the Halting Problem, which has a few essentially equivalent definitions, the most transparent in my opinion being $$H={e: Phi_e(0)downarrow}.$$ Here "$Phi_e(0)downarrow$" means "the $e$th Turing machine on input $0$ halts."
You have already seen, I suspect, the proof that $H$ is not computable. However, it is computably enumerable! To tell whether $ein H$ we just run $Phi_e(0)$ and wait for it to halt - if it does halt, we put $ein H$. This is a computable process, and enumerates $H$. Note that it does not decide $H$: if $Phi_e(0)$ never halts, we don't necessarily figure that out at any particular moment. ("Well, it's been ten billion years and $Phi_e(0)$ hasn't halted yet ... but it might tomorrow!")
We can be a bit more precise about the relationship between "computably enumerable" and "computable." Specifically, we have (focusing on sets for simplicity):
A set $X$ is computable iff both $X$ and $overline{X}$ are computably enumerable.
(Here "$overline{X}$" denotes the complement of $X$.)
For the left-to-right direction, just note that all computable sets are computably enumerable, and the complement of a computable set is again computable.
For the right-to-left direction, suppose both $X$ and $overline{X}$ are computably enumerable. Then I can compute $X$ as follows: given $n$, I simply wait to see $n$ enter $X$ or $n$ enter $overline{X}$. Exactly one of these two things will happen (since $Xsqcupoverline{X}=mathbb{N}$), and I can tell which one does (since my enumerations are computable).
The relationship between computability and computable enumerability for functions is a bit more subtle. Specifically, we have (focusing on unary functions for simplicity):
Suppose $f:mathbb{N}rightarrowmathbb{N}$ is total. Then $f$ is computable iff $f$ is computably enumerable.
(Here, I'm conflating a function with its graph: "$f$ is computably enumerable" means "${langle a, brangle: f(a)=b}$ is computably enumerable.")
The left-to-right direction is again clear: $f$ is computable if the graph of $f$ is computable (by definition), and if the graph of $f$ is computable then it's certainly computably enumerable.
The right-to-left direction is the interesting one. Suppose $Graph_f={langle a,brangle: f(a)=b}$ is computably enumerable and I want to figure out what $f(n)$ is. What I'll do is "dovetail" - run a bunch of computations in parallel until one of them halts (basically, a more complicated version of what I did in the proof of the previous claim). Specifically:
See if $langle n, 0rangle$ enters $Graph_f$ by time $1$. If so, $f(n)=0$. If not, ...
See if $langle n, 1rangle$ enters $Graph_f$ by time $2$. If so, $f(n)=1$. If not, ...
See if $langle n, 0rangle$ enters $Graph_f$ by time $2$. If so, $f(n)=0$. If not, ...
See if $langle n, 2rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=2$. If not, ...
See if $langle n, 1rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=1$. If not, ...
See if $langle n, 0rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=0$. If not, ...
...
After finitely much time, eventually we'll see $langle n,krangle$ enter $Graph_f$ for some $k$. At that point, we stop and say, "$f(n)=k$."
We've used here two properties of $f$ (beyond the computable enumerability of its graph): that it is single-valued (once we know $langle 3,17ranglein Graph_f$, we know that $langle 3, 42ranglenotin Graph_f$) and that it is defined on all of $mathbb{N}$ (if $f(12)$ weren't defined, the procedure above would never finish with $n=12$ and so would never tell us conclusively that $langle 12, 451ranglenotin Graph_f$). These turn out to be essential:
There is a function with computably enumerable domain whose graph is computably enumerable but not computable, and there is a binary relation with domain $mathbb{N}$ (= for each $a$ there is at least one $b$ with $langle a,brangle$ in the relation) which is computably enumerable but not computable.
Proving these two claims is a good exercise.
answered Nov 30 '18 at 17:08
Noah SchweberNoah Schweber
124k10150287
$endgroup$
$begingroup$
I think what is confusing me is, what does it mean for a set to be computable vs computably generated?
$endgroup$
– Pinocchio
Dec 1 '18 at 2:52
1
$begingroup$
@Pinocchio Again, the idea is that a set is computably enumerable iff we can computably get positive information about it (if $nin A$ then we eventually realize $nin A$) but don't necessarily have negative information about it. In particular, the example of $H$ above should be helpful: it's easy to tell when something is in $H$ - we just see the corresponding program halt eventually - but it's very hard to tell when something isn't in $H$.
$endgroup$
– Noah Schweber
Dec 1 '18 at 3:21
$begingroup$
Re: that specific example, do you understand why $H$ is computably enumerable but not computable? (If not, which part is unclear.)
$endgroup$
– Noah Schweber
Dec 1 '18 at 3:22
$begingroup$
fantastic! Your second comment was the most helpful. Now I see what the difference between the two is. I didn't realize $a not in R iff forall x neg Q(a,x)$. So that "for all" quantifier is what makes it "uncomputable" (or at least there is no reason to believe that in finite time we can determine $a in R$ so its characteristic function isn't guaranteed to terminate in finite time). It seems intuitively plausible that there is no mechanical way always transform a forall statement into an exists...if there was then we wouldn't have this problem in the first place. Thanks!
$endgroup$
– Pinocchio
Dec 2 '18 at 1:56
1
$begingroup$
@Pinocchio That's it exactly - glad I could help!
$endgroup$
– Noah Schweber
Dec 2 '18 at 3:02
|
show 3 more comments
$begingroup$
First of all, a comment on terminology: "recursively enumerable" and "computably enumerable" are the standard terms (and I'll use the latter here); moreover, I've never heard "computably generated" used before (although the meaning is clear).
I'll give informal, "Church's thesis style" arguments below; you should understand the intuitions behind the results before diving into the formal details (which are generally tedious if the motivation isn't clear). I'll also, for simplicity, focus on unary $R$ (and unary functions).
Finally, here's the first bit of actual intuition: we generally interpret "$exists x Q(a,x)$" as "$a$ enters $R$ at stage some stage," and in particular "$Q(a,b)$" as "$a$ enters $R$ at stage $b$" (or "by stage $b$"). Specifically, to tell whether $ain R$ we check:
Is $Q(a,0)$ true?
Is $Q(a, 1)$ true?
Is $Q(a,2)$ true?
...
Now to your question. Every computable relation is computably enumerable, but the converse is not true. The classic example is the Halting Problem, which has a few essentially equivalent definitions, the most transparent in my opinion being $$H={e: Phi_e(0)downarrow}.$$ Here "$Phi_e(0)downarrow$" means "the $e$th Turing machine on input $0$ halts."
You have already seen, I suspect, the proof that $H$ is not computable. However, it is computably enumerable! To tell whether $ein H$ we just run $Phi_e(0)$ and wait for it to halt - if it does halt, we put $ein H$. This is a computable process, and enumerates $H$. Note that it does not decide $H$: if $Phi_e(0)$ never halts, we don't necessarily figure that out at any particular moment. ("Well, it's been ten billion years and $Phi_e(0)$ hasn't halted yet ... but it might tomorrow!")
We can be a bit more precise about the relationship between "computably enumerable" and "computable." Specifically, we have (focusing on sets for simplicity):
A set $X$ is computable iff both $X$ and $overline{X}$ are computably enumerable.
(Here "$overline{X}$" denotes the complement of $X$.)
For the left-to-right direction, just note that all computable sets are computably enumerable, and the complement of a computable set is again computable.
For the right-to-left direction, suppose both $X$ and $overline{X}$ are computably enumerable. Then I can compute $X$ as follows: given $n$, I simply wait to see $n$ enter $X$ or $n$ enter $overline{X}$. Exactly one of these two things will happen (since $Xsqcupoverline{X}=mathbb{N}$), and I can tell which one does (since my enumerations are computable).
The relationship between computability and computable enumerability for functions is a bit more subtle. Specifically, we have (focusing on unary functions for simplicity):
Suppose $f:mathbb{N}rightarrowmathbb{N}$ is total. Then $f$ is computable iff $f$ is computably enumerable.
(Here, I'm conflating a function with its graph: "$f$ is computably enumerable" means "${langle a, brangle: f(a)=b}$ is computably enumerable.")
The left-to-right direction is again clear: $f$ is computable if the graph of $f$ is computable (by definition), and if the graph of $f$ is computable then it's certainly computably enumerable.
The right-to-left direction is the interesting one. Suppose $Graph_f={langle a,brangle: f(a)=b}$ is computably enumerable and I want to figure out what $f(n)$ is. What I'll do is "dovetail" - run a bunch of computations in parallel until one of them halts (basically, a more complicated version of what I did in the proof of the previous claim). Specifically:
See if $langle n, 0rangle$ enters $Graph_f$ by time $1$. If so, $f(n)=0$. If not, ...
See if $langle n, 1rangle$ enters $Graph_f$ by time $2$. If so, $f(n)=1$. If not, ...
See if $langle n, 0rangle$ enters $Graph_f$ by time $2$. If so, $f(n)=0$. If not, ...
See if $langle n, 2rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=2$. If not, ...
See if $langle n, 1rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=1$. If not, ...
See if $langle n, 0rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=0$. If not, ...
...
After finitely much time, eventually we'll see $langle n,krangle$ enter $Graph_f$ for some $k$. At that point, we stop and say, "$f(n)=k$."
We've used here two properties of $f$ (beyond the computable enumerability of its graph): that it is single-valued (once we know $langle 3,17ranglein Graph_f$, we know that $langle 3, 42ranglenotin Graph_f$) and that it is defined on all of $mathbb{N}$ (if $f(12)$ weren't defined, the procedure above would never finish with $n=12$ and so would never tell us conclusively that $langle 12, 451ranglenotin Graph_f$). These turn out to be essential:
There is a function with computably enumerable domain whose graph is computably enumerable but not computable, and there is a binary relation with domain $mathbb{N}$ (= for each $a$ there is at least one $b$ with $langle a,brangle$ in the relation) which is computably enumerable but not computable.
Proving these two claims is a good exercise.
answered Nov 30 '18 at 17:08
Noah SchweberNoah Schweber
124k10150287
$endgroup$
First of all, a comment on terminology: "recursively enumerable" and "computably enumerable" are the standard terms (and I'll use the latter here); moreover, I've never heard "computably generated" used before (although the meaning is clear).
I'll give informal, "Church's thesis style" arguments below; you should understand the intuitions behind the results before diving into the formal details (which are generally tedious if the motivation isn't clear). I'll also, for simplicity, focus on unary $R$ (and unary functions).
Finally, here's the first bit of actual intuition: we generally interpret "$exists x Q(a,x)$" as "$a$ enters $R$ at stage some stage," and in particular "$Q(a,b)$" as "$a$ enters $R$ at stage $b$" (or "by stage $b$"). Specifically, to tell whether $ain R$ we check:
Is $Q(a,0)$ true?
Is $Q(a, 1)$ true?
Is $Q(a,2)$ true?
...
Now to your question. Every computable relation is computably enumerable, but the converse is not true. The classic example is the Halting Problem, which has a few essentially equivalent definitions, the most transparent in my opinion being $$H={e: Phi_e(0)downarrow}.$$ Here "$Phi_e(0)downarrow$" means "the $e$th Turing machine on input $0$ halts."
You have already seen, I suspect, the proof that $H$ is not computable. However, it is computably enumerable! To tell whether $ein H$ we just run $Phi_e(0)$ and wait for it to halt - if it does halt, we put $ein H$. This is a computable process, and enumerates $H$. Note that it does not decide $H$: if $Phi_e(0)$ never halts, we don't necessarily figure that out at any particular moment. ("Well, it's been ten billion years and $Phi_e(0)$ hasn't halted yet ... but it might tomorrow!")
We can be a bit more precise about the relationship between "computably enumerable" and "computable." Specifically, we have (focusing on sets for simplicity):
A set $X$ is computable iff both $X$ and $overline{X}$ are computably enumerable.
(Here "$overline{X}$" denotes the complement of $X$.)
For the left-to-right direction, just note that all computable sets are computably enumerable, and the complement of a computable set is again computable.
For the right-to-left direction, suppose both $X$ and $overline{X}$ are computably enumerable. Then I can compute $X$ as follows: given $n$, I simply wait to see $n$ enter $X$ or $n$ enter $overline{X}$. Exactly one of these two things will happen (since $Xsqcupoverline{X}=mathbb{N}$), and I can tell which one does (since my enumerations are computable).
The relationship between computability and computable enumerability for functions is a bit more subtle. Specifically, we have (focusing on unary functions for simplicity):
Suppose $f:mathbb{N}rightarrowmathbb{N}$ is total. Then $f$ is computable iff $f$ is computably enumerable.
(Here, I'm conflating a function with its graph: "$f$ is computably enumerable" means "${langle a, brangle: f(a)=b}$ is computably enumerable.")
The left-to-right direction is again clear: $f$ is computable if the graph of $f$ is computable (by definition), and if the graph of $f$ is computable then it's certainly computably enumerable.
The right-to-left direction is the interesting one. Suppose $Graph_f={langle a,brangle: f(a)=b}$ is computably enumerable and I want to figure out what $f(n)$ is. What I'll do is "dovetail" - run a bunch of computations in parallel until one of them halts (basically, a more complicated version of what I did in the proof of the previous claim). Specifically:
See if $langle n, 0rangle$ enters $Graph_f$ by time $1$. If so, $f(n)=0$. If not, ...
See if $langle n, 1rangle$ enters $Graph_f$ by time $2$. If so, $f(n)=1$. If not, ...
See if $langle n, 0rangle$ enters $Graph_f$ by time $2$. If so, $f(n)=0$. If not, ...
See if $langle n, 2rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=2$. If not, ...
See if $langle n, 1rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=1$. If not, ...
See if $langle n, 0rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=0$. If not, ...
...
After finitely much time, eventually we'll see $langle n,krangle$ enter $Graph_f$ for some $k$. At that point, we stop and say, "$f(n)=k$."
We've used here two properties of $f$ (beyond the computable enumerability of its graph): that it is single-valued (once we know $langle 3,17ranglein Graph_f$, we know that $langle 3, 42ranglenotin Graph_f$) and that it is defined on all of $mathbb{N}$ (if $f(12)$ weren't defined, the procedure above would never finish with $n=12$ and so would never tell us conclusively that $langle 12, 451ranglenotin Graph_f$). These turn out to be essential:
There is a function with computably enumerable domain whose graph is computably enumerable but not computable, and there is a binary relation with domain $mathbb{N}$ (= for each $a$ there is at least one $b$ with $langle a,brangle$ in the relation) which is computably enumerable but not computable.
Proving these two claims is a good exercise.
answered Nov 30 '18 at 17:08
Noah SchweberNoah Schweber
124k10150287
edited Nov 30 '18 at 17:44
answered Nov 30 '18 at 17:08
Noah SchweberNoah Schweber
124k10150287
answered Nov 30 '18 at 17:08
Noah SchweberNoah Schweber
124k10150287
answered Nov 30 '18 at 17:08
Noah SchweberNoah Schweber
124k10150287
124k10150287
$begingroup$
I think what is confusing me is, what does it mean for a set to be computable vs computably generated?
$endgroup$
– Pinocchio
Dec 1 '18 at 2:52
1
$begingroup$
@Pinocchio Again, the idea is that a set is computably enumerable iff we can computably get positive information about it (if $nin A$ then we eventually realize $nin A$) but don't necessarily have negative information about it. In particular, the example of $H$ above should be helpful: it's easy to tell when something is in $H$ - we just see the corresponding program halt eventually - but it's very hard to tell when something isn't in $H$.
$endgroup$
– Noah Schweber
Dec 1 '18 at 3:21
$begingroup$
Re: that specific example, do you understand why $H$ is computably enumerable but not computable? (If not, which part is unclear.)
$endgroup$
– Noah Schweber
Dec 1 '18 at 3:22
$begingroup$
fantastic! Your second comment was the most helpful. Now I see what the difference between the two is. I didn't realize $a not in R iff forall x neg Q(a,x)$. So that "for all" quantifier is what makes it "uncomputable" (or at least there is no reason to believe that in finite time we can determine $a in R$ so its characteristic function isn't guaranteed to terminate in finite time). It seems intuitively plausible that there is no mechanical way always transform a forall statement into an exists...if there was then we wouldn't have this problem in the first place. Thanks!
$endgroup$
– Pinocchio
Dec 2 '18 at 1:56
1
$begingroup$
@Pinocchio That's it exactly - glad I could help!
$endgroup$
– Noah Schweber
Dec 2 '18 at 3:02
|
show 3 more comments
$begingroup$
I think what is confusing me is, what does it mean for a set to be computable vs computably generated?
$endgroup$
– Pinocchio
Dec 1 '18 at 2:52
1
$begingroup$
@Pinocchio Again, the idea is that a set is computably enumerable iff we can computably get positive information about it (if $nin A$ then we eventually realize $nin A$) but don't necessarily have negative information about it. In particular, the example of $H$ above should be helpful: it's easy to tell when something is in $H$ - we just see the corresponding program halt eventually - but it's very hard to tell when something isn't in $H$.
$endgroup$
– Noah Schweber
Dec 1 '18 at 3:21
$begingroup$
Re: that specific example, do you understand why $H$ is computably enumerable but not computable? (If not, which part is unclear.)
$endgroup$
– Noah Schweber
Dec 1 '18 at 3:22
$begingroup$
fantastic! Your second comment was the most helpful. Now I see what the difference between the two is. I didn't realize $a not in R iff forall x neg Q(a,x)$. So that "for all" quantifier is what makes it "uncomputable" (or at least there is no reason to believe that in finite time we can determine $a in R$ so its characteristic function isn't guaranteed to terminate in finite time). It seems intuitively plausible that there is no mechanical way always transform a forall statement into an exists...if there was then we wouldn't have this problem in the first place. Thanks!
$endgroup$
– Pinocchio
Dec 2 '18 at 1:56
1
$begingroup$
@Pinocchio That's it exactly - glad I could help!
$endgroup$
– Noah Schweber
Dec 2 '18 at 3:02
$begingroup$
I think what is confusing me is, what does it mean for a set to be computable vs computably generated?
$endgroup$
– Pinocchio
Dec 1 '18 at 2:52
$begingroup$
I think what is confusing me is, what does it mean for a set to be computable vs computably generated?
$endgroup$
– Pinocchio
Dec 1 '18 at 2:52
1
1
$begingroup$
@Pinocchio Again, the idea is that a set is computably enumerable iff we can computably get positive information about it (if $nin A$ then we eventually realize $nin A$) but don't necessarily have negative information about it. In particular, the example of $H$ above should be helpful: it's easy to tell when something is in $H$ - we just see the corresponding program halt eventually - but it's very hard to tell when something isn't in $H$.
$endgroup$
– Noah Schweber
Dec 1 '18 at 3:21
$begingroup$
@Pinocchio Again, the idea is that a set is computably enumerable iff we can computably get positive information about it (if $nin A$ then we eventually realize $nin A$) but don't necessarily have negative information about it. In particular, the example of $H$ above should be helpful: it's easy to tell when something is in $H$ - we just see the corresponding program halt eventually - but it's very hard to tell when something isn't in $H$.
$endgroup$
– Noah Schweber
Dec 1 '18 at 3:21
$begingroup$
Re: that specific example, do you understand why $H$ is computably enumerable but not computable? (If not, which part is unclear.)
$endgroup$
– Noah Schweber
Dec 1 '18 at 3:22
$begingroup$
Re: that specific example, do you understand why $H$ is computably enumerable but not computable? (If not, which part is unclear.)
$endgroup$
– Noah Schweber
Dec 1 '18 at 3:22
$begingroup$
fantastic! Your second comment was the most helpful. Now I see what the difference between the two is. I didn't realize $a not in R iff forall x neg Q(a,x)$. So that "for all" quantifier is what makes it "uncomputable" (or at least there is no reason to believe that in finite time we can determine $a in R$ so its characteristic function isn't guaranteed to terminate in finite time). It seems intuitively plausible that there is no mechanical way always transform a forall statement into an exists...if there was then we wouldn't have this problem in the first place. Thanks!
$endgroup$
– Pinocchio
Dec 2 '18 at 1:56
$begingroup$
fantastic! Your second comment was the most helpful. Now I see what the difference between the two is. I didn't realize $a not in R iff forall x neg Q(a,x)$. So that "for all" quantifier is what makes it "uncomputable" (or at least there is no reason to believe that in finite time we can determine $a in R$ so its characteristic function isn't guaranteed to terminate in finite time). It seems intuitively plausible that there is no mechanical way always transform a forall statement into an exists...if there was then we wouldn't have this problem in the first place. Thanks!
$endgroup$
– Pinocchio
Dec 2 '18 at 1:56
1
1
$begingroup$
@Pinocchio That's it exactly - glad I could help!
$endgroup$
– Noah Schweber
Dec 2 '18 at 3:02
$begingroup$
@Pinocchio That's it exactly - glad I could help!
$endgroup$
– Noah Schweber
Dec 2 '18 at 3:02
|
show 3 more comments
$begingroup$
I think I want to emphasize what made it click to me. Computable means that one can recognize if an element is in the set and if its not in finite time. So the indicator function or characteristic function is computable (which means that in finite time we always get a positive or negative answer). While computably generated/recursively enumerable is that membership is computable. So given an element in $R$ one can find a "certificate" that it indeed is in $R$ (is the way I interpret it from the definition:
$$ a in R iff exists x Q(a,x) $$
so we can get positive information about $a$ if it happens to be in $R$ (note we assume $Q$ is computable, so every time we plug in $(a,x)$ we get an answer in finite time). Note that if $a in R$ (which we don't know a priori usually) the search for $x$ shall terminate, say by checking all $x$'s until $Q(a,x)$ returns true.
But if its not then we might not find that out ever because notice the negation:
$$ a not in R iff forall x neg Q(a,x) $$
which means you might have to potentially need to check all $x$'s. There probably isn't a standard way to convert for all statements into existence statements so this search might never terminate. Which is the key. If $a$ happens to not be in $R$ then the above might never terminate.
So we can only get positive info about $R$.
Note if both are computably enumerable, then we do get $R$ is computable, since we can find a certificate for both membership and not in finite time.
answered Dec 2 '18 at 18:18
PinocchioPinocchio
1,91041854
$endgroup$
add a comment |
$begingroup$
I think I want to emphasize what made it click to me. Computable means that one can recognize if an element is in the set and if its not in finite time. So the indicator function or characteristic function is computable (which means that in finite time we always get a positive or negative answer). While computably generated/recursively enumerable is that membership is computable. So given an element in $R$ one can find a "certificate" that it indeed is in $R$ (is the way I interpret it from the definition:
$$ a in R iff exists x Q(a,x) $$
so we can get positive information about $a$ if it happens to be in $R$ (note we assume $Q$ is computable, so every time we plug in $(a,x)$ we get an answer in finite time). Note that if $a in R$ (which we don't know a priori usually) the search for $x$ shall terminate, say by checking all $x$'s until $Q(a,x)$ returns true.
But if its not then we might not find that out ever because notice the negation:
$$ a not in R iff forall x neg Q(a,x) $$
which means you might have to potentially need to check all $x$'s. There probably isn't a standard way to convert for all statements into existence statements so this search might never terminate. Which is the key. If $a$ happens to not be in $R$ then the above might never terminate.
So we can only get positive info about $R$.
Note if both are computably enumerable, then we do get $R$ is computable, since we can find a certificate for both membership and not in finite time.
answered Dec 2 '18 at 18:18
PinocchioPinocchio
1,91041854
$endgroup$
add a comment |
$begingroup$
I think I want to emphasize what made it click to me. Computable means that one can recognize if an element is in the set and if its not in finite time. So the indicator function or characteristic function is computable (which means that in finite time we always get a positive or negative answer). While computably generated/recursively enumerable is that membership is computable. So given an element in $R$ one can find a "certificate" that it indeed is in $R$ (is the way I interpret it from the definition:
$$ a in R iff exists x Q(a,x) $$
so we can get positive information about $a$ if it happens to be in $R$ (note we assume $Q$ is computable, so every time we plug in $(a,x)$ we get an answer in finite time). Note that if $a in R$ (which we don't know a priori usually) the search for $x$ shall terminate, say by checking all $x$'s until $Q(a,x)$ returns true.
But if its not then we might not find that out ever because notice the negation:
$$ a not in R iff forall x neg Q(a,x) $$
which means you might have to potentially need to check all $x$'s. There probably isn't a standard way to convert for all statements into existence statements so this search might never terminate. Which is the key. If $a$ happens to not be in $R$ then the above might never terminate.
So we can only get positive info about $R$.
Note if both are computably enumerable, then we do get $R$ is computable, since we can find a certificate for both membership and not in finite time.
answered Dec 2 '18 at 18:18
PinocchioPinocchio
1,91041854
$endgroup$
I think I want to emphasize what made it click to me. Computable means that one can recognize if an element is in the set and if its not in finite time. So the indicator function or characteristic function is computable (which means that in finite time we always get a positive or negative answer). While computably generated/recursively enumerable is that membership is computable. So given an element in $R$ one can find a "certificate" that it indeed is in $R$ (is the way I interpret it from the definition:
$$ a in R iff exists x Q(a,x) $$
so we can get positive information about $a$ if it happens to be in $R$ (note we assume $Q$ is computable, so every time we plug in $(a,x)$ we get an answer in finite time). Note that if $a in R$ (which we don't know a priori usually) the search for $x$ shall terminate, say by checking all $x$'s until $Q(a,x)$ returns true.
But if its not then we might not find that out ever because notice the negation:
$$ a not in R iff forall x neg Q(a,x) $$
which means you might have to potentially need to check all $x$'s. There probably isn't a standard way to convert for all statements into existence statements so this search might never terminate. Which is the key. If $a$ happens to not be in $R$ then the above might never terminate.
So we can only get positive info about $R$.
Note if both are computably enumerable, then we do get $R$ is computable, since we can find a certificate for both membership and not in finite time.
answered Dec 2 '18 at 18:18
PinocchioPinocchio
1,91041854
answered Dec 2 '18 at 18:18
PinocchioPinocchio
1,91041854
answered Dec 2 '18 at 18:18
PinocchioPinocchio
1,91041854
answered Dec 2 '18 at 18:18
PinocchioPinocchio
1,91041854
1,91041854
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2f3020322%2fwhat-is-the-difference-between-computably-generated-and-computable%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
2
$begingroup$
The remark at the end says that there are computably generated relations (see later in the book) such that their complements are not computably generated. They will thus fail to be computable. Moreover, a relation is computable iff it and its complement are both computably generated.
$endgroup$
– Berci
Nov 30 '18 at 17:11
$begingroup$
now that I read back on the notes, I think I do know what computable function is but NOT on what computable set of L-sentences is, hence my Q: math.stackexchange.com/questions/3020934/…
$endgroup$
– Pinocchio
Dec 1 '18 at 3:08
$begingroup$
Recall that computable means you can determine membership AND non membership in finite time. Computably generated just means you can ONLY determine membership in finite time (but cannot get information about non membership in finite time).
$endgroup$
– Pinocchio
Dec 2 '18 at 2:01
$begingroup$
Im also having a hard time understanding why that was the chosen name...how does it enumerate or generate stuff?
$endgroup$
– Pinocchio
Dec 2 '18 at 22:01