Philosophy of Computer Science: Online Resources

Further Readings for Chapter 8:

Turing's Analysis of Computation

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.)

§8.1: Introduction:

• A wonderful guide to reading all of Turing 1936 slowly and carefully is:
  • Petzold, C. (2008). The Annotated Turing: A Guided Tour through Alan Turing’s Historic Paper on Computability and the Turing Machine. Wiley, Indianapolis.

• For a review of Petzold's book, see:
  • Davis, M.D. (2008). Touring Turing. American Scientist, 96(6):520.

"A 1923 play called The Adding Machine lampooned the monotony of assembly-line office work and prefigured fears about machine automation. Its main character, 'Mr. Zero,' writes down numbers all day long, 'upon a square sheet of ruled paper.'" (Lepore, J. (2018). These Truths: A History of the United States. W.W. Norton, New York, p. 404.)
• For more information on the play, by Elmer Rice, see "The Adding Machine" (Wikipedia)

§8.8.1: "Man" and "Machine":

• On Hilbert's idea:
  
  • For the origin of Hilbert's observation about tables, chairs, and beer mugs, see the letter from Irving H. Anellis, responding to a query I made on a newsgroup.
    

  • Elsewhere, Hilbert used a different example:
    "… it is surely obvious that every theory is only a scaffolding or schema of concepts together with their necessary relations to one another, and that the basic elements can be thought of in any way one likes. If in speaking of my points, I think of some system of things, e.g., the system: love, law, chimney-sweep … and then assume all my axioms as relations between these things, then my propositions, e.g., Pythagoras' theorem, are also valid for these things … [A]ny theory can always be applied to infinitely many systems of basic elements."
    (My boldface. Quoted on p. 168 of:
    Shapiro, Stewart (2013). The open texture of computability. In Copeland, B.J., Posy, C.J., and Shagrir, O., editors, Computability: Turing, Gödel, Church, and Beyond, pages 153–181. MIT Press, Cambridge, MA.)

  • See also Shapiro, Stewart (2009). We hold these truths to be self-evident: But what do we mean by that? Review of Symbolic Logic, 2(1):175–207.

  • Excellent discussions of this kind of abstraction can be found in:
    • Cohen, M.R. and Nagel, E. (1934). An Introduction to Logic and Scientific Method. Harcourt, Brace and Co., New York, Ch. 7, "The Nature of a Logical or Mathematical System".

    • Hempel, C. G. (1945). Geometry and empirical science. American Mathematical Monthly, 52(1):7–17.

• On Turing's claim that "by altering its m-configuration the machine can effectively remember some of the symbols which it has "seen" (scanned) previously", see:
  • Sieg, W. (2008), On computability. In Irvine, A. (ed.), Philosophy of Mathematics. Oxford, Elsevier, pp. 525–621, esp. p. 575, footnote 35; and pp. 578–579, footnote 38

  • Dresner, E. (2003). Effective memory and Turing's model of mind. Journal of Experimental & Theoretical Artificial Intelligence, 15(1):113–123.

  • Dresner, E. (2012). Turing, Matthews and Millikan: Effective memory, dispositionalism and pushmepullyou states. International Journal of Philosophical Studies, 20(4):461–472.

• The Universal Turing Machine is covered in detail in:
  • Dewdney 1989, Chs. 1, 28, 48

  • Petzold 2008

  • Bernhardt 2016, Ch. 6.

  • §2.4 ("The Universal Turing Machine"; pp. 49–53) of:
    Mundici, Daniele; & Sieg, Wilfried (2017), "Turing, the Mathematician", in Juliet Floyd & Alisa Bokulich (eds.), Philosophical Explorations of the Legacy of Alan Turing: Turing 100 (Cham, Switzerland: Springer), Ch. 2, pp. 39–62.

• Another presentation, using the notion of a register machine, can be found in Dennett 2013, pp. 126–128.

• For a Common Lisp implementation of Turing's universal program as specified in Davis and Weyuker 1983, see:
  • Lammens, J. (1990). Universal program

• Davis 2012, p. 147, notes that "Turing's universal machine showed that the distinctness of these three catgories [machine, program, and data] is an illusion."

• In a fascinating paper on "programming in English":
  Hill, I.D. (1972), "Wouldn't It Be Nice If We Could Write Computer Programs in Ordinary English  —  Or Would it?", The Computer Bulletin (London: British Computer Society), 16(6) (June): 306–312

  the author writes:

  At least when a computer follows a ludicrous program, it is not itelf (so far as we know) aware of what it is doing. (p. 310, col. 1)

  'Aware', of course, is an anthropomorphic term (though one that might be used with Large Language Models such as ChatGPT). But even if we use it in a more neutral sense, we might say that a Turing Machine is not "aware" of its own program, but a Universal Turing Machine  — although not "aware" of its own fetch-execute program  —  is "aware" of the program that it is fetching and executing.

§8.14: Further Information on Turing:

• Turing's Writings:
  1. As if creating computer science (Turing 1936), helping to win World War II (see §6.4.4), and writing one of the first papers on artificial intelligence (Turing 1950) wasn't enough, Turing also had an interest in such questions as why zebras have the kinds of stripes that they do(!) — see:
     • Turing, A.M. (1952). The chemical basis of morphogenesis. Philosophical Transactions of the Royal Society of London, Series B, Biological Science, 237(641):37 72
       • This paper "laid the groundwork for the entire field of mathematical biology", according to geneticist Gregory S. Barsh, as quoted in Gorman, J. (2021, 7 September). How the cat gets its stripes: It's genetics, not a folk tale. New York Times.

     See also:

     • Billock, V.A. and Tsou, B.H. (2010, February). Seeing forbidden colors. Scientific American, 302(2):72–77, esp. pp. 75–76.

  2. Turing's last essay before his death:
     • Turing, A.M. (1954). Solvable and unsolvable problems. Science News, 31:7

     is a fascinating version of Turing 1936 aimed at a(n intelligent) general audience. In this article, he shows that many, if not most, puzzles can be put into a "kind of 'normal form' or 'standard form'" (p. 587) called a "substitution type of puzzle" (p. 588), which turns out to be essentially the notion of a formal system or a Turing Machine. He states a kind of "Turing's Thesis" for such puzzles, noting that such a …

     "… statement is moreover one which one does not attempt to prove. Propaganda is more appropriate to it than proof, for its status is something between a theorem and a definition. In so far as we know a priori what is a puzzle and what is not, the statement is a theorem. In so far as we do not know what puzzles are, the statement is a definition which tells us something about what they are." (p. 588).

     In this article, he also proves a version of the Halting Problem, in the sense that he proves "that there cannot be any systematic procedure for determining whether a puzzle be solvable or not" (p. 590).

     • For further discussion of Turing's essay, see Mundici & Sieg 2017, §2.2 ("Puzzles vs. Calculable Functions", pp, 41–46).

  3. Copeland, B. J., editor (2004). The Essential Turing. Oxford University Press, Oxford.
     • An anthology of Turing's papers.
     • Reviewed in:
       • Hodges, A. (2006). Review of Copeland 2004. Notices of the AMS, 53(10):1190–1199.

  4. Jack Copeland's website, "AlanTuring.net Reference Articles on Turing", contains a variety of interesting papers on various aspects of Turing's work, most written by Copeland, a well-respected contemporary philosopher, including essays on the Church-Turing Thesis and Turing Machines.

  5. Cooper, S.B. and van Leeuwen, J., editors (2013). Alan Turing: His Work and Impact. Elsevier, Amsterdam.
     • A large, "coffee table"-sized anthology of Turing's writings with commentaries by, among many others, Rodney Brooks, Gregory Chaitin, B. Jack Copeland, Martin Davis, Daniel Dennett, Luciano Floridi, Lance Fortnow, Douglas Hofstadter, Wilfried Sieg, Aaron Sloman, Robert I. Soare, and Stephen Wolfram.

     • Reviewed in:
       • Avigad, J. (2014). Review of Cooper and van Leeuwen 2013. Notices of the American Mathematical Society, 61(8):886–890.

  ---

• Biographical Information:
  1. Hodges, A. (2012). Alan Turing: The Enigma; Centenary Edition. Princeton University Press, Princeton, NJ.
     • The standard biography.
     • See also Hodges's "Alan Turing: The Enigma" website.

     • Reviews of the first edition of Hodges's biography can be found in:
       • Hofstadter, D.R. (1983, 13 November). Mind, body and machine. New York Times Book Review.

       • Toulmin, S. (1984, 19 January). Fall of a genius. New York Review of Books, pages 3–4, 6.
         • See also:
           Stern, H. and Daston, L. (1984). Turing & the system. New York Review of Books, pages 52–53, with a reply by Toulmin.

       • Bernstein, J. (1986, 20 January). A portrait of Alan Turing. The New Yorker, pages 78, 81–87.

  2. Fitzsimmons, E.G. (2013, 24 December). Alan Turing, Enigma code-breaker and computer pioneer, wins royal pardon. New York Times.
     • Discusses the British pardon of Turing for his "crime" of being homosexual.

  ---

• Dramatizations:
  1. Whitemore, H. (1966). Breaking the Code. Samuel French Inc., 2010
     • A play, later made into a superb film.
     • The play is excerpted in:
       • Whitemore, H. (1988). The Enigma: Alan Turing confronts a question of right and wrong. The Sciences, 28(2):40–41)

  2. Enigma, a 2001 film, is of interest if only because this fictionalized version omits Turing!

  3. Another film, Codebreaker: The Story of Alan Turing (2011), is half dramatization, half documentary, with interviews of people who knew Turing (including some who are fictionalized in The Imitation Game).

  4. The most recent Hollywood treatment, rather controversial because of the many liberties it took with the facts, is The Imitation Game (2014).

     Several websites offer background and critiques of the film:

     • "The Imitation Game: The Philosophical Legacy of Alan Turing", The Critique (31 December 2014).

     • Woit, P. (2014, 19 November). The Imitation Game. Not Even Wrong.

     • von Tunzelmann, A. (2014, 20 November). The Imitation Game: Inventing a new slander to insult Alan Turing. The Guardian.

     • Anderson, L.V. (2014, 3 December). How accurate is The Imitation Game? Slate.

     • Caryl, C. (2015, 5 February). Saving Alan Turing from his friends. New York Review of Books, pages 19–21.

  ---

• Turing's Legacy:
  1. Copeland, B.J. and Proudfoot, D. (1996). On Alan Turing's anticipation of connectionism. Synthese, 108:361–377.
     • Observes that "Turing was probably the first person to consider building computing machines out of simple, neuron-like elements connected together into networks in a largely random manner. … By the application of what he described as 'appropriate interference, mimicking education' … [such a] machine can be trained to perform any task that a Turing machine can carry out …" (p. 361).

  2. American Mathematical Society, editor (2006). Alan Turing. Special issue of Notices of the AMS 53(10) (November).
     • Includes articles by Andrew Hodges, Solomon Feferman, S. Barry Cooper, and Martin Davis, among others.

  3. Soare 2013 compares Turing and Church to Michelangelo and Donatello, respectively.
     • The illustrations are at "The Art of Classical Computability").

  4. Daylight, E.G. (2013). Towards a historical notion of "Turing — the father of computer science"
     • Argues from historical evidence that the reasons that Turing is considered "the father of computer science" have nothing to do with his involvement in computer design or construction.

  5. Daylight, E.G. (2014). A Turing tale. Communications of the ACM, 57(10):36–38.
     • "assess[es] the accuracy of popular descriptions of Alan Turing's influences and legacy" (p. 36).

  6. Haigh, T. (2014). Actually, Turing did not invent the computer. Communications of the ACM, 57(1):36–41
     • Discusses the role of the Turing Machine in the history of computers, minimizing its historical importance to the actual development of computing machines.

  7. Bullynck, M., Daylight, E.G., and Mol, L. (2015). Why did computer science make a hero out of Turing? Communications of the ACM, 58(3):37–39

  8. Other evaluations include:
     • Robinson1994

     • Sieg 1994, §3.

     • Kleene 1995

     • Leiber, J. (2006). Turing's golden: How well Turing's work stands today. Philosophical Psychology, 19(1):13–46.

     • Michie, D. (2008). Alan Turing's mind machines. In Husband, P., Holland, O., and Wheeler, M., editors, The Mechanical Mind in History, Ch. 4, pp. 61–74. MIT Press, Cambridge, MA.

     • Copeland, B.J. (2012). Is Alan Turing both inventor of the basic ideas of the modern computer and a pioneer of artificial intelligence? Big Questions Online.

     • Copeland, B.J. (2013). What Apple and Microsoft owe to Turing. Huff[ington] Post Tech/The Blog.

     • Vardi, M.Y. (2013). Who begat computing? Communications of the ACM, 56(1):5.

     • Vardi 2017

  ---

• Pedagogy:
  1. On Turing Machines and pedagogy, see:
     • Schagrin et al. 1985, "Turing Machines", Appendix B, pp. 327–339.

     • Tymoczko, T. and Goodhart, S. (1986). From logic to computers: A suggestion for logic teachers. Teaching Philosophy, 9(1):15–33.

     • Suber, P. (1997a). Turing machines.

     • Suber 1997b

     • Michaelson, G. (2012). A visit to the Turing machine: A short story. CS4FN: Computer Science for Fun, 14.

     • Lodder, J. (2014). Introducing logic via Turing machines.

  2. Other Turing Machine exercises are at Teaching Discrete Mathematics via Primary Historical Sources

  ---

• Implementations of Turing Machines:

  There are several Turing Machine simulators and implementations, some quite curious:

  1. Curtis, M. (1965). A Turing machine simulator. Journal of the ACM, 12(1):1–13.
     • Contains a program written for the IBM 1620, designed for education purposes.

  2. Weizenbaum 1976, Ch. 2, "Where the Power of the Computer Comes From".
     • Contains a masterful presentation of a Turing Machine implemented with pebbles and toilet paper!
     • This is also an excellent book on the role of computers in society, by the creator of the "Eliza" AI program.

  3. Two implementations of Turing Machines using subway trains and railroad trains, respectively:
     • Stewart, I. (1994, September). A subway named Turing. Scientific American, pages 104, 106–107

     • Hayes, B. (2007). Trains of thought. American Scientist, 95(2),

  4. Implementations of Turing Machines in John Conway's Game of Life:
     • Rendell, P. (2000). This is a Turing Machine implemented in Conway's Game of Life;
     • Rendell, P. (2001). A Turing Machine In Conway's Game Life;
     • Rendell, P. (2010). This is a Universal Turing Machine (UTM) implemented in Conway's Game of Life.

  5. Two physical implementations of Turing Machines (but with finite tapes!):
     • "[O]ne using servo motors, a Parallax Propeller, felt-tipped pen, and 1000 feet of film leader" is described at A Turing Machine in the Classic Style and at Turing Machine a Masterpiece of Craftsmanship.

     • A Turing Machine simulator app for iPhones and iPads is available at Turing — Turing Machine Simulator

  6. Two implementations on a business card!
     • Smith, A. R. (2014a). A business card universal Turing machine;
     • Smith, A. R. (2014b). Turingtoys.com

     For more information on the business-card Turing Machines, see:

     • Casselman, B. (2014). About the cover: Smart card. Notices of the AMS, 61(8):872.