1. Let A be the language {s} containing only the single string s where
s = 0 if live will never be found on Mars, 1 otherwise
Note that at any point in time, s has a definite fixed value (that could be unknown to us).
Show that A is decidable.
2. Show that L is decidable iff L is recursively enumerable in the string order.
3. Let InfinityDFA = { : D is a DFA that accepts infinitely many strings }. Show that InfinityDFA is decidable.
4. Show that the following language is decidable.
L = { : D is a DFA that accepts reverse(w) whenever it accepts w}.
5. Show that the complement of this language is recognizable.
ETM = { : M is a TM that does not accept any string}.