Now that we’ve discussed Turing machines, we’re ready to define the notions of (Turing) decidability and recognizability for languages and decision problems. We will show that there are problems - such as the halting problem - that are undecidable and we will also show how we can use (Turing) reductions to show that a problem is undecidable.

Decidability and recognizability of languages and decision problems

In this video, I will present the concept of (Turing) decidability and recognizability for languages and decision problems. You might be asking yourself: Decision problems, where did that come from? We have actually been dealing with decision problems this whole time! Indeed, there is always a decision problem for a corresponding formal language (and vice-versa). The decision problem \(Q\) of a language \(L_Q\) is typically the following: “Given \(x \in \Sigma^*\), is \(x \in L_Q\)?” While this might seem like a bit of a silly way of talking about a language, we will see that it’s a much more natural conceptualization when discussing properties of decidability and recognizability. This and more in the following video!

The halting problem is undecidable

In this video, I show you the infamous proof that the halting problem is undecidable. The technique which I use is very similar to Cantor’s diagonalization technique used to show that \(\mathbb{R}\) is uncountable.

The undecidability hierarchy and reductions

In this video, I discuss the undecidability hierarchy and introduce, at a high level, how we can use (Turing) reductions to show that a decision problem is undecidable. A more concrete example is presented in the next video!1

Using a reduction to show that EXAM2 is harder than EXAM1

In this final video of this section, I provide a more concrete usage of the reduction proof technique to show that one exam, EXAM2, is harder than another exam, EXAM1. While this doesn’t use any decision problems you will encounter in a theoretical CS class, it will provide you with the general blueprint that we will be following to reduce one decision problem to another. More “realistic” reductions can be found in the exercises below.

Exercises

Exercise. Suppose we have a finite family of languages \(\mathcal{F}\) that partitions \(\Sigma^*\). Assume every language \(L \in \mathcal{F}\) is Turing recognizable. Show that every language in the partition is in fact Turing decidable.

Exercise. Show that the Halting Problem \(\textsf{HP}\) is undecidable by giving a reduction from the Acceptance Problem \(\textsf{AP}\).
  • \(\textsf{HP}:\) Given a TM \(M\) and an input \(x\), does \(M\) halt on \(x\)?
  • \(\textsf{AP}:\) Given a TM \(M\) and an input \(x\), does \(M\) accept \(x\)?

Exercise. Show that the decision problem \(\textsf{EMPTY}\) is undecidable using a reduction from either \(\textsf{AP}\) or \(\textsf{HP}\). Recall \(\textsf{EMPTY}\): Given a TM \(M\), is \(L(M) = \emptyset\)?

Exercise. Show that the decision problem \(\textsf{REG}\) is undecidable using a reduction from either \(\textsf{AP}\) or \(\textsf{HP}\). Recall \(\textsf{REG}\): Given a TM \(M\), is \(L(M)\) regular?

  1. I never explicitly say it in these videos, but all the reductions we see in this section fall under the term Turing reductions. Mapping reductions, which are a special type of Turing reduction, are not discussed here. ↩