Due: Thursday, Oct. 31
Show that language {p | p is a program that halts on all inputs} is uncomputable.
Is the set {M | M is a DFA that accepts the empty string} computable? Explain.
Is the set {G | G is a context-free grammar that can generate the empty string} computable? Explain.
Is the set {p | p is a Turing machine program that stops and answers yes when its input is the empty string} computable? Explain.
Show that the <=m relation on languages is transitive. That is, show that if A <=m B and B <=m C then A <=m C.