2020-10-01
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.