Problem Set 9—Computation Histories and Reduction

Purpose

This problem set reinforces your understanding of some undecidability results following from reductions via computation histories. By the time you finish this exercise, you should be able to reason about (1) the Post Correspondence Problem, (2) proof(s) that ambiguity and related problems about context free grammars are undecidable, and (3) how computation histories are used in a proof that ALL_CFG is undecidable.

Background

This problem set is based on material in sections 5.1 and 5.2 of our textbook. We discussed this material in lectures between April 6 and April 13.

Activity

Solve the following problems.

Problem 1

Recall the book’s proof that ALL_CFG is undecidable (Theorem 5.13). This proof centers on a PDA that recognizes strings that are not accepting computation histories for some Turing machine. That PDA relies on nondeterminism to guess which of several conditions for being an accepting computation history its input violates. Could you use this same strategy to design an NFA that recognizes strings that aren’t accepting computation histories, and thereby show that ALL_NFA is undecidable? Why or why not?

Problem 2

Is ALL_NFA from Problem 1 undecidable? (OK, asking this question implies that the answer to Problem 1 is “no,” but not why.) If so, give a proof; if not, sketch a decider for ALL_NFA.

Problem 3

Problem 5.19 in our textbook (show that the “silly Post Correspondence Problem” is decidable; see the text for the definition of the “silly Post Correspondence Problem”).

Problem 4

Problem 5.35 in our textbook (show that the problem of determining whether a variable in a context free grammar is “necessary” is undecidable; see the text for the definition of “necessary” variables).

Problem 5

Consider a modified Post Correspondence Problem instance { ab/aba, ab/b, aa/a } where I’ve written tiles with a slash symbol between their top and bottom parts, and the starting tile for the modified PCP (the one the book calls the “first” tile) is the first one listed in the set. Show the tiles that would result from the book’s construction of a standard PCP instance from this modifed PCP instance. Explain why the construction creates two variations on the first tile, but only one variation on all the others.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. If you worked in a group on this exercise, the whole group should schedule a single meeting with me. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.