#1220 overall
6.045J Automata, Computability, and Complexity
MIT OpenCourseWare
1 recommender · 1 thread · recommended in 1 year, 2015 · score 0.7
An MIT undergraduate course on formal models of computation: finite automata, regular expressions, context-free grammars, Turing machines, decidability, and complexity classes. Commenters place it as a proof-heavy theory course.
One commenter calls it a good introduction to how to think about theoretical computer science, valued more for its reasoning than as a pure math class.
CS Fundamentals & Systemsintermediatefreevideo lectures#automata#computability#complexity#turing machines#regular expressions
Recommendations by year
20062026
Hi there and congrats on working through this course. Most students coming into this class are learning all the formalized truth table/mappings/isomorphism/etc stuff for the first time. I took this class after having failed a course in Real Analysis and ended up appreciating it not so much as a math class but as a good intro to how to think about Theoretical Computer Science.
Looking back at the psets, i think it's actually worth looking at them in reverse order just to not get too discouraged: the class ends on some number theory and begins with the Relation/Axiom/Set/Sequence stuff you see in early high level math classes. Some of that number theory/counting stuff is incredibly accessible from the outset, so the class doesn't just get monotonically more obtuse.
That said, if you've worked through vellman and you finish up this class, you're more than ready to do a class in proper number theory, discrete math or even real or complex analysis. Somebody else said that this course was a prereq for clrs, it is sort of, but you could take them both concurrently if you had to, as clrs doesn't have such a strong focus on proofs (if you're interested, 6.045j is a good followup in automata/computability/etc, lots of regexes, state machines and turing machines)
anyhow, i just want to say that it's ok if you don't get it all at once. i think i ended up seeing lots of these ideas two or three times in a variety of classes. probably the first time i was just mechanically spitting out proofs without understanding them. by the third time i came across them, they actually clicked for me. But there was value (for me at least) to exposure early on because you do know the things that are hazy and it's easier to dive deeper on those the next time you encounter them.
have fun!