Undecidability
This next set of lectures concerns the question of whether there are problems
that provably cannot be solved by computers, and how
to identify these.
Lecture #25: The Diagonalization Method — Part One
Required Reading
Lecture Presentation
Lecture #26: The Diagonalization Method — Part Two
Required Reading
Lecture Presentation
Lecture #27: Reductions and Reducibilities — Part One
Required Reading
Lecture Presentation
Tutorial Exercise #17: The Diagonalization Method — and an
Introduction to Reducibility
Lecture #28: Reductions and Reducibilities — Part Two
Required Reading
Lecture Presentation
Lecture #29: Reductions and Reducibilities — Part Three
Required Reading
Lecture Presentation
Tutorial Exercise #18: Reductions and Undecidability —
Part One
Lecture #30: Reductions and Reducibilities — Part Four
Required Reading
Lecture Presentation
Lecture #31: Reductions and Reducibilities — Part Five
Required Reading
Lecture Presentation
Tutorial Exercise #19: Reductions and Undecidability —
Part Two
Lecture #32: Reductions and Reducibilities — Part Six
Required Reading
Lecture Presentation
Tutorial Exercise #20: Reductions and Undecidability —
Part Three
Lecture #33: Reductions and Reducibilities — Part Seven
Required Reading
Lecture Presentation
Lecture #34: Reductions and Reducibilities — Part Eight
Required Reading
Lecture Presentation
Assignment #3: Turing Machines and Decidability
