> -----Original Message----- > From: Pavel Kankovsky [mailto:peakat_private] > Sent: Wednesday, August 05, 1998 2:29 AM > To: BUGTRAQat_private > Subject: Re: Object tag crashes Internet Explorer 4.0 > > > 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. For the specific example of values of the "data" field in the object tag, you're right. However, web pages can contain more complex constructs than that, constructs that can make them into (in the general case) full fledged, Turing complete, programs. As many people have pointed out to me as if I were an idiot, in many cases, whether these halt is also determinable by examining the page. I knew that. However, it is not possible in general to so determine -- and it was to the more general problem that I was referring, not the specific example. That's the context I intended to set by the phrase "the possibility of infinite loops and infinite recursion in HTML has been discussed before". Judged by the reactions, that didn't come across. There was also controversy over whether HTML, strictly defined, was Turing complete. I will plead guilty to not knowing that -- HTML 1.0 was surely not Turing complete, but I don't know exactly what specification introduces the ability to script, and whether it was "HTML n.0" or DHTML, or what. > > 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. We do. It's the depth of the stack. The actual objection of many correspondents, after their joy in pointing out my incompetence to me fades, seems to be the behavior of IE when the stack overflows. But no one has been very clear about what it is in the cases they've seen (if they've indeed seen any); when IE 4 has died on me (all pre-SP1 of course :-), it restarted and about all I lost was the history list that drives the "back" button. If it doesn't restart as clean as that in all cases of stack overflow, then that should be looked at, and reports would be appreciated, especially if it can be reporduced easily. Paul
This archive was generated by hypermail 2b30 : Fri Apr 13 2001 - 14:11:39 PDT