Lecture 17 (Computation Theory) Reducibility and Undecidable Problems

In the proof that A_TM is undecidable, the machine D is constructed to do what when fed an input ⟨M⟩?

1. A.Run ⟨M⟩, ⟨M⟩ on H and output the OPPOSITE of what H says
2. B.Simulate M on its own description and accept iff M halts
3. C.Enumerate every string M accepts and reject if the list is finite
4. D.Check that M is a decider before passing ⟨M⟩ to H