Question
Answer and Explanation
To prove that a language is undecidable, you typically demonstrate that no Turing machine can always halt and correctly decide whether a given string belongs to the language or not. Here's a breakdown of common methods:
1. Reduction from a Known Undecidable Problem:
- The most common technique is to show that if you could decide the language in question (let's call it L), you could also solve a known undecidable problem (e.g., the Halting problem). This is done by reducing the known undecidable problem to L.
- The Halting problem is frequently used as the basis for reductions. The Halting problem asks: Given a Turing Machine M and an input string w, will M halt when run on w?
- To perform a reduction, you must show that if you had a decider for L (a Turing Machine that always halts and correctly answers whether a string is in L or not), you could construct a Turing Machine that decides the Halting problem. Since the Halting problem is undecidable, it follows that L must also be undecidable.
2. Proof by Contradiction:
- Assume that the language L is decidable. This implies there exists a Turing Machine (TM) that can decide L.
- Show that this assumption leads to a contradiction, often by using the hypothetical TM to solve a known undecidable problem.
3. Rice's Theorem:
- Rice's Theorem states that any non-trivial property of the language recognized by a Turing machine is undecidable.
- A "non-trivial" property is one that is neither true for all recognizable languages nor true for no recognizable languages.
- To use Rice's Theorem, you need to show that the language in question represents a non-trivial property of the languages recognized by Turing machines. For example, determining whether a TM recognizes an empty language is undecidable by Rice's Theorem.
4. Diagonalization:
- Diagonalization is a powerful technique often used to prove undecidability. This method was famously employed by Alan Turing to show the undecidability of the Halting problem.
- The general idea involves creating a "diagonal" Turing machine that behaves differently from all other Turing machines on a particular input.
Example: Reduction from the Halting Problem
Suppose we want to show that the language L = { < M > | M is a Turing Machine that halts on at least one input } is undecidable.
Assume, for the sake of contradiction, that L is decidable. That is, there exists a Turing Machine, `decider_L`, that decides L.
Now, let's use `decider_L` to build a TM, `decider_Halting`, that decides the Halting problem.
Given a Turing Machine M and input w (the input to the Halting problem), `decider_Halting` does the following:
1. Construct a new Turing Machine M' from M and w.
2. M' ignores its input and runs M on w.
3. Run `decider_L` on < M' >. If `decider_L` accepts, then M' halts on at least one input (in fact, it halts on every input). Thus, M halts on w. If `decider_L` rejects, then M' halts on no inputs, which is a contradiction. Thus, M does not halt on w.
Thus, if `decider_L` exists, we've constructed `decider_Halting`, a decider for the Halting problem. But the Halting problem is undecidable! Therefore, our initial assumption (that `decider_L` exists) must be false. Therefore, L is undecidable.
These methods are crucial in theoretical computer science for understanding the limits of computation.