On Tue, 4 Aug 1998, Paul Leach wrote: > The possibility of infinite loops and infinite recursion in HTML has been > discussed on the lists before. Trying to detect and prevent them is an > instance of the "Turing machine halting" problem, and it is well known among > computer scientists to be impossible. No, it is an instance of "directed graph search halting" problem. The programs can always detect a finite loop because it has found the loop iff the current object name (URL) is already present on the stack. (Assuming your computer has enough memory to remember it.) The only way to cause infinite recursion is to create an "infinite loop" of names. Natural numbers generate a simple example of such a "loop." Object N includes object N+1, N+1 includes N+2... et cetera ad infinitum. Let's assume the natural number N is encoded as the sequence of N "1"'s. Adding 1 to such a number is as easy as prepending or appending one "1" to it. A program acting as a filter can do it in O(N) time and O(1) space. Therefore it is feasible to create a "server" which generates an infinite chain of objects. Nevertheless, the defense is trivial: it is always possible to impose an artificial (perhaps customizable) limit on the depth of recursion, the number of searched objects or anything else. Or let the user interrupt the search when his/her patience is over. --Pavel Kankovsky aka Peak [ Boycott Microsoft--http://www.vcnet.com/bms ] "You can't be truly paranoid unless you're sure they have already got you."
This archive was generated by hypermail 2b30 : Fri Apr 13 2001 - 14:11:27 PDT