6.045/18.400 Automata, Comput, & Complexity
Spring 2015
Instructors: Scott Aaronson, Robin Ashok Kothari
Lecture: TR9.30-11 (34-101)
Information:
[Alan Turing's 1936 paper "On Computable Numbers"]
This course provides a challenging introduction to some of the
central ideas of theoretical computer science. Beginning in
antiquity, the course will progress through finite automata,
circuits and decision trees, Turing machines and computability,
efficient algorithms and reducibility, the P versus NP problem,
NP-completeness, the power of randomness, cryptography and one-way
functions, computational learning theory, and quantum computing. It
examines the classes of problems that can and cannot be solved by
various kinds of machines. It tries to explain the key differences
between computational models that affect their power.
Prerequisites: We assume that you have taken 6.042 Mathematics for
Computer Science, or have equivalent mathematical preparation. In
particular, we will assume you have basic "mathematical
maturity": i.e., that you're comfortable both reading and
writing rigorous mathematical proofs.
Textbooks:
1.
Introduction to the Theory of Computation by Michael Sipser --
covers most material from the first half of the course
2. Optional:
Quantum Computing Since Democritus by Scott Aaronson
3. Optional: The
Nature of Computation by Cris Moore and Stephan Mertens
4. Optional:
Computational Complexity: A Modern Approach by Sanjeev Arora
and Boaz Barak -- covers most material from the second half (as
well as more advanced material that we won't get to in class).
Draft
available for free on the web.
Announcements
Final exams are graded
Hi everyone,We've finished grading the final exam; all your grades should now be available on Stellar.
69 students took the final. The average score was 61.65 out of 100, the standard deviation was 12.81, and the high score was 87.
In retrospect, the final was maybe *slightly* too hard -- harder than the midterm, but as promised, not anywhere near hard as the 2011 final. We will, of course, take that into account in determining course grades. Roughly speaking, anything above 55 is adequate, above 65 is good, and above 75 is excellent.
The final did, once again, satisfy the property that there was no problem no hard that *no one* completely solved it. There were even people who got 25/25 on the true/false/open and 10/10 on the Chaitin's constant problem.
In general, the problems that people found hardest were:
- 2(e), about why a certain argument about Diophantine equations doesn't imply that P=NP would make the halting problem computable. Here the key point is that even if a Diophantine equation is solvable, it might only be solvable by integers that are astronomically, Busy-Beaverly large --- indeed that has to be so, because of the known equivalence between solving Diophantine equations and the halting problem.
- 6(b), about why a solution to the halting problem for every program of size at most n+O(log n) would let you compute the first n bits of Chaitin's Omega. Even though it was explicitly stated in the hint, only a few people figured out how, given the first i bits of Omega, you can construct a program whose halting or non-halting tells you the (i+1)st bit. Namely, take the first i bits of Omega and append a '1' to the end as the (i+1)st bit to get a number that we'll call w. Then write a program that dovetails over all programs, adding 1/2^|P| to a running total whenever some program P halts, and that halts if and only if the running total ever reaches w. If *this* program ever halts, then the (i+1)st bit of Omega was 1; otherwise it was 0. Furthermore, this program takes i+O(log i)+O(1) bits to specify: the first i bits of Omega, plus i itself encoded in binary, plus O(1) additional bits for the control.
Anyway, you can come to my office until 5:30PM today to look over your final if you'd like to (unfortunately, I can't let you take them home with you). After today, I'll be away from campus for a couple weeks, but I'll leave the finals with my administrative assistant Debbie Lehto in 32-G675A, and she can let you see the finals if you want.
Thanks so much to all of you for making this a great semester---at least for me and the TAs, and I hope for you as well. :-) Have a wonderful summer!
All the best,
Scott
Announced on 20 May 2015 2:21 p.m. by Scott Aaronson
Problem set 6 solutions
Announced on 18 May 2015 2:29 a.m. by Adam B Yedidia
2 pages of cheat sheet
Hi everyone,By popular request, we're going to allow 2 pages of cheat sheet for the final exam, and you can write on both sides of both of them. You're welcome! :-)
Best,
Scott
Announced on 15 May 2015 6:16 p.m. by Scott Aaronson
Review session
Hi everyone,The TA's will be holding a review session for the final exam this Wednesday at 7PM in 32-141. If you can't make it, there will also be final exam review in the recitations on Friday.
All the best,
Scott
Announced on 11 May 2015 1:56 p.m. by Scott Aaronson
Final practice materials
Hi everyone,Practice materials for the final exam are now available at
https://stellar.mit.edu/S/course/6/sp15/6.045/materials.html
I especially recommend doing the 2011 final; it should provide excellent preparation. (Note: You can expect this year's final to be shorter.)
In the other finals, you can ignore any material about VC-dimension or the Post Correspondence Problem; we didn't get to those topics this year.
Meanwhile, the TAs will have a final exam review session next week, either Tuesday or Wednesday evenings -- in addition to the recitation next week, which will also have final exam review.
Best,
Scott
Announced on 09 May 2015 11:30 a.m. by Scott Aaronson
