PHI 322 Philosophy of the Cognitive Sciences
Foundations of classical, quantum, and biological computation
Readings  Homework 
Handouts  Course outline
 Course mechanics
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 takehome 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.
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,
cellularautomata, 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, SpringerVerlag, New York, Second Edition, 1997
(xx+637 pp). (Rather technical, but an unmatched reference for those
who need the full details.) Firestone Reserve.
Enhanced TuringMachines
 B. Jack Copeland. Super TuringMachines. Complexity, vol. 4 (1998) pp. 3032.
Preprint
 B. Jack Copeland and Richard
Sylvan. Beyond the Universal Turing Machine
Australasian Journal of Philosophy, vol. 77
(1999), pp. 4666.
Preprint
 Davies, E.B. "Building infinite machines". British Journal for the
Philosophy of Science 52 (2001) 671582. Preprint
 Joel David Hamkins. Infinite Time Turing Machines: Supertask Computation
(For more technically adventuresome readers.)
Introduction to computational complexity: bigO 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 Billiardball model of
computation.
The ChurchTuring 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. 110 and 2324 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 foulups,
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 questionsthe ones requiring
multiplesentence answersplease type your answers.
Grading
40% weekly homework assignments and class, precept participation, 30% midterm
exam, 30% takehome 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  adame@princeton.edu
 Princeton University
Last modified: Fri Dec 12 17:40:51 EST 2003
