fn halts(program: A) -> bool
fn b(program: A) {
if halts(A) {
loop {}
} else {
return ();
}
}
What happens if we pass b
to b()
?
- If
halts(b)
istrue
, thenb(b)
will loop forever. - If
halts(b)
isfalse
, thenb(b)
will halt.
So halts(b)
is true
if and only if halts(b)
is false
.
This is a contradiction, so halts(b)
is undecidable.