Corrections and Pedagogical Issues

1. Item 4 of Example 1.11 is too cumbersome. Replace with

<{card(X) | X \in C}, \leq >.

2. The proof of Theorem 2.1 uses multitape Turing machines, but occurs in the section before defining multitape Turing machines. It would be best to state the result here, but postpone its proof to after discussion of multitape Turing machines. This proof is a good illustration of the usefulness of multitape Turing machines. There is another unfortunate aspect to the current placement of the proof. Namely, students should solve Homework 2.1 using single-tape Turing machines. They should do this for the experience and because this exercise will help to drive home the point that multitape Turing machines are both more efficient and easier to program.

3. Homework 2.2 should occur in Section 2.3.1, because it is acceptable to use multitape Turing machines for this exercise.

4. Lemma 3.1 should state that the graph of a TOTAL computable function is decidable. It is a common convention to use “computable” to mean “total computable,” but so far we have been careful to write “total computable” when that is what we mean, and we should continue that style.

5. Homework 3.21 should ask for a nontrivial language (i.e., L \notin {\Sigma^*, \emptyset}).

6. This note is similar to item 4. Theorem 3.7 promises existence of a total computable function. So does Corollary 3.3 So do Theorems 3.9 and Corollary 3.4. Theorem 3.10 applies to total computable functions. In general “computable” means total computable.

7. The description of UNIT RESOLUTION on page 178 might be confusing to students. On page 7 we defined a clause to be a disjunction of literals. However in this example we use set notation to describe clauses. It would be best to write “Identify a clause $c = x_1 \vee \ldots x_k$ with the set

$c = \{ x_1, \ldots, x_k \}$.”