Introduction to Turing, computability, and the "halting problem"
Introduction to Turing, computability, and the "halting problem"
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)
External Links