1. Suppose ATM is decidable. Describe how to decide HALT under this assumption.

2. L1 = { <M> : M, given empty string as input, at some point writes any non-blank symbol }. Is L1 decidable?

3. Show that EQ-CFG = {<G1,G2> : G1 and G2 are CFGs such that L(G1)=L(G2) } is in co-RE. Hint: Try to use a non-deterministic machine.

4. Program P spreads a virus on input F if running P under operating system OS
on input F alters OS. Otherwise it is safe on input F. P is safe if it is safe for all inputs.

Let IsSafe be an antivirus program. IsSafe(P,F) = yes iff P is safe on F.
Construct program EvilVirus(P) : if IsSafe(P,P)=no, draw :-); else alter OS

Suppose EV(EV) draws :-)... Then?
Suppose EV(EV) alters OS... Then?

Conclude that either IsSafe is not safe or is not correct.

This is from an AMS article by Downing (1989) where he claimed that no program can both test its input for the presence of a virus and simultaneously be guaranteed not to spread a virus itself.