Philosophy of Computer Science: Online Resources

Further Readings for Chapter 10:

Procedures

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:

• Good general discussions of the various Computability Theses (Church's, Turing's, et al.) and their history can be found in:
  • Special Issue on Church's Thesis, Notre Dame Journal of Formal Logic 28(4) (October 1987)

  • Sieg 1994, §§2–3.

  • Davis 2004

  • Olszewski, A., Woleński, J., and Janusz, R., editors (2006). Church's Thesis after 70 Years. Ontos Verlag, Frankfurt.
    • Includes essays by Selmer Bringsjord, Carol Cleland, B. Jack Copeland, Janet Folina, Yuri Gurevich, Andrew Hodges, Charles McCarty, Elliott Mendelson, Oron Shagrir, Stewart Shapiro, and Wilfrid Sieg, among many others

  • Soare 2009, §§2, 3, and 12 ("Origins of Computabilty and Incomputability", "Turing Breaks the Stalemate", and "Renaming It the 'Computability Thesis'")

  • Copeland, B. J. and Shagrir, O. (2019). The Church-Turing thesis: Logical limit or breachable barrier? Communications of the ACM, 62(1):66–74.

  • Boker, U., Dershowitz, N. (2022). What is the Church-Turing Thesis?. In: Ferreira, F., Kahle, R., Sommaruga, G. (eds), Axiomatic Thinking II. Springer, Cham.

• Kripke, S.A. (2013). The Church-Turing "thesis" as a special corollary of Gödel's completeness theorem. In Copeland, B.J., Posy, C.J., and Shagrir, O., editors, Computability: Turing, Gödel, Church, and Beyond, pages&nbs;p;77–104. MIT Press, Cambridge, MA.
  • Contains a lot of useful historical remarks and offers an argument that the Thesis can be proved as a corollary of Gödel's Completeness Theorem.

• On the other hand, Folina 1998 argues — against Gandy 1988, Mendelson 1990, Stewart Shapiro 1993, Sieg 1994, and others — that the thesis is true but unprovable (perhaps as in Gödel's Incompleteness Theorem?). See also:
  • Sieg, W. (2000). Calculations by man and machine: Conceptual analysis. Technical Report CMU-PHIL-104, Carnegie-Mellon University Department of Philosophy, Pittsburgh, PA.

  • Sieg 2008

• Stewart Shapiro 2013 is a very readable discussion of the provability of the Computability Thesis; of the nature of the "informality", "vagueness", or "open texture" of the notion of computability; and of the difference between human, mechanical, and mathematical computability, with observations on many of the other readings discussed or mentioned in this chapter.

• Mendelson 1990 has one of the clearest discussions of the nature of the Computability Thesis.
  • For responses to Mendelson, see Bringsjord 1993 and Stewart Shapiro 1993.

• Robin Gandy — Turing's only Ph.D. student — gave this statement of what (ironically) he referred to as Church's Thesis:
  "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)

  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 …

  "… 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)

  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.

• On physical versions of the Computability Thesis, see Piccinini and Maley 2021

• On the Computability Thesis and AI, see:
  • Kearns, J. (1997). Thinking machines: Some fundamental confusions. Minds and Machines, 7(2):269 287,
    • Argues that the Computability Thesis "has no interesting consequences for human cognition" because "carrying out a procedure is a purposive, intentional activity. No actual machine does, or can do, as much."

  • Abramson, D. (2011). Philosophy of mind is (in part) philosophy of computer science. Minds and Machines, 21:203–219.
    • Argues that the Computability Thesis is relevant to questions about the Turing Test for AI.

• Rey, G. (2012). The Turing thesis vs. the Turing test. The Philosopher's Magazine, 57:84 89.
  • Distinguishes the Turing Thesis from the Turing Test.

§10.4: Carol Cleland: Some Effective Procedures Are Not Turing Machines:

• Cleland's arguments a lengthy debate:
  • Horsten, L. and Roelants, H. (1995). The Church-Turing thesis and effective mundane procedures. Minds and Machines, 5(1):1–8.

  • Cleland, C.E. (1995). Effective procedures and computable functions. Minds and Machines, 5(1):9–23.

  • Cleland, C.E. (2001). Recipes, algorithms, and programs. Minds and Machines, 11(2):219–237.

  • Cleland, C.E. (2002). On effective procedures. Minds and Machines, 12(2):159–179.

  • Israel, D. (2002). Reflections on Gödel's and Gandy's reflections on Turing's thesis. Minds and Machines, 12(2):181–201.

  • Seligman, J. (2002). The scope of Turing's analysis of effective procedures. Minds and Machines, 12(2):203–220.

• Other articles on the issues appear in:
  • Cleland, C.E., editor (2002, May). Effective Procedures. Special Issue of Minds and Machines 12(2).

  • Wells, B. (2004). Hypercomputation by definition. Theoretical Computer Science, 317:191–207.
    • §2 contains a discussion of Cleland 1995 and Cleland 2001, in addition to remarks on the relation between the Computability Thesis and the P=NP problem.

§10.5: Beth Preston: Recipes, Algorithms, and Specifications:

• On the notion of a "specification" (the general requirements for an algorithm), see:
  • Turner, R. (2011). Specification. Minds and Machines, 21(2):135–152.

• Petroski, H. (2010). Occasional design. American Scientist, 98(1):16–19.
  • A nice follow-up to Preston, in which he describes how "an everyday challenge provides lessons in the processes of planning and execution".

• Daly, I. (2010, 24 February). Just like mombot used to make. New York Times, pages D1, D5.
  • About robots that not only follow recipes, but actually cook the meals ("Fear not, humans, these robots are here to be our friends. To prove it, they serve you food").
  • Interesting reading in connection with what both Cleland and Preston have to say about the computability of recipes.