PHI 322 Philosophy of the Cognitive Sciences

Foundations of classical, quantum, and biological computation

Readings | Homework | Handouts | Course outline | Course mechanics

Spring 2003
Professor: Adam Elga.
TA: Colin Klein.
(Follow the appropriate link above for Elga or Klein's office hours and contact information.)
Meeting time: 2:30 TTh + Precept
Class meeting place: Jones 203


  • The final exam will be a take-home exam distributed on Tuesday, May 13, and due at noon on Monday, May 19.

What questions can your computer answer in a reasonable amount of time? Our answer will be: It depends what sort of computer you've got. We will contrast the power and limits of one standard sort of computer (the Turing Machine) with several exotic cousins (quantum computers, infinitely fast Turing Machines, DNA and cellular computers). On the way, we'll get tastes of algorithmic information theory (which makes precise the notion that simple objects have short descriptions), reversible computation, and elementary quantum mechanics.


Unless otherwise noted, you should do the problems on your own.


Readings will be drawn from:

  • A few lecture handouts.
  • The required texts:
    • George S. Boolos, John P. Burgess, Richard C. Jeffrey. Computability and Logic. Cambridge University Press, 2002. (Fourth edition), [Addenda]
    • Hughes, R. I. G.. The Structure and Interpretation of Quantum Mechanics. Harvard Univ. Press, 1989.
    • Albert, David. Quantum Mechanics and Experience. Harvard Univ. Press.
  • Various articles available on the web (linked from this page).
  • Articles on electronic reserve. You can access the ereserves through the library's electronic reserve page. You'll need the course userid (phi322) and course password [supplied in class] to log in. You also may need to download some special software; see the help page for details.
  • Materials on reserve in Firestone's reserve room (abbreviated "FIR", below). Note: this is an underused resource; be sure to check out that list, since there may be a book there that would interest you.

Course Outline

Note that this outline does not represent the relative time spent on each topic. In fact, we will spend most of the first half of the semester on classical computation, and most of the second half of the semester on quantum mechanics and quantum computation. DNA, cellular-automata, and cellular computation will fill in the gaps.

Abstract notion of computation, physics of computation

What is a computer?

    Classical computation: Turing Machines

    Enumerability, diagonalization, finite state automata, Turing Machines, universal machines, uncomputability.

  • George S. Boolos, John P. Burgess, Richard C. Jeffrey. Computability and Logic. Cambridge University Press, 2002. (Fourth edition). Chapters 3, 4. On Electronic Reserve
  • Those who are not at all familiar with the material may wish to consult chapters 1 and 2, as well (of which, only chapter 2 is on ereserve).
  • (optional reference)Michael Sipser. Introduction to the Theory of Computation. Brooks/Cole Pub Co; ISBN: 053494728X; 1st edition. Firestone reserve.

Kolmogorov complexity and uncomputability

  • (Background reading) M. Li and P.M.B. Vitanyi, An Introduction to Kolmogorov Complexity and its Applications, Springer-Verlag, New York, Second Edition, 1997 (xx+637 pp). (Rather technical, but an unmatched reference for those who need the full details.) Firestone Reserve.

Enhanced Turing-Machines

  • B. Jack Copeland. Super Turing-Machines. Complexity, vol. 4 (1998) pp. 30-32. Preprint
  • B. Jack Copeland and Richard Sylvan. Beyond the Universal Turing Machine Australasian Journal of Philosophy, vol. 77 (1999), pp. 46-66. Preprint
  • Davies, E.B. "Building infinite machines". British Journal for the Philosophy of Science 52 (2001) 671-582. Preprint
  • Joel David Hamkins. Infinite Time Turing Machines: Supertask Computation (For more technically adventuresome readers.)

Introduction to computational complexity: big-O notation, complexity classes, logic gates, combinatorial circuits, circuit complexity.

  • Background reading (somewhat technical): Papadmitriou. Computational Complexity. Firestone Reserve.

Logic gate architecture, reversible computation. Reversible logic gates, universal reversible gates, the Billiard-ball model of computation.

The Church-Turing Thesis

Quantum Computation

Quantum mechanics: linear algebra, the representation of spin states, Schrodinger evolution, Born's rule.

  • Less technical treatment: Albert, David. Quantum Mechanics and Experience. Harvard Univ. Press. Chapter 2.
  • More technical treatment: Hughes, R. I. G., "The Structure and Interpretation of Quantum Mechanics", Harvard Univ. Press, 1989. Chapter 1.

Quantum circuits, universal quantum gates, the quantum black box, quantum teleportation

Bad news: due to personal constraints, Ken Steiglitz will not be able to give a guest lecture as scheduled. Good news: A local philosophy of mind guru, Karen Bennett, has agreed to give a guest lecture on a devious attack on functionalism.

Is your brain a computer?

April 10: be sure to have read the Maudlin article below.

April 15: Guest lecture: Karen Bennett, Philosophy

DNA computation

Thursday, April 17
Guest lecture: Danny van Noort, Ecology and Evolutionary Biology
Lecture slides (html)
Be sure to have read at least the first two of the following articles:

Cellular computation

April 24. Class cancelled

April 28. Professor Tim Maudlin (Rutgers Philosophy) will be attending the 4:30 (Monday) precept. All precepts this week (i.e., Monday April 28 2:30 and Wednesday April 30 2:30) are moved to Monday April 28 4:30 for this special visit. Please be ready to ask questions about and/or present objections to "Computation and Consciousness".n

April 29. Class extended: 2:30 - 4:00 Guest lecture: Ron Weiss, Electrical Engineering.
Before Professor Weiss's lecture, please read at least pp. 1-10 and 23-24 of the following article:

Course mechanics and policies

Prerequisites: No formal prerequisites, since all needed background will be covered in class. However, the homework assignments will involve some mathematics, so students should be comfortable doing simple proofs.

COS Majors: PHI 322 counts as a COS departmental this spring, if you haven't already taken COS 487.

Reading/Writing Assignments

Weekly homework assignments.

  • These will be graded on a coarse scale. Please print out and bring your homework to precept, as we will often discuss the answers to homework questions there.
  • Late homework accepted only with a very good reason. (Example of a very good reason: extreme medical excuse with written documentation. Examples of not very good reasons: computer foul-ups, other commitments.)
  • Some of the homework questions will be mathematical or will require diagrams. For these questions, it is fine to neatly write your answers. But for the remaining questions--the ones requiring multiple-sentence answers--please type your answers.

40% weekly homework assignments and class, precept participation, 30% midterm exam, 30% take-home final exam.

Missing class or precept: If you miss a lecture or a precept, it is your responsibility to find out from another student what happened and to get copies of notes and handouts. After doing that, if you have questions about what was covered, please do meet with me or your preceptor to discuss them.

Precept Guidelines:

  • Please show up to precept ready to rock.  That means:
    • Showing up on time.
    • Being prepared, which means, in addition to having attended lectures and done the relevant readings, having thought about the material.  If you don't understand something in the readings, be prepared to ask.  If you think something we read is wrong, or crazy, be prepared to say so.
    • Bringing copies of the readings for that week so that we can refer to specific passages.
  • An important aim of precept is for you  to discuss each others' views.  In order to do that effectively you need to learn the names of the people in the precept.  It is better to try to use someone's name and get it wrong than just to say "I agree with the second thing she said..."

Adam Elga | | Princeton University
Last modified: Fri Dec 12 17:40:51 EST 2003