Universal Machines and Undecidability
摘要
Turing’s universal machine is constructed and used to prove the undecidability of the Halting Problem and the undecidability of validity in first-order logic. We include a brief discussion of the Recursion Theorem.