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.
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...
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?