I'm going over the proof for The Halting Problem in Intro to the Theory of Computation by Sipser and my main concern is about the proof below:
If TM M doesn't know when it's looping (it can't accept or reject which is why a TM is Turing Recognizable for all strings), then how would could the decider H decide if M could possibly be in a loop? The same problem will carry through when TM D does its processing.
After reading this and trying to visualize the proof I came up with this code which is a simplified version of the code in this answer to a related question:
function halts(func) {
// Insert code here that returns "true" if "func" halts and "false" otherwise.
}
function deceiver() {
if(halts(deceiver))
while(true) { }
}
If halts(deceiver)
returns true
, deceiver
will run forever, and if it returns false
, deceiver
will halt, which contradicts the definition of halts
. Hence, the function halts
is impossible.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With