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 3: Circuits and Finite Automata
Lecture 5: Reducibility and Gödel
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.
Follow
Comment #1 March 10th, 2008 at 11:12 am
Have you thought about podcasting these?
Comment #2 March 10th, 2008 at 12:00 pm
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.
Comment #3 March 10th, 2008 at 1:32 pm
Um, you know, you could, uuuuh, you know, um, edit them, like, out?
Comment #4 March 10th, 2008 at 1:46 pm
That’s a great idea: get the students to do it! It saves you time, and they learn from it (I’m guessing).
Comment #5 March 10th, 2008 at 1:52 pm
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.
Comment #6 March 10th, 2008 at 3:09 pm
hey
thanks for this! great readig material!
will be waiting for more like these 🙂
Comment #7 March 10th, 2008 at 4:00 pm
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.
Comment #8 March 10th, 2008 at 5:10 pm
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?
Comment #9 March 10th, 2008 at 9:46 pm
Yeah. Anything wrong with Lecture 3 is my fault and will be fixed in the final draft. Great class so far!
Comment #10 March 10th, 2008 at 11:26 pm
Thanks, Adam! And no, most of what’s wrong with Lec3 should be laid at my feet. (Incidentally, great job with the graphics!)
Comment #11 March 11th, 2008 at 11:13 pm
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!
Comment #12 March 12th, 2008 at 5:24 pm
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.
Thanks,
Todd.
Comment #13 March 12th, 2008 at 6:01 pm
Todd, you could start with the resources (course lecture notes, etc.) listed on the sidebar of my blog!
Comment #14 March 13th, 2008 at 3:35 am
Thanks, thats exactly what I was looking for!
Comment #15 March 15th, 2008 at 1:09 pm
Scott:
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.
Comment #16 March 17th, 2008 at 1:21 am
Hi Scott,
I thought you (and your reaseders) might get a kick out of this comic:
http://www.viruscomix.com/subnormality.html
Enjoy…
Comment #17 March 17th, 2008 at 12:36 pm
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.
Comment #18 March 26th, 2008 at 4:04 pm
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?
Comment #19 March 27th, 2008 at 8:12 pm
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.
Comment #20 March 29th, 2008 at 3:46 pm
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
http://terrytao.wordpress.com/2007/03/18/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]
Comment #21 March 31st, 2008 at 12:15 am
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.