Skip to main content

Introduction to Turing, Computability, and the "Halting Problem"

Difficulty level
Beginner
Speaker
Type
Duration
28:28

This lecture will addresses what it means for a problem to have a computable solution, methods for combining computability results to analyse more complicated problems, and finally look in detail at one particular problem which has no computable solution: the halting problem.

Topics covered in this lesson
  • What is a computable function?
  • Extensionality
  • The Church-Turing thesis
  • Decidable predicates
  • The halting problem: why can't we build a 'halt-tester'?
Documents
Lecture Slides (365.14 KB)
Prerequisites

Watch the first and second lectures.