Reductions and Undecidability

Learn how reducing a problem into a simpler problem can help us solve the complex problem easily.

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, AA (for “accept”), that, given any Turing machine MM, and any string ww, will determine whether MM accepts ww. Again, we doubt this is possible, since not all TM\text{TM}s halt. What would be the consequences of the existence of such an algorithm, AA? In essence, it would mean that all recursively enumerable languages are recursive, since AA would decide all TM\text{TM}s with an input arbitrary string. But we know that some recursively enumerable languages are not recursive (contradiction!), so AA 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, AA is “reducible” to any other RE language’s TM\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, HH, is undecidable by reducing the membership problem, AA, to HH. In other words, we can show that if HH is decidable, then so is AA—a contradiction. Consider the program (or, by the Church-Turing Thesis, the “Turing machine”) below:

Get hands-on with 1200+ tech skills courses.