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

halting-problem
jfisk picture jfisk · Dec 6, 2011 · Viewed 18.1k times · Source

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

Answer

Juan picture Juan · Nov 27, 2013

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.

Related questions

Proof that the halting problem is NP-hard?

In this answer to a question about the definitions of NP, NP-hard, and NP-complete, Jason makes the claim that The halting problem is the classic NP-hard problem. This is the problem that given a program P and input I, will …

Read More
What exactly is the halting problem?

Whenever people ask about the halting problem as it pertains to programming, people respond with "If you just add one loop, you've got the halting program and therefore you can't automate task" Makes sense. If your program has an infinite …

Read More
Infinite loops in Java

Look at the following infinite while loop in Java. It causes a compile-time error for the statement below it. while(true) { System.out.println("inside while"); } System.out.println("while terminated"); //Unreachable statement - compiler-error. The following same infinite while …

Read More