Basic Undecidability Proofs

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:

• Applications of method (ii), namely reduction from a known undecidable language, A, to the language in question, B, employs an ‘if and only if’ argument of the form x ∈ A ⇔ f(x) ∈ B.
• Method (iii), namely mapping reductions, isolates this ‘if and only if’ argument into a mapping reduction principle which is quite powerful, and also applicable in other contexts.
• Method (iv), namely Rice’s Theorem, capitalizes on the core argument underlying all these proofs. It tends to make the connection that Hidden in every undecidability proof is a proof of the undecidability of the Halting problem. Rice’s Theorem makes it even more convenient to carry out undecidability proofs.

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:

• We can deem two computers to be equivalent if they can solve the same class of problems — ignoring the actual amount of time taken (see discussions on page 5).
• Problem solving can be modeled in terms of deciding membership in languages (page 5).
• Some problems are unsolvable. Formally stated, there exists a class of problems P such that for any p ∈ P, one can model p using a language Lp such that Lp admits no membership deciders.
• Other problems have deciders, but these may take different amounts of runtime to decide language membership.

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.