The problem of deciding, given an arbitrary program and its input, whether that program will eventually halt or run forever; proven by Alan Turing to be undecidable, meaning no general algorithm can solve it for every possible program, a foundational limit on what computation can determine about itself.
Facts
Core PrincipleDeciding, given an arbitrary computer program and an input, whether the program will eventually halt or run forever. 1 Connections
In Field
Invented
Alan Turing proved the undecidability of the halting problem in his foundational 1936 paper on computable numbers.
Sources
1. Halting problem, Wikipedia
Lead section, first sentence
the halting problem is the decision problem of, given an arbitrary computer program and an input, determining whether said program will eventually finish running and halt, or will continue to run forever.
Lead section, second sentence
Alan Turing proved in 1937 that the halting problem is undecidable
View the SourceReader 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.