Introduction to Turing, computability, and the "halting problem"

Introduction to Turing, computability, and the "halting problem"

By
HBP Education Programme
Difficulty level
Beginner
Speaker
David Lester
Type
Video
Duration
28:28
Topic
Computer Science

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
Lecture Slides (365.14 KB)
External Links
Link to HBP Education Programme
Prerequisites

Watch the first and second lectures.

Back to the course
Introduction to information and communications technology (ICT) for non-specialists