W3C home > Mailing lists > Public > www-tag@w3.org > December 2005

Re: Initial Draft Finding on Principle of Least Power

From: Jon Hanna <jon@hackcraft.net>
Date: Thu, 22 Dec 2005 16:19:00 +0000
Message-ID: <43AAD1F4.1070709@hackcraft.net>
To: www-tag@w3.org

Another thought on this:

The client-side Javascript on most browsers (all of them AFAIK) is not 
strictly Turing-complete because the interpreter is interrupts the 
processing after a certain length of time (with the intention of 
stopping infinite loops or other code that will run for a very long 
time) - a languge executed any such interpreter is not strictly Turing 
complete.

Conversely while the processing of XML entities is provably finite it is 
possible in practice to write a short XML document that will take 
gigabytes of storage to process in any sort of tree model (DOM etc.) and 
an impractical length of time to process in any sort of single-pass 
parsing (SAX etc.)

The former raises a nit-picking point about how we've been labelling 
languages, but more importantly the two show a case where the 
theoretical advantage of static analysis of XML's "lesser power" doesn't 
hold in practice.
Received on Thursday, 22 December 2005 16:22:04 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 22:56:10 UTC