MIT OpenCourseWare
4 HN recommenders · recommended in 4 months, 2021–2025
1:00:34 · 628K views · Oct 6, 2021
The first lecture of Michael Sipser's MIT 18.404J Theory of Computation course, covering course mechanics, finite automata, regular languages and regular expressions. It proves closure of regular languages under union and begins concatenation.
HN recommends Sipser's free lectures as the companion to the standard theory of computation textbook and a path to understanding how computers fundamentally work.
5 comments from Hacker News
AI won't ever be able to teach math because AI cannot reason. It handles information very differently than humans do. It is at best a flawed oracle that may lie through omission without you being able to tell. This is supported by the fact that there are hard limits to computation, in terms of both Computability Theory, and Complexity Theory that are often disregarded by the novice and magical thinker alike despite being largely solved fields by experts in Computer Science, at least in terms of Computability Theory. Most of this work was completed in the 1950s. This is not a difficult a subject, but most people online simply are unwilling to do the work to rationally learn this and instead choose to try and hide their own ignorance because they feel inadequate, or perhaps they are engaging in something more malevolent. The reasoning (false justification) doesn't really matter. It is, however; quite telling when expert's have validated these things, and yet any mention contrary to a narrative provokes downvotes in a public forum to remove it from view. A perfect example of intentional actions done by third-parties trying to misinform others about the risks (by those parties actions removing legitimate and valid information). For those with the cajones to actually learn this stuff. Here is a link. It seems very jaron laden but it provides a true understanding of how computers actually work which is sorely lacking in the youth of today. MIT 18.404J Theory of Computation this video
> if you require your parens to be balanced, that's no longer a regular language. TIL: [LINK] As someone who has only recently learned the formal definition of regular language ( Thanks to this video as mentioned on this board recently ), I'm interested in the formal proof for this? It feels intuitively true, but I haven't finished the course yet and therefore haven't come across it and can't yet reason well about it. Is the problem then in trying to "encode" whether brackets are balanced, that we would need infinite "levels" of how many more brackets we've opened rather than closed, (i.e a stack) and that violates the finite nature of finite automota? So I've googled it now, and I've found the result is due to the "Pumping lemma": [LINK]
As someone else said already: Theory of Computation by Sipser is the go to intro book for this. I'd recommend really reading the book front to back honestly. It helps to have a complete picture of everything that leads up to getting into complexity theory. Sipser also has corresponding lectures that are available for free on YouTube here: this video .
It's half a chapter in most books I know. Or a subset of this 1h MIT videos [0], but the instructor also explains Finite Automata which is the basic mechanism that does all the stuff. [0]: this video
He addresses prerequisites specifically in the first lecture at this timestamp: this video (You're expected to be comfortable understanding mathematical theorems and producing proofs.)