1
$\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:

enter image description here

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?

$\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
5
$\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 $a\in 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 $e\in H$ we just run $\Phi_e(0)$ and wait for it to halt - if it does halt, we put $e\in 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 $X\sqcup\overline{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}\rightarrow\mathbb{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, b\rangle: 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,b\rangle: 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, 0\rangle$ enters $Graph_f$ by time $1$. If so, $f(n)=0$. If not, ...

  • See if $\langle n, 1\rangle$ enters $Graph_f$ by time $2$. If so, $f(n)=1$. If not, ...

  • See if $\langle n, 0\rangle$ enters $Graph_f$ by time $2$. If so, $f(n)=0$. If not, ...

  • See if $\langle n, 2\rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=2$. If not, ...

  • See if $\langle n, 1\rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=1$. If not, ...

  • See if $\langle n, 0\rangle$ enters $Graph_f$ by time $3$. If so, $f(n)=0$. If not, ...

  • ...

After finitely much time, eventually we'll see $\langle n,k\rangle$ 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,17\rangle\in Graph_f$, we know that $\langle 3, 42\rangle\not\in 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, 451\rangle\not\in 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,b\rangle$ in the relation) which is computably enumerable but not computable.

Proving these two claims is a good exercise.

$\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 $n\in A$ then we eventually realize $n\in 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
0
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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