impossible problems even the best programmer sometimes writes program that goes into an infinite loop of coursewhen you run program that has not stoppedyou do not know for sure if it is just slow program or program in an infinite loop after "enough time,you shut it down wouldn' it be great if your compiler could look at your program and tell you before you run it that it might get into an infinite loopalternativelygiven program and particular inputit would be useful to know if executing the program on that input will result in an infinite loop without actually running the program unfortunatelythe halting problemas this is calledcannot be solved there will never be computer program that can positively determinefor an arbitrary program pif will halt for all input nor will there even be computer program that can positively determine if arbitrary program will halt for specified input how can this beprogrammers look at programs regularly to determine if they will halt surely this can be automated as warning to those who believe any program can be analyzed in this waycarefully examine the following code fragment before reading on while ( if (odd( ) else this is famous piece of code the sequence of values that is assigned to by this code is sometimes called the collatz sequence for input value does this code fragment halt for all values of nnobody knows the answer every input that has been tried halts but does it always haltnote that for this code fragmentbecause we do not know if it haltswe also do not know an upper bound for its running time as for the lower boundwe can easily show ohm(log )(see exercise personallyi have faith that someday some smart person will completely analyze the collatz function and prove once and for all that the code fragment halts for all values of doing so may well give us techniques that advance our ability to do algorithm analysis in general unfortunatelyproofs from computability -the branch of computer science that studies what is impossible to do with computer -compel us to believe that there will always be another bit of program code that we cannot analyze this comes as result of the fact that the halting problem is unsolvable