<br><div class="gmail_quote">On Tue, Mar 13, 2012 at 12:29 PM, Philip TAYLOR <span dir="ltr"><<a href="mailto:P.Taylor@rhul.ac.uk" target="_blank">P.Taylor@rhul.ac.uk</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">


<div><br>
<br>
Stefan Löffler wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
[1] <off-topic>Is TeX Turing-complete?</off-topic><br>
</blockquote>
<br></div>
I have always [1] believed so.<span><font color="#888888"><br>
Philip Taylor<br>
--------<br>
[1] Where "always" is defined as "since 1986".<br>
</font></span></blockquote></div><br><div><br></div><div>TeX is worse than Turing-complete---most boring old Turing-complete programming languages can be completely parsed and deconstructed by a "dumb" syntax highlighter implemented in a few lines of regular expressions. TeX is __context sensitive__ and therefore also requires a __Turing-complete parser__.</div>


<div><br></div><div>This is why it is so difficult to deconstruct an arbitrary bit of TeX compared to most programming languages, like Python. Python can be parsed with a simple rule-based program while TeX has to be processed by a program that could also perform Lambda calculus[1], serve as a BASIC interpreter[2], or function as a control program for NASA's Mars rovers[3].</div>


<div><br></div><div>The parser for a language like Python cannot stray outside of the rules defined by the language grammer. The parser for a TeX document can typeset TeX, or be re-purposed do any other computable task if given the right input.</div>


<div><br></div><div>See the following TeX StackExchange question for proof and demonstrations:</div><div><br></div><div>  <a href="http://tex.stackexchange.com/questions/4201/is-there-a-bnf-grammar-of-the-tex-language" target="_blank">http://tex.stackexchange.com/questions/4201/is-there-a-bnf-grammar-of-the-tex-language</a></div>


<div><br></div><div>-Charlie</div><div><br></div><div>  [1]: <a href="http://ctan.org/pkg/lambda-lists" target="_blank">http://ctan.org/pkg/lambda-lists</a></div><div>  [2]: <a href="http://ctan.org/pkg/basix" target="_blank">http://ctan.org/pkg/basix</a></div>


<div>  [3]: <a href="http://sdh33b.blogspot.com/2008/07/icfp-contest-2008.html" target="_blank">http://sdh33b.blogspot.com/2008/07/icfp-contest-2008.html</a></div>