- Show that the language $ALLTM
$, defined as $ \{M | \text{ where } M \text{ is a TM and } L(M) = Σ^*\}$, is undecidable. - A useless state in a Turing machine is defined as a state that is never entered by the machine on any input. Consider the problem of detecting if a Turing machine has a useless state. Formulate this problem as a language and show that the language is undecidable.
- If
$A ≤_m B$ and$B$ is a regular language, is$A$ necessarily a regular language? Justify your answer. - Let
$B$ be a decidable language with$B ≠ ∅$ and$B ≠ Σ^*$ , then if$A$ is decidable define a computational reduction$A ≤_m B$ . - (from Sipser) Let Double-SAT be the language { φ | φ has at least two satisfying assignments }. Show, by polynomial time reduction, that Double-SAT is NP-complete.