6.893 Philosophy and Theoretical Computer Science

I thought I’d let Shtetl-Optimized readers know about an experimental new course I’m teaching this fall (starting tomorrow): 6.893 Philosophy and Theoretical Computer Science.  The course was directly inspired by my Why Philosophers Should Care About Computational Complexity essay, and will cover many of the same topics.  Here’s the description:

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.

If you’d like to follow remotely, the course homepage has links to lots of interesting readings, and students will also be posting their personal reactions to the class discussions as the semester progresses.

Update (Sept. 7): By overwhelming request not only from readers but from students in the class, and with several of those students’ extremely kind assistance, we will be making audio recordings—although the audio quality probably won’t be great.

51 Responses to “6.893 Philosophy and Theoretical Computer Science”

  1. Noah Says:

    It would be fantastic if you could get these lectures recorded on MIT Open Courseware. If the Michael Sandel lectures on Justice are any gauge then I could imagine this being very popular (I know I’d like it).

  2. Andrew Marshall Says:

    Thanks for putting this material online, and gives me an added impetus to read Deutch’s latest. Half-surprised not to see GED on the optional reading list, though…

  3. Scott Says:

    Noah: Because of the informal, discussion-oriented nature of the course, I decided not to have it recorded. But as I said, you’ll be able to read the student reactions on the course website shortly.

  4. Scott Says:

    Andrew: Some of the Achilles/Tortoise dialogues in GEB are absolute classics that could be studied purely as literature! But, frankly, it’s also a book that always irritated me for completely ignoring “post-1930s” theoretical computer science, which is what most of my course will deal with. And besides, GEB might be outdated now, given that Hofstadter has since written several more 800+ page books explaining what he was trying to say in GEB! 😀

  5. Qiaochu Yuan Says:

    Hi Dr. Aaronson (or would you prefer Scott?). I signed up for this class and am very much looking forward to it, but what do you think about getting it cross-listed in Course 24? For my own selfish reasons I’d like to get humanities credit for it. I completely understand if this is not a thing that you feel is worth doing.

    In any case, looking forward to meeting you tomorrow!

  6. Mike Says:

    For those without a MIT Kerberos account or who may be following from afar, you can find an on-line version of Deutsch’s “Quantum Mechanics Near Closed Timelike Lines” at:


    I for one am sorry your not recording the lecture/discussion series. Perhaps you’ll reconsider.

  7. Scott Says:

    Qiaochu #5: See you tomorrow! (BTW, Scott is fine.)

    We’re going to have lots of participation by course 24 students and faculty, but sorry, I didn’t seek cross-listing with course 24. If you need humanities credit, can’t you take a real humanities course? Y’know, like literature or history or something? 😀

  8. Scott Says:

    Mike #6: Thanks so much for the link! I updated it on the course website.

    Regarding recording, the main concern was that I didn’t want to inhibit open-ended discussion by recording everyone’s umms, uhhs, and half-baked thoughts for posterity. In addition, there didn’t seem like a pressing need for recording, since I’ve already essentially written a “course textbook” in the form of my essay. But as I said, we will have student reaction essays for each class session and they will go up on the website.

  9. Anonymous Says:

    I agree with others about recording, at least recored the voice so you can later transcribe them and put an edited version online.

  10. Mike Says:

    Scott #8,

    Understood — wish I could listen anyway 😉

    BTW, just finished Deutsch’s new book — reading parts now for the second or third time. As you might imagine, I’m finding it a lot of fun. 🙂

    Good luck with the class.

  11. Orm the Red Says:

    Would a philosophy grad student with two years of high school math, no physics or computer science knowledge to speak of, and a general fear of technology be welcome in the class?

  12. Scott Says:

    Orm the Red: Uhh, are you enrolled at MIT or Harvard? And are you familiar with formal logic and analytic philosophy more generally? If so, then yes, absolutely!

  13. Mike Travers Says:

    Looks really interesting, but seems limited (maybe wisely) to analytic philosophy.

    There is a whole strain of work from the 80s (much of it at MIT) that was partly inspired by Heidegger and phenomenology AND the realization that some classical AI problems were computationally intractable. This work was controversial, to say the least, but influential in its way. I’d suggest that any course on this topic ought to at least touch on this work.



  14. Scott Says:

    Mike Travers #13:

    You’re completely right that, when I use the word “philosophy” in the context of this course, I mean philosophy in the analytic tradition—in other words, philosophy for which things like “solving problems” and “making sense” are at least considered worthwhile as goals! 🙂

    While it’s conceivable that there interesting connections between TCS and Continental philosophy (or Eastern or Christian or Islamic philosophy, etc.), if so I certainly wouldn’t be competent to discuss them.

    I wasn’t planning to touch on either Heidegger or Hubert Dreyfus in this course, and the reason is not that I don’t know who they are.

  15. Mike Travers Says:

    Well, I wouldn’t use Dreyfus or Heidegger in a course like this either, for various reasons. But I might use something like Phil Agre’s Computation and Human Experience, which is (among other things) an introduction to those sorts of ideas from a computational perspective. No prior immersion in continental babble required.

    A fair number of very smart computer people got caught up in these ideas, which means at least they are not prima facie nonsensical to all. However, all of them stopped doing computer science shortly thereafter, so maybe it’s wise to steer clear.


  16. Jago Says:

    It seems as though you have an interest in philosophy, Scott. Have you taken many philosophy classes, which ones, when, at what institution, and under what professors? If you can assure me that the overwhelming majority of your philosophical knowledge is the product of independent thinking and reading, rather than something you gathered from course work, then I’m absolutely in!

  17. Nagesh Adluru Says:

    Thank you so much for making the material available online. I so wish that your course would be available online like that of Stanford’s AI course!!!

    My best wishes Scott,

  18. Usman Masood Says:

    I really want to attend this class but it sadly conflicts with some other courses I “have” to take :(. Will it be okay if I come and sit in the corner during the last hour?

  19. Neel Krishnaswami Says:

    Hey, there’s a complete absence of anything about programming languages. There’s nothing about lambda calculus and constructive logic, or the relationships between type theory, category theory and mathematical structuralism. You can’t really say anything about the philosophy of mathematics without this stuff.

  20. Scott Says:

    Jago #16:

    Have you taken many philosophy classes, which ones, when, at what institution, and under what professors?

    I’ve taken only two philosophy classes in my life:

    Frege at Cornell, with Jason Stanley

    Modal interpretations of quantum mechanics at Berkeley, with Guido Bacciagaluppi

    I enjoyed both of them a lot. But I’ll mostly be relying on the philosophy students in the class (and even some philosophy faculty who might sit in) to keep me honest—especially about what various philosophers said or didn’t say!

  21. Scott Says:

    Neel #19: Sorry! The sad fact is that I’m not competent to discuss programming language semantics, at either a technical or a philosophical level.

    On the positive side, Google turns up many existing courses (including in philosophy departments) devoted to philosophy and programming language theory, and the Stanford Encyclopedia of Philosophy entry on “The Philosophy of Computer Science” is almost entirely devoted to this connection. By contrast, Google didn’t turn up a single course dealing with philosophy and computational complexity.

    So, in discussing what I’m competent to discuss (i.e., philosophy and complexity, cryptography, quantum computing, PAC-learning…), I’ll also be doing something more novel.

  22. John Says:

    Scott, have you seen this:


  23. Neel Krishnaswami Says:

    Scott: I’m very surprised by that! IME, algo/complexity has vastly higher prominence among mathematicians than PL does (since, um, much of the technology of PL was invented by marginal/dissident factions of logicians), so I would have expected more philosophers to know about complexity.

    Certainly PAC-learning seems like it should be hot stuff for anyone who wants to avoid living in a Bayesian mono-culture.

  24. Ungrateful_Person Says:


    I would be really grateful if these lectures could be videoed.

    Yours truly

  25. Ungrateful_Person Says:

    This comment is kind of vague, so please bear with it.

    On a more serious note I feel (I might be wrong about it) that putting up videos of a course like this which is informal and discussion oriented is certainly more valuable than those which are formal and very terse.

    Certainly, there is room in these kind of lectures for some wildly inaccurate assumptions on part of the listener (in particular thos who watch it recorded) but its more of a value add to these kinds of listeners as well. While I agree that if someone wants to get something valuable out of this course has to take it seriously and think through the lectures, but thats precisely what an informal lecture allows a “passive” listener like the one I have in mind (namely me and I believe many more) to avoid.

    We can focus on the big picture and get to know the subject and feel compelled to learn more (maybe later).

  26. Vijay Vazirani Says:

    How about the Invisible hand of the market and
    recent results on computability of market equilibria.

  27. Mitch Says:

    It is really hard to record a room so you can hear everybody. I imagine it would be quite annoying to the students to pass around a mike if they wanted to say something. I think the reaction essays could be really interesting in a class like this… especially from people who are not mathematicians/scientists and may agree with alot of stuff we take for granted.

  28. Mitch Says:

    ^^Obv should be may NOT agree…

  29. Scott Says:

    Vijay #26: Yep, we’re gonna talk about it!

  30. Nagesh Adluru Says:

    Audio recordings would be awesome! Thanks so much Scott and to the team recording this.

  31. helpneeded Says:

    May be you should invite Morgan Freeman to provide an introduction:)

  32. Anonymous Says:

    Thanks Scott. 🙂

    (Just imagined for a second imagine how interesting it could be if they had recorded the lectures by Hilbert or Turing or von Neumann or [put our favorite scientist here]!)

  33. mike Says:

    Glad you’ll be recording . . . thanks.

  34. Mike Says:


    Just checked out the Syllabus. Oh to be young again — and even remotely capable of getting into MIT and participating in such fascinating courses and discussions.

    It looks like a whole lot of fun.

    Well, perhaps in another universe 😉

  35. helpneeded Says:

    @Mike: Read his philosophy. Scott does not believe in multiple worlds!!

  36. Mike Says:

    “Scott does not believe in multiple worlds!!”

    Well, I don’t recall saying he did. But, whether he does or not, it doesn’t have any impact on the question, does it? 😉

  37. Francesco Bruschi Says:

    Hi Scott, I just finished reading “The Beginning of Infinity” (I bought it ‘cos you mentioned it in a recent post, and I now see it is one of the required readings for your course), and the chapter on the multiverse resparked in me enthusiasm on that QM interpretation. So I checked out what you wrote about that, and found you’re agnostic, and leave freedom of conscience on the issue (“be whatever you find most useful, be it copenaghenism on monday and bohmism on tuesday…”) But there is a thought experiment I found disturbing, in Deutsch book: if you initialize every bit of a computer memory tossing some quantum coin for each one of them, IF we were in a multiverse, then you would be generating every possible program, likely including various forms of AI, among which some probably initialized in a suffering state… wouldn’t that be a very nasty thing to do, if (and only if) we really were in a multiverse? But the real question is: are you gonna talk about the moral implications raised by this speculation, in your thrilling course?

  38. Joshua Zelinsky Says:


    I can’t speak for Scott obviously, but that thought experiment seems wrong. A quantum computer only generates a finite set of quantum bits. Even if you could generate say 2048 quantum bits, since a mind requires far more bits than that, this wouldn’t be able to generate any minds. There are other problems with this idea but that seems to be the most obvious.

  39. Mike Says:

    @Joshua Zelinsky,

    “Even if you could generate say [2048] quantum bits, since a mind requires far more bits than that, this wouldn’t be able to generate any minds.”

    Assumption one: The “mind” is a physical object performing a computational task.

    Assumption two: The Church-Turing Principle in its strong form (sometimes called the Church-Turing-Deutsch principle), is correct and there can be built a universal quantum computer that can be programmed to perform any computational task that can be performed by any physical object.

    Then, a quantum computer can be built that is capable of generating AI, or “minds”.

    And, since it’s not forbidden by the laws of physics, the rest, as they say, is “just” engineering.

    But that’s not even the hard part. Figuring out how to program the darn thing will probably take a lot longer than building the hardware since we are making such very slow progress understanding consciousness and human creativity.

    Of course, if one doesn’t think the basic assumptions are correct, and that the either the mind is somehow “more” than a physical object performing a computational task, or that the CTD principle is not correct — say because something we don’t understand about quantum physics forbids the construction of the universal quantum computer, then it “might” be impossible — assuming no one figures out a very clever way to generate the necessary resources classically.

    I do, however, think that the “moral” implications are worthy of discussion.

  40. Francesco Bruschi Says:

    Dear @Joshua, Deutsch (if I got him right) talks of a good old classical computer with, say, 4GB of CMOS memory. The fact is that, always if I got it, you could initialize every bit of that memory tossing a quantum coin (which could physically mean, for instance, to decide to set it to 0 or 1 according to the polarization of a photon emitted by a given source etc) Every time the coin is tossed, both the outcomes happen, each one in a different universe, and once you measure it, you cause decoherence and keep those universes from interfering anymore. You would end up with 2^2^35 classical computers, each with a different memory content, each in a different universe. If it is possible to “generate” a conscience with 4GB of RAM and a “classical” processor of those we have nowadays, that will happen in some of the universes generated by the initialization…

  41. Abel Molina Says:

    @Francesco. That sort of seems to assume that conscience is a “static” thing, but I guess you could get around that by counting as part of the conscience also the future behaviour of the computer when you initialize it to that state (though then you might need to initialize more stuff than the RAM, but well, that’s not the point).

    Also, I wonder whether the author would say that the same argument applies when instead of having a computer with 4GB of memory, you have 2^32 computers with one bit of memory each, separated in space from each other, and if not, why.

  42. Scott Says:

    Francesco #37:

    if you initialize every bit of a computer memory tossing some quantum coin for each one of them, IF we were in a multiverse, then you would be generating every possible program, likely including various forms of AI, among which some probably initialized in a suffering state… wouldn’t that be a very nasty thing to do, if (and only if) we really were in a multiverse?

    Sure, by tossing a bunch of quantum coins you have some nonzero probability of generating immense suffering … but you also have some nonzero probability of creating heaven on earth! And the crucial point is that both of those probabilities are whatever they are, regardless of whether you choose to regard the possibilities as “really existing, in a real multiverse” or just as unrealized hypotheticals.

    As previous commenters said, I’m not sure whether I believe MWI, but more important is that I’m not even sure I understand what the question of MWI’s truth or falsehood means. (What exactly does it mean for other decohered branches of the wavefunction to “exist”? How could we know? Presumably via a suitable interference experiment—but if such an experiment succeeded, then the branches wouldn’t have decohered in the first place! 🙂 )

    Keep in mind that MWI leads to exactly the same predictions as standard QM, in any experiment that anyone knows how to describe. And therefore, any time you catch yourself thinking “gee, if the parallel universes are real, I should live my life differently than if they aren’t,” I’d argue that the only reasonable conclusion is that you need to change the way you think about MWI!

    (Trivial example: Suppose you decide that you shouldn’t drive home drunk, because in some parallel universe you’re going to run over schoolchildren, and that isn’t balanced out by any foreseeable good effects in the other parallel universes. Well then, you shouldn’t drive home drunk even if MWI is false! The probabilities work out exactly the same, whether or not you call them “measures” over a set of actually-existing worlds.)

  43. Mike Says:


    “And therefore, any time you catch yourself thinking “gee, if the parallel universes are real, I should live my life differently than if they aren’t,” I’d argue that the only reasonable conclusion is that you need to change the way you think about MWI!”

    I know this is right, but I just can’t help but allow myself a “wistful” feeling once in a while — is that so bad?

  44. Raoul Ohio Says:

    Discussing Philosophy, check out the Nietzsche Family Circus:


    (thanks to “Good Morning Silicon Valley” for the lead)

  45. Raoul Ohio Says:

    Also from GMSV, a catalog of deep philosophical gems hidden in lyrics to Beatles songs:


    Back in the 60’s, everyone thought the Beatles were “real deep”. In the 70’s, I evolved into a revisionist, pointing out that everything seems “real deep” if you are smoking pot.

  46. thank you based scott Says:

    A New General-Purpose Method to Multiply 3×3 Matrices Using Only 23 Multiplications
    Maybe this has been posted already. I just want to point it out since matrix multiplication has (maybe?) been mentioned on this blog before.
    Thank you Scott. Keep going with the hard work, and maybe do some collaborations with Marcus Hutter if you get some free time 🙂 Have a good day!

  47. Mike Says:


    I’m not going to presume to comment on the class blog, but the last comment by “ezyang” was surprising in its subtly, creativity and at the same time it seem connected and grounded. I’m not sure ultimately of the meaning, but it was truly great fun to read.

  48. Silas Barta Says:

    This seems like it would be a neat course to participate in! I read your paper on computational complexity’s application to philosophy and really enjoyed it. Not to be vain, but I also like how it gave a rigorous expression to a lot of the intuitions I’ve had about the various topics. My LW comments.

    Just a heads-up, though: It looks like some joker broke in to the server and added Penrose to the reading list 😛

  49. Raoul Ohio Says:

    Scott leaves ’em speechless, perhaps dumbfounded:

    “Scott Aaronson’s talk on free will deserves a special mentioning, but I found it impossible to summarize. I recommend you just watch the video when it comes out.”



  50. Raoul Ohio Says:


    I am confident that had John Sidles or I been at this event, we would have scrounged up something to argue with Scott about.

  51. Daniel Cali Says:

    This is a fascinating class! I am a philosophy major and, I would love to explore the underworld of computer science more. Now, it is just up to Bash scripts, C, and C++ and Java. This is a fascinating idea! Keep it up! Also, Oxford University beat you to it!


    That is just FYI.