chap limits to computation /return true if "proghalts when given itself as input bool selfhalt(string progif (halt(progprog)return trueelse return false/return the reverse of what selfhalt returns on "progvoid contrary(string progif (selfhalt(prog)while (true)/go into an infinite loop what happens if we make program whose sole purpose is to execute the function contrary and run that program with itself as inputone possibility is that the call to selfhalt returns truethat isselfhalt claims that contrary will halt when run on itself in that casecontrary goes into an infinite loop (and thus does not halton the other handif selfhalt returns falsethen halt is proclaiming that contrary does not halt on itselfand contrary then returnsthat isit halts thuscontrary does the contrary of what halt says that it will do the action of contrary is logically inconsistent with the assumption that halt solves the halting problem correctly there are no other assumptions we made that might cause this inconsistency thusby contradictionwe have proved that halt cannot solve the halting problem correctlyand thus there is no program that can solve the halting problem now that we have proved that the halting problem is unsolvablewe can use reduction arguments to prove that other problems are also unsolvable the strategy is to assume the existence of computer program that solves the problem in question and use that program to solve another problem that is already known to be unsolvable example consider the following variation on the halting problem given computer programwill it halt when its input is the empty string ( will it halt when it is given no input)to prove that this problem is unsolvablewe will employ standard technique for computability proofsuse computer program to modify another computer program proofassume that there is function ehalt that determines whether given program halts when given no input recall that our proof for the halting problem involved functions that took as parameters string representing program and another string representing an input consider