Just how powerful are Turing machines? Today we see what we know of the answer to this question. From there, we give some formal definitions to key terms so we can ultimately answer the big question at the core of CS103: what problems can we solve with computers?
Links
- Condensed Slides.pdf
- Lecture Slides.pdf
- recognizers-and-recognizability.pdf
- very-important-terminology.pdf
Lecture Recording
The complete archive of this quarter's lecture recordings is available on Canvas.
Very Important Terminology
For your convenience, here are the "Very Important Terminology" and "Recognizers and Recognizability" slides from today's lecture! Of course, this is not to imply that the other things in today's slides aren't super important as well. 🙂 Do not sleep on the rest of the slide deck from today's lecture!
Keith mentioned today that while the terminology in these slides isn't necessarily complicated, a misunderstanding of these terms is a really common source of mistakes we see in the final few weeks of this course.