Procedures
Last Update: Wednesday, 2 November 2022 |
Note 1: Many of these items are online; links are given where they are known. Other items may also be online; an internet search should help you find them.
Note 2: In general, works are listed in chronological order. (This makes it easier to follow the historical development of ideas.)
§10.2: The Church-Turing Computability Thesis:
Gandy goes on to be concerned with a mechanical version of the
Thesis: whether "What can be calculated by a machine is computable"
(Gandy 1980,
p. 124), where by 'machine' he says that he is …
One difference between a human
(even an "abstract" one) and a machine is that the latter can easily
perform parallel operations such as printing "an arbitrary number of
symbols simultaneously"
(Gandy 1980,
p. 125).
For discussion of Gandy's Thesis, see
Shagrir 2022,
§3.1.
§10.4: Carol Cleland: Some Effective Procedures Are Not Turing Machines:
§10.5: Beth Preston: Recipes, Algorithms, and Specifications:
"What is effectively calculable ["by an abstract human being using
some mechanical aids (such as paper and pencil)"] is computable …
[where] "computable" … mean[s] "computable by a Turing
machine"[,] … "abstract" indicates that the argument makes no
appeal to the existence of practical limits on time and space … [and]
"effective" in the thesis serves to emphasize that the process of calculation is
deterministic — not dependent on guesswork — and that it must
terminate after a finite time."
(Gandy 1980,
pp. 123–124, my italics)
"… using the term with its nineteenth century meaning; the reader may
like to imagine some glorious contraption of gleaming brass and polished
mahogany, or he [sic] may choose to inspect the parts of Babbage's
"Analytical Engine" which are preserved in the Science Museum at South
Kensington."
(Gandy 1980,
p. 125)
Copyright © 2022 by
William J. Rapaport
(rapaport@buffalo.edu)
http://www.cse.buffalo.edu/~rapaport/OR/A0fr10.html-20221102