Is Troff Turing complete?
up vote
8
down vote
favorite
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
asked Nov 20 at 4:25
theindigamer
2161312
add a comment |
up vote
8
down vote
favorite
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
asked Nov 20 at 4:25
theindigamer
2161312
add a comment |
up vote
8
down vote
favorite
up vote
8
down vote
favorite
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
asked Nov 20 at 4:25
theindigamer
2161312
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
roff
asked Nov 20 at 4:25
theindigamer
2161312
asked Nov 20 at 4:25
theindigamer
2161312
asked Nov 20 at 4:25
theindigamer
2161312
asked Nov 20 at 4:25
theindigamer
2161312
asked Nov 20 at 4:25
theindigamer
2161312
2161312
add a comment |
add a comment |
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".)
answered Nov 20 at 4:29
muru
35.2k582155
add a comment |
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.
answered Nov 20 at 4:35
Michael Homer
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'smovinstruction 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 amovinstruction (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 ajmpto create a loop around your block ofmovinstructions, 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
6
@SpaceBison Of course there is :-) github.com/Battelle/movfuscator
– Daniel Näslund
Nov 20 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 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 amovor 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 at 17:18
|
show 1 more comment
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".)
answered Nov 20 at 4:29
muru
35.2k582155
add a comment |
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".)
answered Nov 20 at 4:29
muru
35.2k582155
add a comment |
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".)
answered Nov 20 at 4:29
muru
35.2k582155
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".)
answered Nov 20 at 4:29
muru
35.2k582155
edited Nov 20 at 4:35
answered Nov 20 at 4:29
muru
35.2k582155
answered Nov 20 at 4:29
muru
35.2k582155
answered Nov 20 at 4:29
muru
35.2k582155
35.2k582155
add a comment |
add a comment |
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.
answered Nov 20 at 4:35
Michael Homer
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'smovinstruction 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 amovinstruction (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 ajmpto create a loop around your block ofmovinstructions, 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
6
@SpaceBison Of course there is :-) github.com/Battelle/movfuscator
– Daniel Näslund
Nov 20 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 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 amovor 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 at 17:18
|
show 1 more comment
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.
answered Nov 20 at 4:35
Michael Homer
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'smovinstruction 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 amovinstruction (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 ajmpto create a loop around your block ofmovinstructions, 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
6
@SpaceBison Of course there is :-) github.com/Battelle/movfuscator
– Daniel Näslund
Nov 20 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 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 amovor 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 at 17:18
|
show 1 more comment
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.
answered Nov 20 at 4:35
Michael Homer
44.8k7117156
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.
answered Nov 20 at 4:35
Michael Homer
44.8k7117156
edited Nov 20 at 5:13
answered Nov 20 at 4:35
Michael Homer
44.8k7117156
answered Nov 20 at 4:35
Michael Homer
44.8k7117156
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'smovinstruction 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 amovinstruction (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 ajmpto create a loop around your block ofmovinstructions, 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
6
@SpaceBison Of course there is :-) github.com/Battelle/movfuscator
– Daniel Näslund
Nov 20 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 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 amovor 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 at 17:18
|
show 1 more comment
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'smovinstruction 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 amovinstruction (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 ajmpto create a loop around your block ofmovinstructions, 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
6
@SpaceBison Of course there is :-) github.com/Battelle/movfuscator
– Daniel Näslund
Nov 20 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 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 amovor 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 at 17:18
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
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
2
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 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
1
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 at 17:18
@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 at 17:18
|
show 1 more comment
Thanks for contributing an answer to Unix & Linux Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
