Homework 9

Last updated: Wed, 14 Apr 2021 15:30:02 -0400

Out: Mon April 12, 00:00 EST Due: Sun April 18 Tues April 20, 23:59 EST

This homework covers material from Chapter 5 of the textbook.

Homework Problems

1. Complement and Undecidability (6 points)

2. TMs That Accept CFLs (6 points)

3. A_TM vs E_TM (6 points)

4. Rice’s Theorem (6 points)

5. More Undecidable Languages (6 points)

6. README (2 points)

Total: 32 points

Submitting

Submit this assignment at Gradescope hw9.

1 Complement and Undecidability

Show that if a language A is undecidable, then its complement \overline{A} is undecidable.

2 TMs That Accept CFLs

Show that the following language is undecidable:

\textrm{CONTEXTFREE}_{TM} = \{\left\langle M\right\rangle\mid M \textrm{ is a TM and } L(M)\textrm{ is a CFL}\}

Prove it using proof by contradiction.

3 A_TM vs E_TM

Recall the language E_{TM} = \{\left\langle M\right\rangle\mid M\textrm{ is a TM and }L(M)=\emptyset\}

We proved undecidability of E_{TM} in class by showing that A_{TM} is mapping reducible to the complement of E_{TM}, i.e., A_{TM}\leq_m\overline{E}_{TM}, and then applying theorem 5.23, and also the closure property proved in Complement and Undecidability.

It turns out that even though E_{TM} is undecidable, it is co-Turing recognizable. In other words, \overline{E}_{TM} is Turing recognizable. This intuitively makes sense because \overline{E}_{TM} is the set of all Turing machines whose languages are not empty. So we could create easily create a recognizer that checked every string until it found one that was accepted.

Use the fact that E_{TM} is co-Turing recognizable to prove that we could not have proven undecidability of E_{TM} by directly showing that A_{TM}\leq_m E_{TM}, because it is not true!

Use a proof by contradiction.

4 Rice’s Theorem

In class, we noticed a pattern that almost every language involving Turing machines is undecidable. Specifically, we cannot decide any properties about the language that a Turing machine accepts.

This is called Rice’s Theorem, which states that all languages P that satisfy the following conditions are undecidable:

• P is not the empty set;

• P consists of only valid Turing machine descriptions;

• P is not the set of all Turing machine descriptions;

• and whether a Turing machine is in P is determined by examining the language of that Turing machine, i.e., P has the form: \{\left\langle M\right\rangle\mid \ldots M \textrm{ is a TM and }\ldots\textrm{ something about }L(M) \ldots\}

Prove Rice’s Theorem.

In other words, prove that all languages P that satisfy the above criteria are undecidable. You may assume that you know how to construct a Turing machine that is in any given P.

5 More Undecidable Languages

Prove that the following languages are undecidable:

1. L_1 = \{\left\langle M\right\rangle\mid M\textrm{ is a \textsf{TM} and } \texttt{"CS420 rules!"}\in L(M)\}

2. L_2 = \{\left\langle M\right\rangle\mid M\textrm{ is a \textsf{TM} and } L(M) \textrm{ is the set of all Rust programs}\}

3. L_3 = \{\left\langle M\right\rangle\mid M\textrm{ is a \textsf{TM} and } L(M) \textrm{ consists of C++ malware that installs bitcoin miners on your computer}\}

UPDATE: For this question, you may use any previous theorems from class or the hws, so you might not necessarily need to do the typical proof by contradiction.