PHI 322 Philosophy of the Cognitive Sciences

Foundations of classical, quantum, and biological computation

Spring 2003
http://www.princeton.edu/~adame/teaching/PHI322_S2003
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

Announcements

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

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

Homework

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

Readings

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.

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.

• Earman, J. (1986), A Primer on Determinism. Dordrecht: Reidel. (selection)
• John Preskill. Lecture notes for Physics 219/Computer Science 219. (selection)

The Church-Turing Thesis

• B. Jack Copeland. The Church-Turing Thesis. Stanford Encyclopedia of Philosophy.

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

• Eleanor Rieffel. An Introduction to Quantum Computing for Non-Physicists.
• John Preskill. Lecture notes for Physics 219/Computer Science 219.
• Nielsen and Chuang. Quantum Computation. A very thorough text, with encyclopedic scope and technical style. For your optional perusal. Firestone Reserve.

Is your brain a computer?

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

April 15: Guest lecture: Karen Bennett, Philosophy

• Tim Maudlin. Computation and Consciousness (JSTOR)
• Ned Block. What is Functionalism? (a revised version of the entry on functionalism in The Encyclopedia of Philosophy Supplement, Macmillan, 1996). Up to and including the section entitled "Functionalism and Physicalism".
• Ned Block. The Mind as the Software of the Brain. Sections 1 and 2.2.
• B. Jack Copeland. What is Computation? Synthese, vol. 108 (1996) pp.335-359.

DNA computation

• Leonard M. Adleman, Computing with DNA, Scientific American, August, 1998, 54-61.
• Adam J. Ruben, Laura F. Landweber. The past, present and future of molecular computing Nature Reviews.
• Leonard M. Adleman. Molecular Computation of Solutions to Combinatorial Problems. Science, Nov. 1994, 266:1021-1024.

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:

• Ron Weiss et. al. Genetic circuit building blocks for Cellular Computation, Communications, and Signal Processing. Natural Computing, an International Journal, 2003 (in press)

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.

Grading
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..."