Recursion - Java Concepts - page 834

}
}

Now ask yourself: What does the halt checker answer when asked whether K halts
when given K as the input? Maybe it finds out that K gets into an infinite loop with
such an input. But wait, that can't be right. That would mean that
checker.check(r, r) returns false when r is the program code of K. As
you can plainly see, in that case, the killer method returns, so K didn't get into an
infinite loop. That shows that K must halt when analyzing itself, so
checker.check(r, r) should return true . But then the killer method
doesn't terminateȌit goes into an infinite loop. That shows that it is logically
impossible to implement a program that can check whether every program halts on a
particular input.

It is sobering to know that there are limits to computing. There are problems that no
computer program, no matter how ingenious, can answer.

Theoretical computer scientists are working on other research involving the nature of
computation. One important question that remains unsettled to this day deals with
problems that in practice are very time-consuming to solve. It may be that these
problems are intrinsically hard, in which case it would be pointless to try to look for
better algorithms. Such theoretical research ca n have important practical
applications. For example, right now, nobody knows whether the most common
encryption schemes used today could be broken by discovering a new algorithm (see
Random Fact 19.1 for more information on encryption algorithms). Knowing that no
fast algorithms exist for breaking a particular code could make us feel more
comfortable about the security of encryption.

610
611

13.5 Mutual Recursions

In the preceding examples, a method called itself to solve a simpler problem.
Sometimes, a set of cooperating methods calls each other in a recursive fashion. In
this section, we will explore a typical situation of such a mutual recursion. This
technique is significantly more advanced than the simple recursion that we discussed
in the preceding sections. Feel free to skip this section if this is your first exposure to
recursion.