3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ There is no "nice" way to construct the set of total recursive functions. For examples, primitive r. f. are those computed by programs in languages with bounded loops, and partial r. f. are computed by programs in any standard language. So, to write a program for a given general problem, the "environment" of partial r. f. has to be used. However, this program should halt for any input in the problem's domain. Thus the program will implement a total function, even though the "environment" allowed the possibility of this function not being total. $\endgroup$ – Luka Mikec Oct 3 '16 at 7:45
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. Suppose that recursive languages are associated to total recursive functions, not partial. In the 2ed as well as 1ed and 3ed, recursive languages are used for defining decidability, but why does the Church-Turing thesis use partial recursive functions instead of total ones for computability? " The unprovable assumption that any general way to compute will allow us to compute only the partial-recursive functions (or equivalently, what Turing machines or modern-day computers can compute) is known as Church's hypothesis (after the logician A. Church) or the Church-Taring thesis." $\endgroup$ – Tim Oct 3 '16 at 12:47
  • $\begingroup$ I edited the answer $\endgroup$ – Manlio Oct 3 '16 at 22:29
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. Your reply tries to address part 1 of my questions, which compares the first two quotes. Note that the second quote says that a problem is said to be decidable if the corresponding language of the problem is recursive, and it doesn't define the decidability of a problem in terms of total recursive functions as in your reply. Do you assume that total recursive functions and recursive languages are essentially the same concept, similarly to what the third quote says? $\endgroup$ – Tim Oct 3 '16 at 13:51
  • $\begingroup$ There is a correspondence, and this correspondence is strong. That's what the quote says, not that they are the same concept. Some of us would love to have a unified theory of those concepts, but we don't have, and we don't really need it. $\endgroup$ – André Souza Lemos Oct 3 '16 at 14:17
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. That explains what "sense" means in the third quote. Does that contradict the implication of the first two quotes as pointed out in my part 1? $\endgroup$ – Tim Oct 3 '16 at 13:17
  • $\begingroup$ @Tim No, that looks more or less correct. Usually we speak of "computable functions" and "decidable languages/problems" to mean that there is some program which can solve some task. The Terms "computable" and "decidable" are not exchangeable only because they are used on different things (functions/sets). $\endgroup$ – chi Oct 3 '16 at 14:40

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.