Homework 6

Last updated: Thu, 4 Nov 2021 14:27:01 -0400

Out: Mon Oct 25, 00:00 EST Due: Sun Oct 31 Wed Nov 3, 23:59 EST

This assignment explores decidability and undecidability.

Homework Problems

1. Am I Uncountable? (8 points)

2. Build-A-Decider (8 points)

3. The Proof of Rice’s Theorem (3 + 3 points)

4. I Can’t Decide (8 points)

5. I Still Can’t Decide (8 points)

6. README (2 point)

Total: 40 points

Submitting

Submit your solution to this assignment in Gradescope hw6. Please assign each page to the correct problem.

A submission must include a README containing the required information, in addition to the solution to the problems.

1 Am I Uncountable?

The natural numbers is the set of all non-negative integers, i.e., 0, 1, 2, ...

The power set of a set is the set of all subsets of that set.

Prove that the power set of the natural numbers is uncountable. Use diagonalization.

2 Build-A-Decider

Prove that the following language L is decidable:

L = \left\{\left\langle D\right\rangle\mid D \textrm{ is a DFA that accepts all strings with at least three 1s}\right\}

3 The Proof of Rice’s Theorem

In class, we proved Rice’s Theorem, which says that any language of the following form is undecidable:

ANYTHING_\textsf{TM} = \left\{\left\langle M\right\rangle\mid M\textrm{ is a TM and ... }\textbf{anything}\textrm{ ... about }L(M)\right\}

1. In the proof from class, why must we assume that the TM that rejects all inputs is not in ANYTHING_\textsf{TM}?

2. Why is it ok to make this assumption?

4 I Can’t Decide

Prove that the following language is undecidable:

SUB_{CFG} = \left\{\left\langle G_1, G_2\right\rangle\mid G_1 \textrm{ and } G_2\textrm{ are CFGs where } L(G_1) \subseteq L(G_2)\right\}

5 I Still Can’t Decide

Prove that the following language is undecidable. You may not use Rice’s Theorem.

A_{\texttt{CS622}} = \left\{\left\langle M\right\rangle\mid M\textrm{ is a TM and }\texttt{CS622}\in L(M)\right\}