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 (1839–1894)
“He who has never failed somewhere, that man can not be great. Failure is the true test of greatness. And if it be said, that continual success is a proof that a man wisely knows his powers,—it is only to be added, that, in that case, he knows them to be small.”
—Herman Melville (1819–1891)