Reductions and Undecidability

The membership problem

Let’s now consider the membership problem, which determines whether a given string is in a given language. For regular languages, we just run the string through the machine’s DFA to see if it is accepted. For context-free languages, we can use the CYK algorithm to see if the string is generated by a given CFG. For recursively enumerable languages, we want an algorithm, $A$ (for “accept”), that, given any Turing machine $M$, and any string $w$, will determine whether $M$ accepts $w$. Again, we doubt this is possible, since not all $\text{TM}$s halt. What would be the consequences of the existence of such an algorithm, $A$? In essence, it would mean that all recursively enumerable languages are recursive, since $A$ would decide all $\text{TM}$s with an input arbitrary string. But we know that some recursively enumerable languages are not recursive (contradiction!), so $A$ cannot exist.

Note: The membership problem is undecidable.

This is a very strong result. This means that the membership problem characterizes RE languages. In other words, $A$ is “reducible” to any other RE language’s $\text{TM}$. Such languages are called RE-complete.

Knowing now that the membership problem is undecidable, suppose for the moment that we didn’t know that the halting problem was undecidable. We can show that the halting problem, $H$, is undecidable by reducing the membership problem, $A$, to $H$. In other words, we can show that if $H$ is decidable, then so is $A$—a contradiction. Consider the program (or, by the Church-Turing Thesis, the “Turing machine”) below:

In this program, we assume that an algorithm for the halting problem, $H$, exists. If $H$ indicates that $M$ halts on $w$ (i.e., it returns True), then $R$ just executes $M$ on $w$ to determine whether it accepts $w$ or not. On the other hand, if $H$ indicates that $M$ does not halt on $w$, then $M$ can’t accept $w$, so $R$ rejects it. The algorithm $R$ decides the membership problem, which we know is undecidable (contradiction!)—therefore, the halting problem must also be undecidable. We have reduced ...