Turing's Proof - Summary of The Second Proof

Summary of The Second Proof

Less than one page long, the passage from premises to conclusion is obscure.

Turing proceeds by reductio ad absurdum. He asserts the existence of a machine E, which when given the S.D (standard description, i.e. "program") of an arbitrary machine M, will determine whether M ever prints a given symbol (0 say). He does not assert that this M is a "computing machine".

Given the existence of machine E, Turing proceeds as follows:

1. If machine E exists then a machine G exists that determines if M prints 0 infinitely often, AND
2. If E exists then another process exits that determines if M prints 1 infinitely often, THEREFORE
3. When we combine G with G' we have a process that determines if M prints an infinity of figures, AND
4. IF the process "G with G'" determines M prints an infinity of figures, THEN "G with G'" has determined that M is circle-free, BUT
5. This process "G with G'" that determine if M is circle-free, by proof 1, cannot exist, THEREFORE
6. Machine E does not exist.