6.893 Philosophy and Theoretical Computer Science
Fall 2011
Readings:
S. Aaronson, NP-complete
Problems and Physical Reality
S. Aaronson, Dude, It's Like
You Read My Mind
S. Aaronson and J. Watrous, Closed Timelike
Curves Make Quantum and Classical Computing Equivalent
E. Bernstein and U. Vazirani, Quantum
Complexity Theory
N. Bostrom, Are You
Living In A Computer Simulation?
D. Chalmers, Does A
Rock Implement Every Finite-State Automaton?
D. Chalmers, The
Singularity: A Philosophical Analysis
D. Deutsch, Quantum Mechanics Near
Closed Timelike Lines
D. Deutsch, Quantum theory, the
Church-Turing Principle and the universal quantum
computer
P. Domingos, The Role of Occam's
Razor in Knowledge Discovery
C. Gentry, Computing Arbitrary
Functions of Encrypted Data
M. Hutter, On Universal
Prediction and Bayesian Confirmation
H. Levesque, Is It Enough To Get The
Behaviour Right?
S. Lloyd, Computational Capacity of
the Universe
C. Papadimitriou, Algorithms,
Games, and the Internet
I. Parberry, Knowledge,
Understanding, and Computational Complexity
S. Kritchman and R. Raz, The
Surprise Examination Paradox and the Second Incompleteness
Theorem
J. Schmidhuber, A Computer
Scientist's View of Life, the Universe, and
Everything
S. Shieber, The Turing Test As
Interactive Proof
M. Sipser, The History and Status of
the P versus NP Question
R. Stalnaker, The Problem of Logical
Omniscience I
A. Turing, On Computable
Numbers
A. Turing, Computing
Machinery and Intelligence
L. Valiant, A Theory of the
Learnable
L. Valiant, Evolvability
A. Wigderson, P, NP and
Mathematics
A. Wigderson, Knowledge, Creativity,
and P versus NP
R. de Wolf, Philosophical
Applications of Computational Learning Theory
Instructor: Scott Aaronson
TA: Andrew Drucker
Lecture: W2-5 (36-112)
Information:
This new offering will examine the relevance of modern theoretical computer science to traditional questions in philosophy, and conversely, what philosophy can contribute to theoretical computer science. Topics include: the status of the Church-Turing Thesis and its modern polynomial-time variants; quantum computing and the interpretation of quantum mechanics; complexity aspects of the strong-AI and free-will debates; complexity aspects of Darwinian evolution; the claim that "computation is physical"; the analog/digital distinction in computer science and physics; Kolmogorov complexity and the foundations of probability; computational learning theory and the problem of induction; bounded rationality and common knowledge; new notions of proof (probabilistic, interactive, zero-knowledge, quantum) and the nature of mathematical knowledge. Intended for graduate students and advanced undergraduates in computer science, philosophy, mathematics, and physics. Participation and discussion are an essential part of the course.
Prerequisites: Previous coursework in either computability and complexity theory (such as 6.045 or 6.840) or analytic philosophy (such as 24.09)
[Official blog -- where Reaction Essays should be posted]
"Course Text": Scott Aaronson, Why
Philosophers Should Care About Computational Complexity
Required Books
David Deutsch,
The Beginning of Infinity
Roger Penrose,
The Emperor's New Mind
Optional Books
David Deutsch,
The Fabric of Reality
Ming Li and Paul Vitanyi,
An Introduction to Kolmogorov Complexity and Its Applications
Christos Papadimitriou,
Computational Complexity
Christos Papadimitriou,
Turing (A Novel About Computation)
Roger Penrose,
Shadows of the Mind
Michael Sipser,
Introduction to the Theory of Computation
Optional Lecture Notes
Scott Aaronson, Quantum Computing
Since Democritus
Scott Aaronson, Great
Ideas In Theoretical Computer Science
Announcements
Reading group on classical complexity
Reading group on classical complexity
Topics: circuit complexity, interactive proofs, average-case complexity and computationally bounded Kolmogorov complexity.
My plan is to choose some readings and problems on each topic and then arrange a time for discussion (time and place will depend on participants). Sessions would only cover a single topic and so if you're only interested in a subset of the topics, you could just come to those sessions. If you're interested in discussing any additional topics in classical complexity or from the class, then let me know and maybe we can arrange something.
My major interest here is relating complexity theory to AI/cognitive science. However, the first priority is just to get a good grasp of these ideas.
Contact: Owain Evans <owain@mit.edu>.
Announced on 18 November 2011 3:20 p.m. by Andrew Drucker
We need your reaction essays!
Hey 6.893 enrolled students,Quick reminder: the reaction essays are an important weekly assignment. They help us get to know each other and refine our views, and they're 25% of your grade for the course!
They're due every week before class on the course blog.
However, if you've missed past ones you can still get the bulk
of the credit by posting them late.
Putting an honest effort into these quick, ~2-paragraph essays is
probably the *easiest* way to improve your grade.
Announced on 09 November 2011 11:11 a.m. by Andrew Drucker
