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:
- If machine E exists then a machine G exists that determines if M prints 0 infinitely often, AND
- If E exists then another process exits that determines if M prints 1 infinitely often, THEREFORE
- When we combine G with G' we have a process that determines if M prints an infinity of figures, AND
- 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
- This process "G with G'" that determine if M is circle-free, by proof 1, cannot exist, THEREFORE
- Machine E does not exist.
Read more about this topic: Turing's Proof
Famous quotes containing the words summary and/or proof:
“Product of a myriad various minds and contending tongues, compact of obscure and minute association, a language has its own abundant and often recondite laws, in the habitual and summary recognition of which scholarship consists.”
—Walter Pater (18391894)
“The proof of a poet is that his country absorbs him as affectionately as he has absorbed it.”
—Walt Whitman (18191892)