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> : D is a DFA that accepts infinitely many strings }. Show that InfinityDFA is decidable.

4. Show that the following language is decidable.
L = { <D> : D is a DFA that accepts reverse(w) whenever it accepts w}.

5. Show that the complement of this language is recognizable.
ETM = { <M> : M is a TM that does not accept any string}.