Basic Undecidability Proofs: In this chapter, we define the notion of decidability, semi-decidability, and undecidability. These notions pertain to degrees of solvability of problems by Turing machines. We will present three proof methods in this chapter: (i) through contradiction (Section 16.2.3), (ii) through reductions from languages unknown to be decidable (Section 16.2.4), and (iii) through mapping reductions (Section 16.2.5). Chapter 17 will
discuss two additional proof methods: (iv) Rice’s theorem, and (v) computational history method.
Methods (ii), (iii), and (iv) are strongly related to each other, in the following sense:
The parallels between this chapter and Chapter 19 are worth reiterating. In this section, we present mapping reductions of the form A ≤m B where there exists a function f such that x ∈ A ⇔ f(x) ∈ B.
All we require of f is that it be a total computable function. In Chapter 19, we will define A ≤P B where the function in question will be one that has polynomial runtime. Also, in Chapter 19, we will point out the analogous fact that Hidden in every NP-complete problem is a proof of the NPcompleteness of Boolean satisfiability. With these introductions, we now proceed to study the three reduction methods.
At this juncture, it pays to recall the facts introduced in Chapter 1,
namely:
In Section 16.1.1, we examine a list of decidable problems with a view to sharpen our intuitions in this area. The existence of deciders is shown by presenting the pseudocode of an algorithm. In Section 16.1.2, we examine a list of undecidable problems.