Computability Theory

4 Recursive Enumerability

First of all, let’s summarize some of the results of the preceding chapters and establish

the terminology that will be used henceforth.

We have seen that the class of general recursive partial functions is exactly the

same as the class of register-machine computable partial functions. The fact that two

such different approaches yield the same class of functions is evidence that we have

here a “natural” class. The members of this class will be called computable partial

functions (or recursive partial functions – the two names are both in common use).

The adjective “partial” covers both the total and nontotal functions; it can be omitted

in cases where we know that the function is total. Church’s thesis is the assertion that ...