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 |
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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [Fwd: Re: Language is not marku, Chris Maden | Thread | RE: [Fwd: Re: Language is not marku, Vun Kannon, David |
auto/embed is not node transclusion, Paul Prescod | Date | Re: size?, Paul Prescod |
Month |