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 Turingcompleteness 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 > Turingcomplete language, one can be written in any Turingcomplete > language. If that's true, then "X is Turingcomplete" 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 nonTuring complete language. If we presume that XSL is not Turing complete then here is a nonTuring 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 hardwired 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 XSLList info and archive: http://www.mulberrytech.com/xsl/xsllist
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 