Is Troff Turing complete?











up vote
8
down vote

favorite
1












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?










share|improve this question


























    up vote
    8
    down vote

    favorite
    1












    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?










    share|improve this question
























      up vote
      8
      down vote

      favorite
      1









      up vote
      8
      down vote

      favorite
      1






      1





      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?










      share|improve this question













      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?







      roff






      share|improve this question













      share|improve this question











      share|improve this question




      share|improve this question










      asked Nov 20 at 4:25









      theindigamer

      2161312




      2161312






















          2 Answers
          2






          active

          oldest

          votes

















          up vote
          12
          down vote



          accepted










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






          share|improve this answer






























            up vote
            12
            down vote













            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.






            share|improve this answer























            • 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 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 at 8:10












            • Is there by any chance a C compiler that produces only movs?
              – SpaceBison
              Nov 20 at 12:07






            • 6




              @SpaceBison Of course there is :-) github.com/Battelle/movfuscator
              – Daniel Näslund
              Nov 20 at 13:04






            • 1




              @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 at 17:07











            Your Answer








            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "106"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            convertImagesToLinks: false,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














             

            draft saved


            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2funix.stackexchange.com%2fquestions%2f482881%2fis-troff-turing-complete%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            2 Answers
            2






            active

            oldest

            votes








            2 Answers
            2






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes








            up vote
            12
            down vote



            accepted










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






            share|improve this answer



























              up vote
              12
              down vote



              accepted










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






              share|improve this answer

























                up vote
                12
                down vote



                accepted







                up vote
                12
                down vote



                accepted






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






                share|improve this answer














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







                share|improve this answer














                share|improve this answer



                share|improve this answer








                edited Nov 20 at 4:35

























                answered Nov 20 at 4:29









                muru

                35.1k581154




                35.1k581154
























                    up vote
                    12
                    down vote













                    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.






                    share|improve this answer























                    • 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 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 at 8:10












                    • Is there by any chance a C compiler that produces only movs?
                      – SpaceBison
                      Nov 20 at 12:07






                    • 6




                      @SpaceBison Of course there is :-) github.com/Battelle/movfuscator
                      – Daniel Näslund
                      Nov 20 at 13:04






                    • 1




                      @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 at 17:07















                    up vote
                    12
                    down vote













                    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.






                    share|improve this answer























                    • 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 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 at 8:10












                    • Is there by any chance a C compiler that produces only movs?
                      – SpaceBison
                      Nov 20 at 12:07






                    • 6




                      @SpaceBison Of course there is :-) github.com/Battelle/movfuscator
                      – Daniel Näslund
                      Nov 20 at 13:04






                    • 1




                      @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 at 17:07













                    up vote
                    12
                    down vote










                    up vote
                    12
                    down vote









                    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.






                    share|improve this answer














                    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.







                    share|improve this answer














                    share|improve this answer



                    share|improve this answer








                    edited Nov 20 at 5:13

























                    answered Nov 20 at 4:35









                    Michael Homer

                    44.8k7117156




                    44.8k7117156












                    • 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 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 at 8:10












                    • Is there by any chance a C compiler that produces only movs?
                      – SpaceBison
                      Nov 20 at 12:07






                    • 6




                      @SpaceBison Of course there is :-) github.com/Battelle/movfuscator
                      – Daniel Näslund
                      Nov 20 at 13:04






                    • 1




                      @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 at 17:07


















                    • 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 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 at 8:10












                    • Is there by any chance a C compiler that produces only movs?
                      – SpaceBison
                      Nov 20 at 12:07






                    • 6




                      @SpaceBison Of course there is :-) github.com/Battelle/movfuscator
                      – Daniel Näslund
                      Nov 20 at 13:04






                    • 1




                      @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 at 17:07
















                    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 at 4:38




                    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 at 4:38




                    4




                    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 at 8:10






                    @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 at 8:10














                    Is there by any chance a C compiler that produces only movs?
                    – SpaceBison
                    Nov 20 at 12:07




                    Is there by any chance a C compiler that produces only movs?
                    – SpaceBison
                    Nov 20 at 12:07




                    6




                    6




                    @SpaceBison Of course there is :-) github.com/Battelle/movfuscator
                    – Daniel Näslund
                    Nov 20 at 13:04




                    @SpaceBison Of course there is :-) github.com/Battelle/movfuscator
                    – Daniel Näslund
                    Nov 20 at 13:04




                    1




                    1




                    @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 at 17:07




                    @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 at 17:07


















                     

                    draft saved


                    draft discarded



















































                     


                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2funix.stackexchange.com%2fquestions%2f482881%2fis-troff-turing-complete%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    Plaza Victoria

                    Puebla de Zaragoza

                    Musa