Lecture 8: Undecidability

Name: Lecture 8: Undecidability
Uploaded: 2021-10-06T12:44:37Z
Duration: 1 h 17 min 2 s
Description: Description: Quickly reviewed last lecture. Showed that \(\mathbb{N}\) and \(\mathbb{R}\) are not the same size to introduce the diagonalization method and used it to prove \(A_\bf{TM}\) is undecidable. Introduced the reducibility method to show that \(HALT_\bf{TM}\) is undecidable. Instructor: Prof. Michael Sipser

1:17:02

Up Next

Lecture 9: Reducibility

Continue

Description: Quickly reviewed last lecture. Showed that \(\mathbb{N}\) and \(\mathbb{R}\) are not the same size to introduce the diagonalization method and used it to prove \(A_\bf{TM}\) is undecidable. Introduced the reducibility method to show that \(HALT_\bf{TM}\) is undecidable.

Instructor: Prof. Michael Sipser