Are there any disadvantages of TeX being Turing complete?

Question

I have read that TeX is Turing complete. I was wondering if making TeX Turing complete gave raise to unwanted effects.

Answer 1

Yes, there is a drawback: instead of "only" writing your thesis you start to code LaTeX packages like tikz-timing, standalone, svn-multi and many more. This wouldn't happen if it wasn't Turing complete.

---

Having it Turing complete enables an infinite number of additions, but of course required some initial investment when TeX was created. All TeX distributions I know make sure that TeX's power can't be used to harm the user, e.g. shell escape is disabled or restricted by default and you can't overwrite files using an absolute or parent folder etc. There is no real drawback for the user but a lot of benefits.

Answer 2

First Disadvantage: Hard to Analyse

One big disadvantage of being Turing complete is that TeX "programs" are subject to Rice's theorem, which basically means that for a given document d and TeX source file f, it is undecidable in general whether f generates d (or not).

There are a lot of corollaries to this theorem, but for TeX the most important one is that it is impossible in general to find out what exactly some piece of TeX source does, especially not with another computer program, short of executing it with TeX.

This actually lies behind the apparent impossibility to convert TeX into something else. It is simply computationally impossible unless "something else" is either just another syntactic variant of TeX source or somehow "isomorphic" with dvi or pdf.

This extends to seemingly simple tasks, i.e. it is also undecidable, in general, whether (or not) a piece of TeX source will produce the letter "d" at some point in time, will have undefined labels, will output colored text, will produce more than one page or whatever other basic property of a document you'd like to find out.

This situation is completely different for non-Turing-complete notations like RTF, HTML or FO.

Second Disadvantage: High Demands on Engines

Another consequence is that there is no "almost compliant" TeX engine. While it is no problem to support a subset of HTML because it is rather easy to estimate what happens when parts of the formalism are not supported, for TeX even the slightest deviation from the intended behaviour can lead to arbitrary devastating and unexpected consequences.

This means all "alternative" TeX engines either just don't get the basic task of document generation right (like ant or exTeX), or are so near to the original TeX that it is hard to see what alternative they really offer (like NTS).

The only thing that works is to start from the original TeX engine and add things on top which it couldn't do before, like with pdftex, eTeX, xetex or LuaTeX.

Third Disadvantage: Low Fault Tolerance

Turing-complete formalisms have so much expressive power that it is hard to deal gracefully with errors.

If I randomly replace half of a HTML file by gibberish, then a browser will still be able to render those parts which look like HTML almost correctly.

For a "TeX program" with errors, if it doesn't conform to some strict "markupish" syntax standard like LaTeX, the engine will be unable to generate meaningful output from the correct parts if the computation as a whole fails.

Answer 3

Turing's result is that essentially any non trivial programming language is computationally equivalent. If it has the power to encode arithmetic, it can do anything that any programming language can do (rough paraphrase).

Thus if you want a formatting language that can do arithmetic, or to be able to measure boxes and take different decisions depending on lengths matching user-specifiable conditions, then a Turing complete language is almost inevitable.

Answer 4

One unwanted effect is the possibility for creating and releasing malicious code, because TeX has the capability to write to the local filesystem. Also, using the special modes for passing content through to PDF machinery, it is possible to embed malicious content inside a PDF document generated from TeX source.

Neither of these possibilities actually require that TeX be Turing-complete, but it becomes much easier to hide malicious code if it is.

Some links:

• Don't take LaTeX files from strangers — Steve Checkoway, Hovav Shacham, and Eric Rescorla [2011-04-06].

• LaTeX malicious PDF Generation — Brandon Dixon [2011-10-07]

• Malicious commands in LaTeX — comp.text.tex thread [2008-08-06]

Answer 5

Turing completeness implies that processing a document might not terminate. Obviously this is a bug caused by looping code but that it is possible at all could run against intuition of non-programmers. Personally I am willing to pay this price in exchange for the power it gains but it is one of the costs of Turing completeness.

Addendum: The undecidability of the halting problem for Turing-complete languages further implies that TeX cannot incorporate a program analysis phase to detect non-terminating code. While possible, it also does not implement a heuristic.

Another consequence is that LaTeX code is difficult to analyze in general without executing it. This makes it hard to analyze it in particular for security problems like it would be useful if LaTeX is provided as an online service.

Answer 6

There is quite some confusion about the exact meaning and relevance of Turing-completness in the question as well as in the answers so far.

@Mico I guess the more general implicit question is "What are the disadvantages to TeX being so darn powerful?" – Seamus

Seamus' comment puts it very well. In fact, I am pretty sure that neither the examples given by Martin, nor David nor Todd actually require TeX to be Turing-complete for any practical purpose.

Turing-completeness basically requires three properties:

1. Variables (registers) that can be modified by primitive arithmetic: An inc operation (+1) is enough.
2. A test operation (if)
3. An endless loop construct, such as goto or while or recursion.

Number 3 is the important point here. You need to have the necessity to do "endless calculations" to actually require Turing-completeness. Given that for any practical purpose the output of TeX is finite, intuitively Turing-completeness is not really required. (Of course, we do need \loop and recursive macro expansion, but it would probably be sufficient if we bound them to, lets say, a billion iterations.)

The only real disadvantage of Turing-completeness is that the halting problem (the question if a program eventually terminates or not) is undecidable.

Answer 7

_{I tried to restrain myself from answering this question, but I could not hold it. :)}

Simply put, Turing complete means that you can perform any computational task (well, any Turing-computable function). If you can simulate a universal Turing machine, you have a Turing complete system.

_{Gosh, I wrote "Turing" four times in that sentence. :)}

Now, to the point of your question: the disadvantages of TeX being Turing complete. I'd say that, despite the fact that you can perform any task, there's no garantee for it being executed efficiently. And being able to do any task doesn't mean it will be easy. At all. So it'd say the tricky part here is how.

TeX being Turing complete means that I could, say, write something extremely complex with it. I could, but just don't ask me how. :)

Answer 8

One of the minor side effects is frustrating people who think they're going to knock off a quick little TeX-to-Foo converter. Or rather it frustrates people who find the resulting converter on the internet and expect it to do something sensible with the document they want to convert.

To actually work, every TeX-to-Foo converter has to be a full blown TeX compiler.

Answer 9

Compare the following:

"It's risky to design minilanguages that are only accidentally Turing-complete. If you do this the odds are good that, sometime in the future, some clever fellow is going to think he needs to press your language into doing loops and conditionals for him. Because these are only available in an obfuscated way, he'll produce obfuscated code. The results may be serviceable in the short term, but are likely to be a nightmare for those who come after him."

The Art of Unix Programming, Eric S. Raymond

( http://www.catb.org/esr/writings/taoup/html/ch08s03.html)