History of The Church–Turing Thesis - Gandy: "machine Computation", Discrete, Deterministic, and Limited To "local Causation" By Light Spe

Gandy: "machine Computation", Discrete, Deterministic, and Limited To "local Causation" By Light Spe

Robin Gandy's influential paper titled Church's Thesis and Principles for Mechanisms appears in Barwise et al. Gandy starts off with an unlikely expression of Church's Thesis, framed as follows:

"1. Introduction
"Throughout this paper we shall use "calculable" to refer to some intuitively given notion and "computable" to mean "computable by a Turing machine"; of course many equivalent definitions of "computable" are now available.
"Church's Thesis. What is effectively calculable is computable.
" ... Both Church and Turing had in mind calculation by an abstract human being using some mechanical aids (such as paper and pencil)"

Robert Soare (1995, see below) had issues with this framing, considering Church's paper (1936) published prior to Turing's "Appendix proof" (1937).

Gandy attempts to "analyze mechanical processes and so to provide arguments for the following:

"Thesis M. What can be calculated by a machine is computable."

Gandy "exclude from consideration devices which are essentially analogue machines ... .The only physical presuppositions made about mechanical devices (Cf Principle IV below) are that there is a lower bound on the linear dimensions of every atomic part of the device and that there is an upper bound (the velocity of light) on the speed of propagation of change". But then he restricts his machines even more:

"(2) Secondly we suppose that the progress of calculation by a mechanical device may be described in discrete terms, so that the devices considered are, in a loose sense, digital computers.
"(3) Lasty we suppose that the device is deterministic: that is, the subsequent behavior of the device is uniquely determined once a complete description of its initial state is given."

He in fact makes an argument for this "Thesis M" that he calls his "Theorem", the most important "Principle" of which is "Principle IV: Principle of local causation":

"Now we come to the most important of our principles. In Turing's analysis the requirement that the action depended only on a bounded portion of the record was based on a human limitation. We replace this by a physical limitation which we call the principle of local causation. Its justification lies in the finite velocity of propagation of effects and signals: contemporary physics rejects the possibility of instantaneous action at a distance."

Read more about this topic:  History Of The Church–Turing Thesis

Famous quotes containing the words local, causation, limited, light and/or machine:

    [Urging the national government] to eradicate local prejudices and mistaken rivalships to consolidate the affairs of the states into one harmonious interest.
    James Madison (1751–1836)

    The very hope of experimental philosophy, its expectation of constructing the sciences into a true philosophy of nature, is based on induction, or, if you please, the a priori presumption, that physical causation is universal; that the constitution of nature is written in its actual manifestations, and needs only to be deciphered by experimental and inductive research; that it is not a latent invisible writing, to be brought out by the magic of mental anticipation or metaphysical mediation.
    Chauncey Wright (1830–1875)

    ...women were fighting for limited freedom, the vote and more education. I wanted all the freedom, all the opportunity, all the equality there was in the world. I wanted to belong to the human race, not to a ladies’ aid society to the human race.
    Rheta Childe Dorr (1866–1948)

    Think what a mean and wretched place this world is; that half the time we have to light a lamp that we may see to live in it. This is half our life. Who would undertake the enterprise if it were all?
    Henry David Thoreau (1817–1862)

    Goodbye, boys; I’m under arrest. I may have to go to jail. I may not see you for a long time. Keep up the fight! Don’t surrender! Pay no attention to the injunction machine at Parkersburg. The Federal judge is a scab anyhow. While you starve he plays golf. While you serve humanity, he serves injunctions for the money powers.
    Mother Jones (1830–1930)