RE: [xsl] turing complete?

["Michael Kay" <mhkay at iclway dot co dot uk>]

> Someone recently caught me off gaurd asking if XSLT is turing
> complete.
>
> But I am still wondering why this is even important. How would you
> answer the question "Is XSLT turing complete"?

Yes, XSLT is Turing complete. I seem to recall someone providing a trivial
proof of that on this list.

The question is important because of its consequences. For example, it means
it is possible to write stylesheets that loop indefinitely, and that it is
sometimes impossible to detect such stylesheets by static analysis.

It also means that anyone who tells you that they are using Javascript
because "XSLT cannot do xxx" is wrong (though they might be correct if they
argued instead that "XSLT can't do xxx easily/efficiently).

Incidentally, SQL in its original form is not Turing-complete, and although
you can easily write an SQL SELECT statement that takes months to execute,
you can't write one that loops indefinitely.

Mike Kay
Software AG


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list