Are partial recursive functions analogous to recursive languages or r.e. languages?

Question

From Ullman and Hopcroft's Introduction to Automata Theory, Language, and Computation 1ed 1979:

1. The assumption that the intuitive notion of "computable function" can be identified with the class of partial recursive functions is known as Church's hypothesis or the Church-Turing thesis.

2. A problem whose language is recursive is said to be decidable. Otherwise, the problem is undecidable. That is, a problem is undecidable if there is no algorithm that takes as input an instance of the problem and determines whether the answer to that instance is "yes" or "no."

3. Note that one TM may compute a function of one argument, a different function of two arguments, and so on. Also note that if TM M computes function f of k arguments, then f need not have a value for all different k-tuples of integers. ...

   In a sense,

   • the partial recursive functions are analogous to the r.e. languages, since they are computed by Turing machines that may or may not halt on a given input.
   • The total recursive functions correspond to the recursive languages, since they are computed by TM's that always halt. ...

How do these go together?

1. From the following first two quotes

   • The first quote says that computability can be identified with the class of partial recursive functions,

   • the second quote seems to say that computability can be identified with recursive languages.

     Note that the second quote says about decidability while here I uses computability, so I assume that computability and decidability are the same or consistent concepts, but is it true?

   Do they imply that partial recursive functions and recursive languages are analogous to each other, as far as computability/decidability is concerned?

2. The third quote says that "in a sense",

   • the partial recursive functions are analogous to the r.e. languages
   • The total recursive functions correspond to the recursive languages.

   Does the third quote contradict the implication from the first two quotes as pointed out above in part 1?

   In what "sense", does the third quote mean?

   For my related confusion about the third quote, see Do the Turing machines involved in Chruch-Turing thesis have to halt on all the inputs?

Answer 1

Let me quote from the second edition of the same textbook, section 9.1 (sorry, I don't have the first one):

Recall that a language L is recursively enumerable (abbreviated RE) if L = L(M) for some TM M. Also, we shall in Section 9.2 introduce "recursive" or "decidable" languages that are not only recursively enumerable, but are accepted by a TM that always halts, regardless of whether or not it accepts.

Therefore recursive languages are associated to total recursive functions, not partial.

Hope this answers both the questions.

EDIT: to answer the comment:

On the one hand, the reason lies on intuition: the Church-Turing thesis is about capturing the intuitive idea of "effective computability" or "things that we can actually compute". Imagine a program that, if there is a correct answer then it computes the answer, otherwise it never halts (i.e. it gives an answer only if there is an answer). Would you say that such a program computes the answer or not?

But on the other hand, if this intuitive picture doesn't convince you, consider the following (way more concrete): consider an effective enumeration $(\varphi_i)_{i\in\mathbb{N}}$ of all total recursive functions and consider the function $\varphi:=x\mapsto\varphi_x(x)+1$. Now it is clear that you can compute $\varphi$: you can find the $x$-th function, you can compute it (as it is recursive) and you can sum 1 (as sum is recursive). But $\varphi$ cannot be total by a diagonal argument: if it were total than it would have its own index $i$, therefore

$$ \varphi(i) = \varphi_i(i)+1 = \varphi(i) +1 $$

which is a contradiction. This problem vanishes if you consider instead partial functions.

Answer 2

To say that the notion of computable (number, function) is intuitive comes from the fact that it is not originally a mathematical concept - which is why your question belongs here, and not on math.se. Partial recursive functions define computability the same way a (formally stated) drawing method can be said to define what "circularity" is, within the context of an axiomatic geometrical theory.

There is no contradiction between the two first quotes, they just talk about different things. Things that are computable can be thought of as those that can be associated to a partial recursive definition, a posteriori. Logical predicates ("problems") that are decidable are those whose truth values can be obtained by a specific method, which has to be formally definable by a total recursive function, also a posteriori. They are called semi-decidable if the function is partial.

"In a sense" is there just to avoid conflating concepts that come from different domains but can be related in a strong way. Geometric shapes are not equations, but in a sense they can be strongly related.

Answer 3

A language $L$ is r.e. if and only if $L$ is the domain of some partial recursive function. That is, iff there's a program halting on $L$ and nowhere else.

A language $L$ is recursive if and only if it is the support of a total recursive function. The support of a function $f$ is the set of points where $f$ is nonzero, i.e. $\{n\ |\ f(n)\neq 0 \}$.

Alternatively, you can consider the characteristic and semi-characteristic functions of a set $L$, defined as follows:

$$ \chi_L(x) = \begin{cases} 1 & \mbox{if $x \in L$}\\ 0 & \mbox{otherwise} \end{cases} \qquad \tilde{\chi}_L(x) = \begin{cases} 1 & \mbox{if $x \in L$}\\ {\sf undefined} & \mbox{otherwise} \end{cases} $$ Then, we have that $L$ is recursive iff $\chi_L(x)$ (which is total) is a recursive function. We also have that $L$ is r.e. iff $\tilde{\chi}_L(x)$ (which is partial) is a recursive function.