Troff Turing é completo?

Question

O Troff suporta as duas definições de macro usando .de e a ramificação usando .if (consulte as páginas 5 e 6 do manual do usuário do Troff ). Nestes dois aspectos, é muito parecido com o TeX. No entanto, eu não sei de programas altamente complexos escritos em Troff (ao contrário do TikZ para TeX). Troff Turing está completo?

    

Answer 1

A arte da programação Unix afirma que é:

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

("acidentalmente" ao contrário de m4 , que é dito ser "deliberadamente Turing-completo").

    

Answer 2

Sim, troff é Turing completo. Ele suporta recursão arbitrária e ramificação condicional, o que é suficiente. Ele também tem registros e várias outras maneiras de armazenar dados, o que lhe dá outro caminho novamente.

A completude de Turing não implica que programas altamente complexos sejam práticos - apenas que eles são teoricamente possíveis, de alguma forma, em algum nível de remoção - e nem a sua ausência implica que eles não são Assim, nem o troff está sendo Turing-completo nem a ausência de programas complexos não sugerem nada de uma maneira ou de outra sobre isso.

A integridade de Turing não é, geralmente, uma propriedade que significa algo útil para você, o usuário. Tudo o que isso significa é que você pode simular uma máquina de Turing com ela, não que você queira, e não que a saída que você obteria seja algo parecido com o que você esperaria ler. A entrada ou saída pode ser apenas um número, ou até mesmo o número de vezes que algo aparece, ao invés de algo útil, e os tipos de máquinas que você acaba simulando e seus programas são quase sempre compreensíveis para começar.

Muitas linguagens e sistemas são incidentalmente Turing-completos, mas não razoavelmente aplicáveis para qualquer programação real naquele subconjunto (por exemplo, o Game of Life ou CSS de Conway), e algumas linguagens que são úteis para reais programação não é Turing-completa (por exemplo, Agda). As características definidoras realmente são que você pode

• continue para sempre
• lembre-se da quantidade de dados que você deseja
• escolha o que fazer, se for o caso,

Muitas vezes essas propriedades - particularmente a não-terminação - são indesejáveis, possivelmente incluindo o troff. Fora da ciência da computação teórica e do design de linguagem, a completude de Turing não é uma propriedade muito interessante virtualmente na época, apesar de ser cativante.