A Simple Proof for the Turing-Completeness of XSLT and XQuery

Abstract

The World Wide Web Consortium recommends both XSLT and XQuery as query languages for XML documents. XSLT, originally designed to transform XML into XSL-FO, is nowadays a fully grown XML query language that is mostly suited for use by machines. XQuery on the other hand was particularly designed to be easily used by humans. Both languages are known to be Turing-complete. We provide here a very simple proof of Turing-completeness of XSLT and XQuery by coding -recursive functions thereby showing that Turing-completeness is a consequence of a few basic and fundamental features of both languages.