PHI 322 Philosophy of the Cognitive Sciences
Foundations of classical, quantum, and biological computation
Readings | Homework |
Handouts | Course outline
| Course mechanics
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 +
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.
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.
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
- 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.
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.
- B. Jack Copeland. Super Turing-Machines. Complexity, vol. 4 (1998) pp. 30-32.
- B. Jack Copeland and Richard
Sylvan. Beyond the Universal Turing Machine
Australasian Journal of Philosophy, vol. 77
(1999), pp. 46-66.
- 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
- 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
The Church-Turing Thesis
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,
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
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:
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
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.
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
- 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,
- 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.
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
Bringing copies of the readings for that week so that we can refer to specific
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
Adam Elga | firstname.lastname@example.org
| Princeton University
Last modified: Fri Dec 12 17:40:51 EST 2003