10
$\begingroup$

Robin Gandy was a student of Alan Turing.

Gandy did an analysis of Babbage's Analytical Engine (see 'Gandy - The Confluence of Ideas in 1936' quoted in 'Herken, Rolf - The Universal Turing Machine—A Half-Century Survey. Springer Verlag') - and said it did (cf. p. 52–53):

  1. The arithmetic functions +, −, ×, where − indicates "proper" subtraction x − y = 0 if y ≥ x.
  2. Any sequence of operations is an operation.
  3. Iteration of an operation (repeating n times an operation P).
  4. Conditional iteration (repeating n times an operation P conditional on the "success" of test T).
  5. Conditional transfer (i.e., conditional "goto").

Then he states

the functions which can be calculated by (1), (2), and (4) are precisely those which are Turing computable.

(p. 53).

Then he states:

… the emphasis is on programming a fixed iterable sequence of arithmetical operations. The fundamental importance of conditional iteration and conditional transfer for a general theory of calculating machines is not recognized…

Gandy p. 55

I'm assessing the scope of Gandy's claim here. (Whether it is right or wrong). He seems to be stating that although Babbage seems to have stumbled onto a notion of Turing Completeness (can express any program using (1), (2) and (4) - he didn't have a notion of a Computable Function. (Perhaps Gandy was saying that since the work of Babbage was prior to the work of Hilbert and Godel, he didn't have the mathematical tools to tie down the definition of a universal computing machine.)

My question is: Did Alan Turing's student Robin Gandy assert that Charles Babbage had no notion of a universal computing machine?

$\endgroup$
  • 2
    $\begingroup$ Note there is also a history of science and math stackexchange hsm.stackexchange.com $\endgroup$ – usul Sep 3 '19 at 14:48
  • $\begingroup$ I'm a little confused by the page referencing. If all page numbers are Gandy's, perhaps it would be more clear to say "(Gandy, pp. 52-53)", (Gandy, p. 53)", and (Gandy, p. 55)". For any excerpts that are quoted in Rolf, the attribution could be expanded as (Gandy, p. 5x; as quoted in Rolf, p. xx)". "Cf." is short for Latin confer/conferatur ("compare"), meaning "go see also this other thing for comparison or contrasting", so it doesn't make sense to say that for the main thing you're quoting. $\endgroup$ – Jacob C. says Reinstate Monica Sep 3 '19 at 22:30
21
$\begingroup$

No, the opposite. This quote of Gandy's is not referring to Babbage, but to some intervening proposals for universal-style computing between Babbage and Turing. Gandy says those proposals did not have Babbage's recognition of the importance of branching and iteration to universal computation.


In "The Confluence of Ideas in 1936" by Gandy, as printed in the book "The Universal Turing Machine - A Half Century Survey", Section 2 is "Babbage and His Followers".

Here Gandy emphasizes that Babbage did understand and respect "conditional iteration" and "conditional transfer", e.g. end of p53 and top of p54

Although Babbage mentions conditional transfer (67-68), he, with a natural respect for well-structured programming, uses only conditional iteration[....] He states conditional transfer explicitly (240), allowing that a 'go to' instruction may have to be executed by ringing a bell to summon the attendant; he gives an example of its use (241).

(Here Gandy refers to the article by Menabrea 1842 on Babbage's engine, but seems to attribute the ideas to Babbage himself.)

Gandy then quotes Babbage

That the whole of the development and operations of analysis are now capable of being executed by machinery.

and writes

Babbage, in his work on general algebra and functional equations, had shown his ability to think in abstract terms. If, then, one had led him to speculate (not difficult!) on what could be done with an abstract machine, free from limitations on its storage, he would surely have assented to a version (based on Sections 2.1.(1)-(5)) of Church's thesis.

Then Gandy goes on to Section 2.3, "Subsequent developments." He writes

Other authors, concerned with more practical machines, referred to Babbage's work. Examples from Ran- dell 1982 are: M. d'Ocagne [1922], L. Couffignal [1933], V. Bush 1936, H.H. Aiken 11964] (which is an unpublished memorandum of 1937). But the emphasis is on programming a fixed iterable sequence of arithmetical operations. The fundamental importance of conditional iteration and conditional transfer for a general theory of calculating machines is not recognized, though the principles may be used in very particular contexts [....]

Finally, Gandy writes:

Conclusions. Babbage asserted what was, in effect a version of Church's thesis. His work was never entirely forgotten, but its theoretical importance - its importance, so to speak, as software - was little recognized[....]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.