Search code examples
algorithmtheorycomputation-theoryhalting-problem

what is exactly the reason of halting


The halting problem states that given an input and a program, there is no algorithm that can decide weather the program will halt. This renders this problem undecidable. My misunderstanding of the halting problem is that, can't we just create another program that could check if the program has infinite loops. I just mean that it may be possible to check the cases where a loop will not stop and based on that decides if the program will halt or not. Please could you let me know what's wrong of my understanding of this problem?


Solution

  • Well, you know, the proof of the halting problem is pretty trivial. Let's assume you have a program that tells you whether a given program will halt or not (forget about inputs for simplicity). Let's call this program doesHalt(program). Let's now write a new program called

    myHalt() 
      if doesHalt(myHalt):
         infinite loop
      else 
         return
    

    What should be the return value of

    doesHalt(myHalt)
    

    To answer your specific question: how does your program examining loops will know whether a given loop halt or not? Does the loop

    for (i = 1; i += 10; ) {
       if (i == 7) break;
    }
    

    loop forever or not? How did your program figure that out?