Class 22: Rice’s Theorem

We recapped reductions. Then, we discussed semantic properties of Turing machines and introduced Rice’s Theorem. It extremely powerful and shows many uncomputable functions at once! Slides are here.

Apr 10, 2025

Class 21: Kolmogorov Complexity

Today, Alice showed a metric of information in a string: Kolmogorov complexity. It is everywhere whenever we human write anything, but it is a big idea that built on the concept of computation. Alice’s slides is here. My slides will be posted on Thursday together with other slides.

Apr 8, 2025

Class 20: Halting problem, and reduction

We showed that Halting Problem is uncomputable through a reduction from \(ACCEPTS\). Also, we discussed Church-Turing Thesis. Slides are here.

Apr 3, 2025

Update (Apr 3): Problem Set 9 is now released. You can find the Overlead link in the PDF.

Class 19: Universal Turing Machines and Uncomputability

We showed that there are universal Turing machines. Using universal Turing machines, we proved that the boolean function \(ACCEPTS\) is uncomputable. Slides are here.

Apr 1, 2025

Class 18: Computability

We discussed more about some potential variants of Turing machines and how Turing addressed them. We then informally introduced the “computable numbers” and more generally computable functions. Slides are here.

Mar 27, 2025

Update (Mar 27): Problem Set 8 is now released. You can find the Overlead link in the PDF.

Class 17: Turing Machines

We concluded DFAs and regular expressions with the Cloudflare outage. With that, we formally introduced Turing machines. Historically, there were multiple models of computation, and Alan Turing showed that they are all equivalent to Turing machines.

Slides are here. PS7 is now posted and due next Tuesday.

Mar 25, 2025