OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help



   Re: [xml-dev] schema-aware XML parser (java heap error)

[ Lists Home | Date Index | Thread Index ]

> I have heard that XSLT 1.0 is Turing complete ..

yes, as far as any language on a real machine is. You need to accept
some finite approximation of an infinite tape  in practice, as not many
real machines have an infinite storage device (and XSLT can't actually
read and write to a file in the same run, so you need to model the tape
in memory, so you'd need infinite (virtual) memory).

> Is XSLT 2.0 also?

Clearly, as XSLT2 contains XSLT1 as a sublanguage (with minor differences
but not anything that would affect this)

> If yes, what will be the proof of this fact?

well there are I think some explict models of a turing machine in xslt1
(ask google) but the whole point of turing's result is that essentially
all programming paradigms are equivalent so long as you have the ability
to store a finite amount of state, and an unbounded (but finite) amount
of data, and the ability to to test values for equality and to read and
write data.

So it's pretty hard to have a language that has variable assignment and
an  if statement that is not turing complete, modulo the lack of an
infinite tape.


This e-mail has been scanned for all viruses by Star. The
service is powered by MessageLabs. For more information on a proactive
anti-virus service working around the clock, around the globe, visit:


News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 2001 XML.org. This site is hosted by OASIS