Problem Set 8—Undecidability by Reduction

Purpose

This problem set develops your ability to use reductions to prove undecidability. By the time you finish this exercise, you should be able to construct reduction proofs for a variety of problems. You should also understand some of the applications and consequences of Rice’s Theorem.

Background

This problem set is based on material in section 5.1 of our textbook. We discussed (or will discuss) reduction in lectures on March 30, April 1, and April 4. Rice’s Theorem is presented in problem 5.28 in our textbook, and a sketch of its proof appears in the solution to that problem (it’s one of the problems with a solution in the book). We will discuss it in class on April 4.

Activity

Solve the following problems.

Problem 1

Determine which of the following are undecidable by Rice’s Theorem, and which are not (although they may still be undecidable for other reasons).

Language 1

{⟨M⟩ | ε ∈ L(M) }

Language 2

{⟨M⟩ | ∅ ⊆ L(M) }

Language 3

{⟨M⟩ | There exists a string w such that M enters exactly 5 distinct states when run on w}

Problem 2

Use reduction (and not just reference to Rice’s Theorem) to show that the set {⟨M⟩ | L(M) contains at least one string of length 3} is undecidable.

Problem 3

Use reduction to show that the following problem is undecidable: given 3 Turing machines, M₁, M₂, and M₃, does L(M₁) = L(M₂) ∪ L(M₃)?

Problem 4

Use reduction to show that the following problem is undecidable: given a program (or pseudocode algorithm) P, a variable name, n, and an input, w, does P ever assign 0 to a variable named n when run on w? You may assume that the program analogs of all problems you already know to be undecidable for Turing machines are also undecidable for programs.

Problem 5

You probably already realize intuitively that if language L is undecidable, then the complement of L is also undecidable. Prove this formally by showing that deciding L reduces to deciding L complement. (Hint: this can be a very short proof—if yours isn’t short, you may be overthinking the problem.)

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.