Is this illustration of the haling problem correct?
function halts(func) {
// Insert code here that returns "true" if "func" halts and "false" otherwise.
}
function deceiver() {
if(halts(deceiver))
while(true) { }
}
If so, why do so many descriptions involve a function which takes two arguments, where one is the program and the other is the same program as program input?
E.g.:
Assume we have a function Halts(P, W) that halts if program P halts on input W. Then we write this perfectly-valid Python function:
def K(P):
if (Halts(P, P)):
while True: pass # run forever
else:
return 42 # halt!
Now, what happens when we call K(K)? If Halts(K,K) is True, then K(K) hangs (runs forever) If Halts(K,K) is False, then K(K) halts So either way, Halts(K,K) is wrong. Thus, the Halts function cannot exist!
