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)
“Sculpture and painting are very justly called liberal arts; a lively and strong imagination, together with a just observation, being absolutely necessary to excel in either; which, in my opinion, is by no means the case of music, though called a liberal art, and now in Italy placed even above the other two—a proof of the decline of that country.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)