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:
“I have simplified my politics into an utter detestation of all existing governments; and, as it is the shortest and most agreeable and summary feeling imaginable, the first moment of an universal republic would convert me into an advocate for single and uncontradicted despotism. The fact is, riches are power, and poverty is slavery all over the earth, and one sort of establishment is no better, nor worse, for a people than another.”
—George Gordon Noel Byron (1788–1824)
“The chief contribution of Protestantism to human thought is its massive proof that God is a bore.”
—H.L. (Henry Lewis)