David Wyde

The Halting Problem


Are there problems that no computer can solve?

The Halting Problem: Proofs and Demos, 7 pages.

A program halts(f) determines if a function f terminates or runs forever. halts must handle three cases: 1) f halts, 2) f doesn’t halt, and 3) f halts if and only if a call to halts(f) returns false. Given these three types of input, halts returns a Boolean: true if f halts and false if f runs forever.

Computer science theory says that case 3) programs are contradictions that show halts cannot exist. I argue that all three cases are valid, but it is unclear how to categorize three types of programs into a true or false output without grouping two cases together.

After writing this paper, I saw that Eric Hehner came to similar conclusions. My main contributions are to simplify the problem to 3 inputs being mapped to 2 outputs, analyze Alan Turing’s 1954 paper in addition to his 1936 one, and provide Python sample code.