Troff supports both macro definitions using .de and branching using .if (see pages 5 and 6 of the Troff user's manual). In these two respects, it is very much like TeX. However, I don't know of highly complex programs written in Troff (unlike say TikZ for TeX). Is Troff Turing complete?


ESR's The Art of Unix Programming claims it is:

We'll examine troff in more detail in Chapter 18; for now, it's sufficient to note that it is a good example of an imperative minilanguage that borders on being a full-fledged interpreter (it has conditionals and recursion but not loops; it is accidentally Turing-complete).

("Accidentally" as opposed to m4, which is said to be "deliberately Turing-complete".)


Yes, troff is Turing-complete. It supports arbitrary recursion and conditional branching, which is sufficient. It also has registers and various other ways to store data, which gives you another path in again.

Turing completeness doesn't imply that highly complex programs are practical - just that they're theoretically possible, somehow, at some level of remove - and nor does its absence imply that they aren't, so neither troff's being Turing-complete nor the absence of complex programs don't suggest anything much one way or the other about that.

Turing completeness is not, generally, a property that means anything useful for you the user. All it means is that you can simulate a Turing machine with it, not that you'd want to, and not that the output that you'd get from it is anything like what you'd expect to read. The input or output might just be a number, or even the number of times something appears, rather than something useful, and the sorts of machine you end up simulating and their programs are often barely comprehensible to start with.

Many languages and systems are incidentally Turing-complete but not reasonably applicable for any actual programming in that subset (for example, Conway's Game of Life or CSS), and some languages that are useful for real programming are not Turing-complete (for example, Agda). The defining characteristics really are that you can

  • keep going forever
  • remember as much data as you want
  • choose what, if anything, to do next

Often those properties - particularly non-termination - are actually undesirable, possibly including for troff. Outside of theoretical computer science and language design, Turing completeness is not a terribly interesting property virtually of the time, despite being catchy.

  • Yes of course, it is not a very useful thing by itself but it is still interesting - e.g. even the mov instruction is Turing complete. – theindigamer Nov 20 '18 at 4:38
  • 4
    @theindigamer - x86's mov instruction is Turing-complete. (Because of addressing modes that let you use lookup tables, and the same mnemonic is used for load, store, and mov-immediate to register.) On many other ISAs that have a mov instruction (e.g. ARM) it's just a reg-reg move and isn't turing-complete. (Although on ARM it can do shifts/rotates.) Also, you actually need a jmp to create a loop around your block of mov instructions, unless you're in 16-bit mode where the instruction pointer can wrap around in a 64k code segment to loop implicitly. – Peter Cordes Nov 20 '18 at 8:10
  • 6
    @SpaceBison Of course there is :-) github.com/Battelle/movfuscator – Daniel Näslund Nov 20 '18 at 13:04
  • 2
    @PeterCordes: Ah; in the old days there ware MOV architectures that had memory mapped ALUs and IP was just another register so JMP was another MOV. – Joshua Nov 20 '18 at 17:07
  • 1
    @Joshua: fun fact: 32-bit ARM does expose PC as one of the 16 general-purpose integer registers. push {r4, lr} / pop {r4,pc} is common in functions that need to save/restore one call-preserved register and keep the stack aligned: they also save the link reg and pop it back into the program counter to return. (32-bit ARM's store/load-multiple instructions use a bitfield to indicate which registers to store/load.) And yeah, you can use PC as the destination of a mov or any instruction. I didn't know that was common in the past, though. But I had heard of transport-triggered ISAs. – Peter Cordes Nov 20 '18 at 17:18

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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