Great Ideas In Theoretical Computer Science Lectures 2-7

For those who missed it on the sidebar, we now have six more GITCS lecture notes available:

Lecture 2: Logic

Lecture 3: Circuits and Finite Automata

Lecture 4: Turing Machines

Lecture 5: Reducibility and Gödel

Lecture 6: Minds and Machines

Lecture 7: Complexity

More are on the way — compared to the Democritus notes, it’s so much easier with others doing the writing! These notes were prepared almost entirely by the students, with only minor editing from me and Yinmeng. In general, I think the students have been doing a fantastic job. On the other hand, if you rely on these notes to build a Turing-machine-controlled jumbo jet which then crashes in the Himalayas, it’s entirely possible that it wasn’t my fault.

21 Responses to “Great Ideas In Theoretical Computer Science Lectures 2-7”

  1. Scarybug Says:

    Have you thought about podcasting these?

  2. Scott Says:

    Sorry, Scarybug. I sound pretty dumb when speaking, and want as few of my “um”s and “y’know”s as possible preserved for future generations.

  3. Jeff Erickson Says:

    Um, you know, you could, uuuuh, you know, um, edit them, like, out?

  4. anonymous Says:

    That’s a great idea: get the students to do it! It saves you time, and they learn from it (I’m guessing).

  5. Scott Says:

    Um, you know, you could, uuuuh, you know, um, edit them, like, out?

    But then it would sound all disjointed and choppy, and it would still be less fluid than the written notes. And all the equations and figures would be missing (or separate), unless I also posted video, which would introduce its own problems…

    Look, I guess I’m trying to say that I like the medium of text. And not out of Luddism. I’ll use anything that works, but for conveying abstract ideas to a non-live audience, I find that text is still king.

  6. vilaca Says:


    thanks for this! great readig material!

    will be waiting for more like these 🙂

  7. Blaise Pascal Says:

    In Lecture three, you give the example of a finite automaton designed to recognize all binary strings with an even number of ones. You also state that it is equivalent to the RE (0*10*1)*. It isn’t. Here’s a simple counter-example: The string “0” has an even number of ones, but is not recognized by the given RE. I suspect it is a simple mis-transcription, as simply adding a single bar to get (0*|10*1)* fixes the problem.

  8. Scott Says:

    Blaise: Thanks! Yes, it was just a mis-transcription, and is fixed now.

    PS. Love the triangle! But will you do me a favor and lay off that belt of spikes?

  9. Adam Rogal Says:

    Yeah. Anything wrong with Lecture 3 is my fault and will be fixed in the final draft. Great class so far!

  10. Scott Says:

    Thanks, Adam! And no, most of what’s wrong with Lec3 should be laid at my feet. (Incidentally, great job with the graphics!)

  11. Anonymous Says:

    Please let your scribes/TA know that a left-double-quote in Latex is written using two back-quotes (` and `), not with the usual double-quote character. Fixing these minor errors would make the notes much prettier!

  12. todd Says:

    Dear Scott,

    I am a theoretical physicist (with an undergraduate degree in electrical engineering) who has gotten interested in quantum computing, complexity etc. through your blog, to the point that I am thinking of doing actual research in the subject. Could you direct me to a resource that is reasonably upto date where I can find an overview of the major ideas in one place? If it is available online, even better! I gave a few google searches and most things I found were a bit too scattered or popular-sciency.


  13. Scott Says:

    Todd, you could start with the resources (course lecture notes, etc.) listed on the sidebar of my blog!

  14. todd Says:

    Thanks, thats exactly what I was looking for!

  15. Len Ornstein Says:


    The notes are excellent.

    Pedagogically, they might be even better if you encouraged one of your very bright students, with the least math background and simultaneously the greatest language skills (if you have such) to reedit the notes.

    He/she might fill in gaps (of intellectual leaps) with helpful prose.

  16. Toronto Says:

    Hi Scott,
    I thought you (and your reaseders) might get a kick out of this comic:


  17. Job Says:

    Progress’ knotted sword seems like it would still be a very effective weapon, if not more so even. I think the comic has unintentionally stumbled into superb weapon conception the likes of which i would not like to meet on the battlefield.

  18. Craig Helfgott Says:

    Scott, have you read “On the uncomputability of hydrodynamics” by Warren D. Smith (circa 2003)?

    Very interesting paper. It basically shows that if you use the Navier-Stokes equation to describe fluid flow, and if you can start with a container with arbitrary length-scales, you can get a computer capable of solving the Halting Problem (and more!) in finite time. (This is much like the setups in Newtonian physics that allow you to accelerate a body to infinite speed in finite time).

    He also goes on to argue that the container might not strictly be necessary, if you can start with an arbitrary initial velocity vector field in R^3. (And that moreover, you might be able to get the vector field to be bounded).

    I was wondering if you could take a look at the paper and let me know your thoughts on the questions he poses at the end?

  19. John Sidles Says:

    Terence Tao’s Why global regularity for Navier-Stokes is hard offers a concise (informal) mathematical overview, with further links and references.

    Tao’s Simons Lecture on Structure and Randomness suggests a satisfying (to me) larger context.

  20. Jonathan Vos Post Says:

    Re: Craig Helfgott’s question of March 26th, 2008 at 4:04 pm

    “Scott, have you read ‘On the uncomputability of hydrodynamics’…”

    See the extensive treatment of the underlying equations by Terry Tao:

    Why global regularity for Navier-Stokes is hard

    18 March, 2007 in expository, math.AP, opinion, question

    Tags: critical equations, Navier-Stokes equations, scale invariance, turbulence

    It is always dangerous to venture an opinion as to why a problem is hard (cf. Clarke’s first law), but I’m going to stick my neck out on this one, because (a) it seems that there has been a lot of effort expended on this problem recently, sometimes perhaps without full awareness of the main difficulties, and (b) I would love to be proved wrong on this opinion 🙂 .

    The global regularity problem for Navier-Stokes is of course a Clay Millennium Prize problem and it would be redundant to describe it again here. I will note, however, that it asks for existence of global smooth solutions to a Cauchy problem for a nonlinear PDE. There are countless other global regularity results of this type for many (but certainly not all) other nonlinear PDE; for instance, global regularity is known for Navier-Stokes in two spatial dimensions rather than three (this result essentially dates all the way back to Leray’s thesis in 1933!). Why is the three-dimensional Navier-Stokes global regularity problem considered so hard, when global regularity for so many other equations is easy, or at least achievable? [truncated]

  21. John Sidles Says:

    Craig, you might want to read Terence Tao’s (online) essay Why global regularity for Navier-Stokes is hard. It discusses many of the same questions from a PDE point of view.