[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: schema-aware XML parser (java heap error)

• To: mukul_gandhi@y...
• Subject: Re: schema-aware XML parser (java heap error)
• From: David Carlisle <davidc@n...>
• Date: Fri, 3 Jun 2005 10:38:13 +0100
• Cc: xml-dev@l...
• In-reply-to: <20050603053053.84512.qmail@w...> (messagefrom Mukul Gandhi on Thu, 2 Jun 2005 22:30:53 -0700 (PDT))
• References: <20050603053053.84512.qmail@w...>

> 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.

David

________________________________________________________________________
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:
http://www.star.net.uk
________________________________________________________________________

• References:
  • RE: schema-aware XML parser (java heap error)
    • From: Mukul Gandhi <mukul_gandhi@y...>

• Prev by Date: RE: schema-aware XML parser (java heap error)
• Next by Date: RE: schema-aware XML parser (java heap error)
• Previous by thread: RE: schema-aware XML parser (java heap error)
• Next by thread: RE: schema-aware XML parser (java heap error)
• Index(es):
  • Date
  • Thread