The undecidability of the halting problem is the theorem, proved by Alan Turing in 1936, that no single general algorithm can determine, for every possible computer program and input, whether that program will eventually halt or run forever. It was among the first problems shown to be algorithmically unsolvable and it established a fundamental limit on what computation can ever achieve.
Facts
StatementNo general algorithm can correctly decide, for every possible pairing of a computer program and an input, whether that program will eventually halt or run forever; the halting problem is therefore undecidable. 1 Classification
Statement Form Connections
Sources
1. Undecidability of the Halting Problem (Wikipedia)
Wikimedia Foundationlead section, first paragraphQuote, lead section, first paragraph
Alan Turing proved in 1937 that the halting problem is undecidable, meaning that no general algorithm exists that can correctly solve the problem for all possible program-input pairs.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.