Problem Set 7—Undecidability

Purpose

This problem set reinforces your understanding of undecidability proofs. By the time you finish this exercise, you should be able to prove the undecidability of a variety of problems.

Background

This problem set is minimally based on material in section 4.2 of our textbook, and may, if you wish, also draw on material in section 5.1. We discussed section 4.2 in lectures on March 25 and March 28. We will discuss section 5.1 in class on March 30 and April 1.

Activity

Prove that the languages in problems 1 through 4 are undecidable. You may use either diagonalization or reduction, as you prefer. Solve problem 5 as it directs.

Problem 1

Problem 5.9 in our textbook ({ ⟨M⟩ | Turing machine M accepts w^R whenever it accepts w }).

Problem 2

Problem 5.12 in our textbook (the language that represents the problem of deciding whether a Turing machine ever writes a blank over a nonblank on its tape; part of the question asks you to formulate this problem precisely as a language).

Problem 3

{ ⟨M⟩ | Turing machine M halts on all inputs }. Note the slight difference between this language and the Halting Problem we studied in class.

Problem 4

{ ⟨M,w⟩ | Turing machine M makes an even number of state transitions when run on input w}. Hint: start by showing how to modify any Turing machine into an equivalent one that “knows” whether it has made an even or odd number of state transitions. (This question is motivated by something one of you asked while grading the Turing machines problem set.)

Problem 5

Show that the complement of the language in problem 3 is not Turing recognizable.

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.