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.

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)

    “There is no better proof of a man’s being truly good than his desiring to be constantly under the observation of good men.”
    —François, Duc De La Rochefoucauld (1613–1680)