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

Re: [Fwd: Re: Language is not markup and markup is not langu

Subject: Re: [Fwd: Re: Language is not markup and markup is not language.]
From: Paul Prescod <paul@xxxxxxxxxxx>
Date: Thu, 13 May 1999 19:55:43 -0500
turing complete languages
Kay Michael wrote:
> > From: David LeBlanc [mailto:whisper@xxxxxxxxxxxxx]
> >
> > Can you write an XSL processor in XSL? If so, I would agree
> > it's Turing complete; otherwise not.
> >
> You are suggesting that the statements "XSL is turing complete" and "An XSL
> processor can be written in XSL" are equivalent. Another interesting
> assertion, can you prove or justify it?

Well, James Clark has demonstrated (though not, admittedly, proved) that
XSL has the features required to be Turing complete. That's good enough as
an axiom for me. 

>From there: any Turing complete language can emulate any other (modulo
I/O) so if XSL can emulate XSL then XSL inherits Turing-completeness from
XSL. Clear?

> I am not a computer scientist, but isn't that the point of the theory
> of Turing completeness?  If an XSL processor can be written in one
> Turing-complete language, one can be written in any Turing-complete
> language.  If that's true, then "X is Turing-complete" and "An XSL
> processor can be written in X" are equivalent.  No?

No, if XSL is not Turing complete then XSL could be implemented in a
non-Turing complete language. If we presume that XSL is not Turing
complete then here is a non-Turing complete language that can implement
XSL: "the source code of XT" (a language containing the source code for XT
and no other strings). This language could be defined as a really weird
regular expression or context free grammar consisting mostly of a single
hard-wired text string.

That language is only Turing complete if XSL is Turing complete.

 Paul Prescod  - ISOGEN Consulting Engineer speaking for only himself

Earth will soon support only survivor species -- dandelions, roaches, 
lizards, thistles, crows, rats. Not to mention 10 billion humans.
	- Planet of the Weeds, Harper's Magazine, October 1998

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

Current Thread


Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
First Name
Last Name
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.