Home

# The Halting Problem cannot be solved

Wikipedia gives a nice, 1000-foot proof by contradiction to this problem. Imagine halts(f) exists and returns true or false for all functions. We could then use it to write a function such as:
function f() {
if (halts(f)) {
while (true) {
// Do nothing
}
}
}
Does f() halt? If it does, then halts(f) is true so we enter an infinite loop (which does not halt). If f does not halt, then we skip the loop and return immediately in which case it does halt. We’ve worked ourselves into a contradiction, and the only way out is if halts(f) does not exist as in our assumption.