The halting problem is the problem of deciding, for an arbitrary program and input, if it will halt (stop running) or continue to run forever. No algorithm exists that solves the halting problem for all program-input pairs. This is proven by contradiction. If the algorithm existed, we could make a recursive function that checks itself with that algorithm, and then does the opposite: ```python def g(): if halts(g): loop_forever() ``` The halting problem is often mentioned to show that definable functions aren't always computable. [^1][^2] [^1]: _Wikipedia_. 2025. “Halting problem.” September 29. [https://en.wikipedia.org/w/index.php?title=Halting_problem&oldid=1313976458#Programming_consequences](https://en.wikipedia.org/w/index.php?title=Halting_problem&oldid=1313976458#Programming_consequences). [[HaltingProblem2025|Annotations]] [^2]: Alfonseca, Manuel, Manuel Cebrian, Antonio Fernandez Anta, Lorenzo Coviello, Andrés Abeliuk, and Iyad Rahwan. 2021. “Superintelligence Cannot Be Contained: Lessons from Computability Theory.” _Journal of Artificial Intelligence Research_ 70 (January): 65–76. [https://doi.org/10.1613/jair.1.12202](https://doi.org/10.1613/jair.1.12202). [[alfonsecaSuperintelligenceCannotBe2021|Annotations]]