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
  1. What is a computable function?
  2. Extensionality
  3. The Church-Turing thesis
  4. Decidable predicates
  5. The halting problem: why can't we build a 'halt-tester'?
Documents
Prerequisites

Watch the first and second lectures.