Philosophy of Computer Science

Reading Assignments

Last Update: 21 April 2010

Note: NEW or UPDATED material is highlighted


Don't let this happen to you!


Notes:
  1. Reading assignments are listed in reverse chronological order.
  2. Many readings are accessible from "buffalo.edu" machines via the appropriate "Directory of Documents" webpages indicated below (next to "Topic").
  3. The username and password that may be required for some online readings will be announced in lecture. If you forget it, email Bill Rapaport.


  1. Assigned: 21 Apr 2010
    Topic:
    Philosophy of Computer Science

    1. Required:

      1. Smith 2002

    2. Recommended:

      1. DeJohn & Dietrich 2003, §3.1
      2. Scheutz 2002


  2. Assigned: 14 April 2010
    Topic:
    Computer Ethics (Part II)

    1. Required:

      1. LaChat 1986

    2. Very, Very Strongly Recommended:

      1. Lem 1971

    3. Strongly Recommended:

      1. Moor 1985

    4. Recommended:

      1. Dietrich 2001
      2. Turkle 2004
      3. Petersen 2007

    5. Someday :-)

      1. Powers 1995


  3. Assigned: 5 April 2010
    Topic:
    Philosophy of Artificial Intelligence

    1. Required:

      1. Turing 1950
      2. Searle 1980

    2. Recommended:

      1. Rapaport 2000


  4. Assigned: 2 April 2010
    Topic:
    Computer Ethics (Part I)

    1. Required:

      1. Moor 1979

    2. Strongly Recommended:

      1. Friedman & Kahn 1992

        • Can be read as raising an objection to Moor 1979,
          esp. the section "Delegating Decision Making to Computational Systems",
          pp. 306–307.

      2. Johnson 2002

        • An op-ed piece that provides an interesting counterexample to Friedman & Kahn 1992

    3. Recommended:

      • Any of the other documents listed along with Moor 1979.


  5. Assigned: 31 March 2010
    Topic:
    Can programs be verified?

    1. Highly Desired:

    2. Strongly Recommended:

      1. De Millo, Lipton, & Perlis 1979
        • The "prequel" to Fetzer 1988.
        • For an insight on how controversial even this paper was, see:
          Vardi, Moshe Y. (2010), "More Debate, Please!", Communications of the ACM 53(1) (January): 5.

      2. Ardis et al. 1989
        • The first of many sequels to Fetzer 1988.
        • This one includes a nasty letter to the editor of CACM signed by 10 computer scientists protesting the publication of Fetzer 1988, a reply by Fetzer, and a self-defense by the editor.

    3. Recommended:

      1. Any of McCarthy 1963, Naur 1966, Floyd 1967, or (especially) Hoare 1969
        • The 4 papers that started the field of program verification.

      2. Dijkstra 1975
        • An example of program verification in action.
        • For a classic textbook, see Gries 1981
        • For a course on the subject, petition to have CSE 451 taught!

      3. Any of Pleasant et al. 1989, Fetzer 1989, Dobson & Randell 1989, Müller et al. 1989, Hill et al. 1989, Tompkins 1989
        • The resulting battle.

      4. Barwise 1989
        • A cooler head prevails.

      5. Fetzer 1998
        • The last word?


  6. Assigned: 25 March 2010
    Topic: What is the program-world relationship?


  7. Assigned: 24 March 2010, but not covered in lecture.
    Topic: What is a computer program: Are computer programs scientific theories?

    1. Required:

      1. Carefully read the passages quoted from:

        1. Simon & Newell 1962
        2. Johnson-Laird 1981
        3. Pylyshyn 1984
        4. Johnson-Laird 1988

      2. Simon 1996
        • (originally written in 1969, updated in 1981)
        • This is a really good chapter that I probably should have had you read back when we were discussing whether computer science is a science.
          So read it now; it's never too late :-)

      3. Thagard 1984

    2. Very Strongly Recommended:

      1. Weizenbaum 1976

        • Ch. 5 is good on the nature of theories and models.
        • Ch. 6 is also good on computer programs as theories, on the potential evils of AI, and for his objections to Simon.
        • I would have required this had you not complained about too much reading ;-)

      2. Moor 1978, § 4 ("Models and Theories")

    3. Strongly Recommended:

      1. Read all of Weizenbaum's 1976 book! (someday)

      2. Simon & Newell 1956

        • Makes many of the same points as Simon 1996, but goes into a bit more detail on the nature of theories and models.

    4. Recommended:

      1. Wilks 1974/1990

          Has a useful, if sometimes confusing, overview of the many meanings of "theory" and "model".

      2. Daubert v. Merrell 1993 has interesting observations on the nature of scientific theories and expertise.

        • Prof. Sargur Srihari recommended this to me, after his experience being called as an expert witness on handwriting analysis, on the grounds that his computer programs that could recognize handwriting were scientific theories of handwriting analysis.

      3. Green 2004 has a useful survey of different views of scientific explanation and scientific models embedded in a discussion of connectionism.


  8. Assigned: 22 March 2010
    Topic:
    What is a computer program: What is implementation?

    1. Required:

      1. Chalmers 1993a:

        • read the "Long Abstract"
        • read §§1–2
        • skim the rest

      2. Rapaport 1999

        • You can read either the (shorter) published version (click on the "published version" link)
          or the (longer) online version (click on the title of the paper)

    2. Strongly Recommended:

      1. Putnam 1988
      2. Chalmers 1993b
      3. Read the rest of Chalmers 1993a
      4. Rapaport 2005

    3. Recommended:

      1. Suber 1997
      2. Suber 2002


  9. Assigned: 19 Mar 2010
    Topic:
    What is a computer program: Can programs be copyrighted or patented?

    1. Required:

      1. Newell 1985–1986

    2. Strongly Recommended:

      1. Samuelson 1990

    3. Recommended:

      1. Koepsell & Rapaport 1995
      2. Stallman, Richard (2010), "Copyright vs. Community".


  10. Assigned: 17 Mar 2010
    Topic:
    What is a computer program: What is software?

    1. Absolutely Required:

      • Moor 1978
        • Pay special attention to §§1–2;
          we'll return to §§3–4 later (just skim them now)

    2. (Merely) Required:

    3. Strongly Recommended:

    4. Recommended:


  11. Assigned: 5 Mar 2010
    Topic:
    What is hypercomputation?

    1. Required:

      1. Copeland (2002), "Hypercomputation":

        • Read pp. 461–465.
        • Read §1.5 (on Putnam & Gold)
        • Read §1.7 (on Boolos & Jeffrey)
        • Read §1.13 (on Kugel)
        • Read §1.18–1.18.1 (on Penrose, Turing, & Gödel)
        • Read §1.24 (on Cleland)
        • Read all of §§2–3

      2. Wegner 1997

      3. Kugel 2002

      4. Davis 2004

    2. Strongly Recommended:

      1. Read the sections of Copeland 2002 not explicitly listed above :-)

    3. Recommended:

      1. Eberbach & Wegner 2003
        • Another useful survey, but with some seriously misleading things to say about the nature of logic.

      2. On Putnam-Gold machines:

        1. John Case's COLT Page
          • Case is a former UB CSE faculty member.

        2. Nowak et al. 2002


  12. Assigned: 1 Mar 2010
    Topic:
    What is a procedure?

    1. Required:

      1. Cleland 1993
      2. Preston 2006

        • p. 3, from last paragraph, to p. 4, top 3 lines
          • introduces 3 theories of "production"
            (producing objects by following procedures):
            Aristotle's, Marx's, and Dipert's
        • §"Aristotle",
          • p. 4, paragraph 2.
        • §"Marx",
          • p. 8, from middle paragraph, to p. 9, end of top paragraph
        • §"Dipert",
          • p. 13, last paragraph.
        • §"Centralized Control Model", pp. 14–17.
        • §"CONTROL & IMPROVISATION", pp. 23–28.
        • Skim the rest.

    2. Strongly Recommended:

      1. Farkas 1999
      2. Read all of Preston 2006

    3. Recommended:

      1. Horsten & Roelants 1995
        • A reply to Cleland 1993
      2. Cleland 1995
        • A reply to Horsten & Roelants 1995
      3. Cleland 2001
      4. Cleland 2002


  13. Assigned: 19 Feb 2010
    Topic:
    What is a computer? (Part II: Philosophy)

    1. Required:

      1. Searle 1990
      2. P.Hayes 1997
      3. Lloyd & Ng 2004
      4. Weinberg 2002

    2. Strongly Recommended:

      1. Shagrir 2006

      2. At least one of:
        1. Piccinini 2006
        2. Piccinini 2007

    3. Recommended:

      1. Piccinini 2003
      2. Rapaport 1998, §1

        • §1 is relevant to Searle 1990; it presents my understanding of what it means to say that cognition is computable (as opposed to "computational").
        • §§2–3 criticize two other theories of computationalism; you can just skim these for now.

      3. Rapaport 2007

        • This is a direct reply to Searle 1990.

      4. Wolfram 2002–2003
      5. Schmidhuber 2006
      6. Powell 2006
      7. B.Hayes 2007


  14. Assigned: 3 Feb 2010
    Topic:
    What is an algorithm?

    1. Required:

      1. Henkin 1962

        1. pp.788–791
        2. skim the rest.

        • Discusses the history of logic and the foundations of math that led up to Turing's analysis.

      2. Re-read Davis 1987
        • Overlaps and extends Henkin's history, and provides a useful summary of Turing 1936.

      3. Herman 1983

        • Discussion (by a former UB CSE faculty member) of the informal notions of "algorithm" and "effective computability";
          good background for Turing 1936.

      4. Turing 1936

        • Or read Petzold 2008.
        • Concentrate on the informal expository parts;
          the technical parts are, of course, of interest, but are rather difficult to follow, incorrect in many parts, and can be skimmed.
        • In particular, concentrate on:

          • §§1–6
            (study the simple examples of Turing machines carefully; skim the complex ones)
          • and §9, part I
            (which elaborates on what it is that a human computer does).

        • §7 describes the universal Turing machine;
          §8 describes the Halting Problem.
          You can skim these sections (that's "skim", not "skip" :-)

    2. Strongly Recommended:

      • Soare 1996 or 1999, §§1–3, 4.5–4.6; skim the rest.

    3. Recommended:

      1. Browse through the "Examples of Algorithms"; enjoy the cartoons :-)

      2. Haugeland 1981

        • A good description of the syntax and semantics of formal systems and their relationship to Turing Machines.

      3. Boehm & Jacopini 1966

        • Uses flowcharts to prove that "go to" statements are eliminable from computer programs in favor of sequence, selection, and loops.
        • Not for the faint of heart!


  15. Assigned: 29 Jan 2010
    Topic:
    What is a computer? (Part I: History)

    1. Highly Desired (if you only had enough time to read two full-length books):

      1. Davis 2000
        • This will give you a good background in the "logical" history of computers,
          written by one of the leading mathematicians in the field of theory of computation.
        • At least try to read his Introduction (it's only 1 page long!)

      2. Aspray 1990
        • This will give you a good background in the "engineering" history of computers.

    2. Required:

      1. "A Very Brief History of Computers" (browse the linked websites)

      2. O'Connor & Robertson 1998, "Charles Babbage"

      3. Simon & Newell 1958
        • pp. 1–3 (on Babbage)
        • skim the rest.

      4. Davis 1987
        • Upon re-reading this, I have decided to promote it to "required".

      5. Ensmenger 2004

    3. Strongly Recommended:

      • Read the rest of Simon & Newell 1958.

    4. Recommended:

      1. Robinson 1994
        • Robinson developed the "resolution" rule of inference
          used in automated theorem proving and knowledge representation & reasoning

      2. Browse through:

        1. Maxfield etc. 1998
        2. Copeland 2000
        3. Lee 2002
        4. Hoyle 2003
        5. Hitmill 2004
        6. Computer History Museum 2008


  16. Assigned: 27 Jan 2010
    Topic:
    What is engineering?

    In doing these readings, remember that our ultimate question is whether computer science is an engineering discipline.

    1. Required:

      1. Davis 2009
      2. Petroski 2003
      3. Loui 1987

    2. Strongly Recommended:

      1. Davis 1998

        • Part I: "Introduction to Engineering", esp.
          Ch. 1 (pp. 3–17);
          pp. 25–28;
          pp. 31–37

      2. Petroski 2008

      3. Re-read (or finish reading) Brooks 1996

    3. Recommended:


  17. Assigned: 22 Jan 2010
    Topic:
    What is science?

    In doing these readings, remember that our ultimate question is whether computer science is a science.

    1. Required:

      1. Kemeny 1959:

        1. Introduction (pp. ix–xii)
        2. Ch. 5 ("The [Scientific] Method", pp. 85–105)

        • You can just skim Ch. 10 ("What Is Science?", pp.174 183), because his answer is just this:
          A science is any study that follows the scientific method.

      2. Kolak et al. 2006

      3. Papineau 1996

        1. pp. 290–295
        2. pp. 298–310;
        3. skim the rest.

    2. Strongly Recommended:

      1. Quine 1951
      2. Popper 1953
      3. Kuhn 1962
      4. Read the rest of Papineau 1996

    3. Recommended:

      1. Hempel 1966
      2. Kyburg 1968
      3. Ziman 1968
      4. Salmon 1984

    4. Highly Desired:

      • Okasha, Samir (2002), Philosophy of Science: A Very Short Introduction (Oxford: Oxford University Press).
        • This is the very best intro to philosophy of science.
          If you can get ahold of it in time, you may read it instead of any of the above.


  18. Assigned: 13 Jan 2010

    1. Required:

      1. Argument Analysis:

        1. Read Miller, David M. (2005), "Argument Analysis Worksheet" [Microsoft Word .doc file]

        2. Do §§A01–A09 of the Argument Analysis Module
          at the Critical Thinking Web of the Department of Philosophy of the University of Hong Kong.

      2. Topic: What is computer science?

        • Read each of the following slowly (i.e., one sentence at a time)
          and actively (i.e., think about each sentence; make notes in your Reading Journal).
        • Keep in mind that your main goal in reading these is to look for each author's answer to the above question.
        • Consequently, at least on a first reading, you don't have to read the "irrelevant" parts quite as carefully.
        • Below, I indicate which parts I think are of central importance for our present purposes
          and which parts you can just skim (i.e., read quickly).
        • Because we will be spending at least 2 class periods on this topic,
          you can split these readings up into 2 groups so that it doesn't become too overwhelming.

        Group 1

        1. Newell, Perlis, & Simon 1967

        2. Knuth 1974
          • §§1–3
          • optionally, §4, also.
          • (The more mathematically inclined may wish to read the whole thing :-)

        3. Newell & Simon 1976,
          • pp. 113–117 & "Conclusion" (pp. 125–126).
          • For now, concentrate just on what they have to say about what CS is.
          • Skim the rest; we'll read it later.

        4. Denning et al. 1989,
          • pp. 9–12 (up to "Curriculum Model"), 16–17 (up to §1);
          • skim the rest.

        Group 2

        1. Hartmanis & Lin 1992,
          • "Computer Science & Engineering" (pp. 163-168)
          • "Abstractions in Computer Systems" (pp. 168-174);
          • skim the rest.

        2. Brooks 1996,
          • pp. 61-64
          • skim the rest.

        3. Shapiro 2001

    2. Strongly Recommended:

      1. On argument analysis: Weston 2009, esp.:

        • I–IV
        • VI–VII

      2. On "What is CS?": Read carefully all the parts above that you skimmed :-)

    3. Recommended:

      1. On argument analysis:

        1. Explore more of the Hong Kong Critical Thinking website

        2. Explore Miller & Connelly 1996/2004

      2. On "What Is CS?":

        Group 1

        1. Arden 1980
        2. Krantz 1984
        3. Denning 1985
        4. Abrahams 1987
        5. Loui 1987

        Group 2

        1. Bajscy et al. 1992
        2. Abelson & Sussman 1996, "Preface"
        3. Gal-Ezer & Harel 1998
        4. Jacob 1999
        5. Shagrir 1999
        6. Comp. Sci. & Telecom. Board 2001
        7. Johnson 2001
        8. Foley 2002
        9. Boston U. Dept. of CS 2003
        10. CC2001: just skim through this
        11. Parlante 2005
        12. Naur 2007

          • Naur (of "Backus-Naur Normal Form", if you know what that is)
            helped develop Algol (if you know what that is:-).
          • This is Naur's Turing Award speech.
          • He appears to be a very bitter man, but has some interesting things to say.


  19. Assigned: 11 Jan 2010
    Topics:What is philosophy?
     What is philosophy of computer science?

    1. Required:

      1. Audi, Robert (2001), "Philosophy: A Brief Guide for Undergraduates"
        • A good brief intro to philosophy and its branches.

      2. Rapaport, "What Is Philosophy? A Brief Essay"
        • lecture notes

      3. Scheutz, Matthias (2002), "Philosophical Issues about Computation"
        • An encyclopedia overview article

    2. Strongly recommended:

      • Plato, The Apology
        • Various versions online
        • Plato's explanation of what Socrates thought philosophy was all about;
          a good intro to the skeptical, questioning nature of philosophy.

    3. Recommended:

      1. Colburn 2000, Chs. 3–4 (pp. 19–50).
        • A good survey of some of the history of philosophy that is relevant to CS.
        • Some of the material may be online; click on the link to the Google Books website to find out.

      2. Browse the readings cited on the "What Is Philosophy?" website.



Copyright © 2010 by William J. Rapaport (rapaport@buffalo.edu)
http://www.cse.buffalo.edu/~rapaport/584/S10/readings.html-20100419