ConceptTheory & Algos
Halting problem
The problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Opens up
Concepts that name this one as a prerequisite.
Lecturers
4Each in their own terms, from the easiest level.
Hal Abelson & Gerald Jay Sussman
Ryan O'Donnell
The problem of determining, given a Turing machine and an input string, whether the Turing machine will halt when run on that input string.Erik Demaine
The halting problem asks whether a given computer program will ever halt or stop running.Bruno Bauwens
The set of pairs consisting of a Turing machine encoding and an input for which the machine eventually halts.
Lectures that assume it
1Connections
13The lectures that define it or assume it, and the concepts next to it.