Re: [Fwd: Re: Language is not markup and markup is not language.]

[Paul Prescod <paul@xxxxxxxxxxx>]

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
 http://itrc.uwaterloo.ca/~papresco

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