From Ullman and Hopcroft's Introduction to Automata Theory, Language, and Computation 1ed 1979:
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.
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."
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?
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?
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?