Take the 2-minute tour ×
TeX - LaTeX Stack Exchange is a question and answer site for users of TeX, LaTeX, ConTeXt, and related typesetting systems. It's 100% free, no registration required.

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

share|improve this question
68  
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 '12 at 18:10
    
@MartinScharrer: Just as I thought, I would gladly accept your answer as official answer. –  nimcap May 31 '12 at 18:47

9 Answers 9

up vote 70 down vote accepted

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.

share|improve this answer
5  
+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 '12 at 8:41
3  
@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 '12 at 8:47
1  
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 '12 at 14: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.

share|improve this answer
10  
"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 or`goto` 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 '12 at 20:45
2  
HTML+CSS is an example of a complete layouting language that isn't Turing complete. –  Lie Ryan Jun 1 '12 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 '12 at 0:17
1  
BTW, @Daniel, it's "Turing" (named after Alan Turing), not "Touring". –  mlp Jun 1 '12 at 5:13
5  
IF you haven't got any comments to make ON THIS ANSWER, please take this discussion elsewhere. –  David Carlisle Jun 2 '12 at 19:06

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:

share|improve this answer
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 '12 at 19:19
1  
How do these potentially problematic features relate to whether the program is Turing-complete? –  Mico May 31 '12 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 '12 at 19:36
    
Do most distros disable reading the first line of the input for command-line switches? According to the comp.text.tex thread referenced above, you can put %& -enable-write18 at the beginning of a file to enable write18 even if it's disabled by default. (Although perhaps that is MikTeX-specific?) –  Todd Lehman May 31 '12 at 23:11
    
@ToddLehman: In TeX Live 2012, parsing of the first line of input files is enabled, but specifying %& -shell-escape has no effect. –  mhp Jun 1 '12 at 20:00

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.

share|improve this answer
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 '12 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 '12 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 '12 at 20:02
4  
@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 '12 at 20:20

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.

share|improve this answer
    
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 '12 at 18:49
2  
@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 '12 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 '13 at 22:53
    
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 '13 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 '13 at 16:39

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.

share|improve this answer

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

share|improve this answer
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 '12 at 23:13
    
Thanks @barbara, great article! :) –  Paulo Cereda Jun 1 '12 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... –  tohecz Jun 2 '12 at 11:53

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.

share|improve this answer
7  
That indeed are points that actually are related to Turing-completenes and that really do matter. –  Daniel Jun 2 '12 at 8:05
    
Great answer, Stephan! :) –  Paulo Cereda Jun 2 '12 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 '12 at 21:28

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)

share|improve this answer
    
So your point is that TeX is accidentally Turing-complete? With what I should compare this? –  percusse Sep 30 '12 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 '12 at 23:28
    
I've been trying to find the story you mention via Google, and haven't had much luck... –  Mohan Oct 1 '12 at 18:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.