CSC 341: April 4, 2007

From CSWiki

1 Instructor's notes for the class session
- 1.1 Reduction proofs
- 1.2 Rice's theorem
2 Study questions
- 2.1 Proposed Solutions

Instructor's notes for the class session

Reduction proofs

Our reading for today introduces the reduction design pattern for undecidability proofs: To prove that language $A$ is undecidable, we show that, if we had a decider for $A$ , we could use it to construct a decider for some other language, $B$ , that has already been proven undecidable. This is a proof by contradiction -- the assumption that $A$ is decidable leads to an impossibility, so $A$ must be undecidable.

Following the usage of mathematicians, we describe the central construction in such a proof as a reduction of $B$ to $A$ ; considered as a problem, the language $B$ is, in effect, no harder than $A$ , since an instance of problem $B$ can be recast or transformed or preprocessed into an instance of problem $A$ . But if $B$ is no harder than $A$ , and $B$ is undecidable, then $A$ must also be undecidable.

Several of the theorems in section 5.1 illustrate this design pattern. In most of those proofs, the acceptance problem for Turing machines plays the role of $B$ . As we build up a larger and larger stockpile of languages that are known to be undecidable, however, the power of this reduction idea grows, because it becomes easier and easier to find something in that stockpile that can be reduced in a simple and straightforward way to the target problem $A$ .

Since the inputs to the kinds of Turing machines that we're discussing in this chapter are often encodings for automata, the reduction step that converts the input to the (supposed) decider for $B$ into input appropriate for the (supposed) decider for $A$ often involves extending or tweaking an encoded automaton. This can be confusing -- if, say, the preprocessor takes an encoding $\langle M\rangle$ and computes from it an encoding $\langle M'\rangle$ , it is tempting, but incorrect, to suppose that the preprocessor must actually run $M$ at some point. Students sometimes worry unnecessarily about where the input to that computation comes from and whether it will terminate. In fact, however, many of the preprocessors that show up in reduction proofs do not need to simulate any execution of $M$ in order to transform its encoding appropriately.

Section 5.1 also discusses one major variation on this theme: reduction via computation history. The idea here is that the $M'$ automaton (grammar, regular expression, or whatever) needs as its input a trace of the execution of the $M$ automaton, that is, a sequence of configurations of $M$ as its processes some given input. When it can be proven that $M$ halts on the necessary input, it is straightforward to design the preprocessor so that it simulates the operation of $M$ and transcribes a trace of $M$ 's configurations onto its tape.

[edit]

Rice's theorem

Rice's theorem, which Sipser presents as problem 5.28 (with the solution on page 215), abstracts out the common structure of proofs by reduction to obtain a very general result: The acceptance problem for Turing machines can be reduced to any language $P$ that (1) contains the encodings for some Turing machines and not for others, and (2) does not distinguish between encodings for Turing machines that recognize the same language (always either including both or including neither). Any such language $P$ is, therefore, undecidable.

[edit]

Study questions

Show that $E Q CFG$ , the problem of whether two given context-free grammars generate exactly the same language, is undecidable.
If a language $A$ is undecidable, and $A$ is reducible to $B$ , then it follows that $B$ is also undecidable. But what if $A$ is undecidable and $B$ is reducible to $A$ ---does anything follow about $B$ ? If so, what?
Modify the proof of Theorem 5.3 to show that $F I N I T E TM$ , the set of encodings for Turing machines that recognize finite languages, is undecidable.
Use Rice's theorem to show that the set of encodings for Turing machines that accept parity-bound languages is undecidable. (A language is parity-bound if it contains only strings of even length or only strings of odd length.)

[edit]

Proposed Solutions

To prove that the given language is undecidable, we need to show that $A L L CFG$ is reducible to $E Q CFG$ . Let's call the decider for $E Q CFG$ N. Using N, we can construct M to be a decider for $A L L CFG$ . M takes a CFG, G as its input. M also contains the encoding for A, a CFG that is known to accept all strings over its alphabet. M passes G and A to N; if N accepts, M accepts, if N rejects, M rejects. Because M now decides $A L L CFG$ , previously proven undecidable, by using a decider for $E Q CFG$ , $E Q CFG$ must also be undecidable.
Nothing is shown about B if A is undecidable and B is reducible to A. B being reducible to A is similar to saying that B is no harder than A. So, if B where undecidable and reducible to A, we would know that B was no harder than A, and that B was insolvable, so A must also be insolvable. However, saying that B is no harder than an unsolvable problem tells us nothing of B.