algorithm design and recursion the halting problem let' just imagine for moment that this book has inspired you to pursue career as computer professional it' now six years laterand you are well-established software developer one dayyour boss comes to you with an important new projectand you are supposed to drop everything and get right on it it seems that your boss has had sudden inspiration on how your company can double its productivity you've recently hired number of rather inexperienced programmersand debugging their code is taking an inordinate amount of time apparentlythese wet-behind-the-ears newbies tend to accidentally write lot of programs with infinite loops (you've been thereright?they spend half the day waiting for their computers to reboot so they can track down the bugs your boss wants you to design program that can analyze source code and detect whether it contains an infinite loop before actually running it on test data this sounds like an interesting problemso you decide to give it try as usualyou start by carefully considering the specifications basicallyyou want program that can read other programs and determine whether they contain an infinite loop of coursethe behavior of program is determined not just by its codebut also by the input it is given when it runs in order to determine if there is an infinite loopyou will have to know what the input will be you decide on the following specificationprogramhalting analyzer inputsa python program file the input for the program outputs"okif the program will eventually stop "faultyif the program has an infinite loop right away you notice something interesting about this program this is program that examines other programs you may not have written many of these beforebut you know that it' not problem in principle after allcompilers and interpreters are common examples of programs that analyze other programs you can represent both the program that is being analyzed and the proposed input to the program as python strings there is something else very interesting about this assignment you are being asked to solve very famous puzzle known and the halting problemand it' unsolvable there is no possible algorithm that can meet this specificationnoticei' not just saying that no one has been able to do this beforei' saying that this problem can never be solvedin principle how do know that there is no solution to this problemthis is question that all the design skills in the world will not answer design can show that problems are solvablebut it can never prove that problem is not solvable to do thatwe need to use our analytical skills one way to prove that something is impossible is to first assume that it is possible and show that this leads to contradiction mathematicians call this proof by contradiction we'll use this technique to show that the halting problem cannot be solved