Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How does this proof, that the halting problem is undecidable, work?

Tags:

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.

the halting problem is undecideable

like image 706
jfisk Avatar asked Dec 06 '11 01:12

jfisk


1 Answers

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.

like image 79
Juan Avatar answered Sep 22 '22 01:09

Juan