chap limits to computation this does not mean that computer program cannot be written that works on special casespossibly even on most programs that we would be interested in checking for examplesome compilers will check if the control expression for while loop is constant expression that evaluates to false if it isthe compiler will issue warning that the while loop code will never be executed howeverit is not possible to write computer program that can check for all input programs whether specified line of code will be executed when the program is given some specified input another unsolvable problem is whether program contains computer virus the property "contains computer virusis matter of behavior thusit is not possible to determine positively whether an arbitrary program contains computer virus fortunatelythere are many good heuristics for determining if program is likely to contain virusand it is usually possible to determine if program contains particular virusat least for the ones that are now known real virus checkers do pretty good jobbutit will always be possible for malicious people to invent new viruses that no existing virus checker can recognize further reading the classic text on the theory of -completeness is computers and intractabilitya guide to the theory of -completeness by garey and johnston [gj the traveling salesman problemedited by lawler et al [llks ]discusses many approaches to finding an acceptable solution to this particular -complete problem in reasonable amount of time for more information about the collatz function see "on the ups and downs of hailstone numbersby hayes [hay ]and "the problem and its generalizationsby lagarias [lag for an introduction to the field of computability and impossible problemssee discrete structureslogicand computability by james hein [hei exercises consider this algorithm for finding the maximum element in an arrayfirst sort the array and then select the last (maximumelement what (if anythingdoes this reduction tell us about the upper and lower bounds to the problem of finding the maximum element in sequencewhy can we not reduce sorting to finding the maximum element use reduction to prove that squaring an matrix is just as expensive (asymptoticallyas multiplying two matrices