75

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

Improve this question
2
  • 86
    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.
    – Martin Scharrer
    May 31, 2012 at 18:10
  • @MartinScharrer: Just as I thought, I would gladly accept your answer as official answer.
    – nimcap
    May 31, 2012 at 18:47

9 Answers 9

Reset to default
93

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.

Improve this answer
3
  • 8
    +1 and more for investing so much time on great packages that have made not only my life so much easier! The answer itself, however, is just wrong, technically and socially: 1: I doubt that for any of the algorithms you have implemented Touring-completeness is actually required. 2: All good PhD students spend (too much?) time on (over-engineered) side projects that are supposed to ease their writing. I have seen many; there is absolutely no evidence, that the turing-completeness of the tool is the driver for procrastination :-)
    – Daniel
    Jun 2, 2012 at 8:41
  • 4
    @Daniel: I implemented parsers in TeX. I doubt this is possible without Turing completeness. Also, my point is that this wouldn't have happened without (La)TeX being so extensible. Without it I would have of course found other ways for procrastination. So my answer stands. ;-)
    – Martin Scharrer
    Jun 2, 2012 at 8:47
  • 3
    Parsing is a point, but only if the language the parser is supposed to accept is context sensitive; context-free or regular languages could be parsed by simpler machines. Well, I will now stop being picky. What really matters is that, even though you have been providing us with many great packages, the halting problem of thesis writing turned out as decidable :-)
    – Daniel
    Jun 3, 2012 at 14:34
97

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.

Improve this answer
5
  • 8
    That indeed are points that actually are related to Turing-completenes and that really do matter.
    – Daniel
    Jun 2, 2012 at 8:05
  • 2
    Great answer, Stephan! :)
    – Paulo Cereda
    Jun 2, 2012 at 11:06
  • @PauloCereda I've always considered Rice's Theorem the most influential result around the halting problem because it is the basis for a large part of Software industry (everything having to do with testing, QA etc.).
    – Stephan Lehmke
    Jun 2, 2012 at 21:28
  • 1
    The first two points are very well made. With respect to the third point, language power can be combined with good fault tolerance, as is seen for example in Prolog. The trouble with Latex is that it is implemented as a layer that tries to abstract away from the Tex engine, complicating error reporting and recovery. Having a Plain Tex document compile automatically to the end usually gives output that does a good job of rendering what can be rendered and an intelligible .log file.
    – Charles Stewart
    Dec 12, 2019 at 8:02
  • @CharlesStewart Having debugged my share of Prolog programs, I beg to differ (silent failure WTF) What you say about plain TeX is true only for "markupish" documents which don't look like algorithms generating text. The more "program-like" your document becomes, the more likely you are to end up with just ** and no output and no explanation.
    – Stephan Lehmke
    Dec 26, 2020 at 1:29
34

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.

Improve this answer
16
  • 12
    "almost inevitable" is debatable here, as neither arithmetic nor the ability to measure boxes and take decisions requires Touring-completeness. Basically, touring completeness requires three properties: (1) variables and the possibility to do arithmetic on them (an inc operation is enough) (2) a test operation (if) and (3) an endless loop construct (such as recursion orgoto or while). Number 3 is the key point here: Only if you really need some sort of "endless computation", Touring-completness is inevitable.
    – Daniel
    May 31, 2012 at 20:45
  • 3
    HTML+CSS is an example of a complete layouting language that isn't Turing complete.
    – Lie Ryan
    Jun 1, 2012 at 0:05
  • 5
    @LieRyan also of course the vast majority of complex layouts in a web page (such as this one) use javascript in addition to css and that of course is Turing complete again.
    – David Carlisle
    Jun 1, 2012 at 0:17
  • 2
    @LieRyan: CSS3 is turing complete. That doesn't change the fact that previous versions weren't and were still sufficiently capable layouting systems.
    – Joachim Sauer
    Jun 1, 2012 at 6:38
  • 5
    IF you haven't got any comments to make ON THIS ANSWER, please take this discussion elsewhere.
    – David Carlisle
    Jun 2, 2012 at 19:06
32

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:

Improve this answer
10
  • 2
    This is limited by sensible write18 limitations that should be standard on most distributions. A related point is that some inputs to TeX programs don't halt. This isn't in general a problem, but if you want to build a service that runs TeX on a server, then there is a danger of malicious people clogging your server with infinite loops.
    – Seamus
    May 31, 2012 at 19:19
  • 1
    How do these potentially problematic features relate to whether the program is Turing-complete?
    – Mico
    May 31, 2012 at 19:19
  • 3
    @Mico I guess the more general implicit question is "What are the disadvantages to TeX being so darn powerful?"
    – Seamus
    May 31, 2012 at 19:36
  • 1
    @Mico Turing completeness makes it easier to hide the dangerous code. I'm sure you could use write18 without ever seeing this command in a TeX source and hence any naive analysis would not able to catch it.
    – Christian Lindig
    Jun 13, 2012 at 5:04
  • 1
    @Mico, as ChristianLindig mentioned, for some sub-Turing-complete languages it is possible to solve the halting problem (for example, trivially, in a total language (en.wikipedia.org/wiki/Total_functional_programming). On the other hand, it is guaranteed that, in a Turing complete language, not only are there programs that will not halt, but it is not even possible always to tell in advance (i.e., without running it) whether or not a given program will halt.
    – LSpice
    Jun 17, 2015 at 20:12
19

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.

Improve this answer
4
  • 6
    I have a feeling that even systems that fail to be Turing complete can have inputs that don't halt. So it's a cost of something strictly weaker than Turing completeness.
    – Seamus
    May 31, 2012 at 19:35
  • 5
    Having non terminating loops isn't directly related to Turing Completeness. It is trivial to design a language that isn't Turing Complete but has non-terminating programs. For example a language with a single command \wait that never terminates, would have that property., or less trivially a language without any of TeXs arithmetic or testing commands but which let you do \def\oops{\oops}\oops
    – David Carlisle
    May 31, 2012 at 19:35
  • 4
    I did not claim that non-termination implies Turing completeness. Hence, I agree that there exist non-Turing complete languages that permit to write non-terminating code. The question was about drawbacks of Turing completeness and possible non-termination is one such drawback.
    – Christian Lindig
    May 31, 2012 at 20:02
  • 5
    @DavidCarlisle,Seamus: Well, the important point here is that for a Touring-complete language the halting problem (will a program terminate or not) is undecidable, whereas for a regular language as sketched by David it is.
    – Daniel
    May 31, 2012 at 20:20
18

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.

Improve this answer
5
  • In tex/pdftex, tex the program uses only a fixed amount of memory. Isn't "infinite tape" also a requirement for a Turing machine?
    – Aditya
    Jun 2, 2012 at 18:49
  • 3
    @Aditya: That is true, "infinite state" is formally also a requirement of a Turing machine. So TeX as a language is turing-complete (TC), the tex machine that interprets this language, however, is actually a linear bounded automaton, LBA. This, of course, holds for any real-world computing machine (there is no computer with unlimited memory...), so in colloquial usage the term TC usually implies a "given that the machine is an LBA with enough memory".
    – Daniel
    Jun 3, 2012 at 7:39
  • (Why do people cling to state so much?) Turing completeness does not require state (so scrap #1), if you have functions, fun t f => t (~true) and fun t f => f (~false) can act as bools and if-construct at the same time (scrap #2). All you need is #3, e. g. in the form of recursion. (Untyped) lambda calculus has all you need, but three fixed functions suffice (actually, one is enough). And that can be done in TeX…
    – nobody
    Mar 28, 2013 at 22:53
  • 1
    Here you go: \def\k#1#2{#1} \def\s#1#2#3{#1{#3}{#2{#3}}} \def\X#1{#1\s\k} % one combinator to compute everything \def\I{\X\X} \def\S{\X{\X{\X{\X\X}}}} % S re-implemented on top of X \def\O{\S\I\I} \O\O % (constant space) endless loop, SII(SII) -> SII(SII)
    – nobody
    Mar 28, 2013 at 23:29
  • @nobody: Yes, SKI is Turing-complete, as are μ-recursive functions and all the other computation models that are based on recursion. However, recursive functions are way more than #3, they just hide "data state" in "control flow state" (#1) and conditionals in termination (#2). So they are all, but not minimal primitives (even though elegant).
    – Daniel
    Apr 1, 2013 at 16:39
17

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. :)

Improve this answer
3
  • 6
    an illustration of this appears in a tugboat article by Andrew Mark Greene, "BaSiX -- an interpreter written in TeX". (but just because you can, doesn't necessarily mean that you should.)
    – barbara beeton
    Jun 1, 2012 at 23:13
  • Thanks @barbara, great article! :)
    – Paulo Cereda
    Jun 1, 2012 at 23:37
  • The point about time efficiency of (La)TeX is really valid. I guess that everybody know what I speak about who used \tracingmacros once and had to go through the complete mess of (mostly font-related) macro listings...
    – yo'
    Jun 2, 2012 at 11:53
11

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.

Improve this answer
7

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)

Improve this answer
3
  • So your point is that TeX is accidentally Turing-complete? With what I should compare this?
    – percusse
    Sep 30, 2012 at 22:16
  • 3
    TeX is actually intentionally TC, as goes a well-known story of Knuth about its development. Nonetheless, this is very true.
    – Ryan Reich
    Sep 30, 2012 at 23:28
  • I've been trying to find the story you mention via Google, and haven't had much luck...
    – Mohan
    Oct 1, 2012 at 18:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .