Ist Troff Turing fertig?

9

Troff unterstützt sowohl Makrodefinitionen .deals auch Verzweigungen mit .if(siehe Seiten 5 und 6 des Troff-Benutzerhandbuchs ). In dieser Hinsicht ist es TeX sehr ähnlich. Ich kenne jedoch keine hochkomplexen Programme, die in Troff geschrieben wurden (im Gegensatz zu TikZ für TeX). Ist Troff Turing fertig?

Cutculus
quelle

Antworten:

12

ESRs The Art of Unix Programming behauptet, es sei:

Wir werden troff in Kapitel 18 genauer untersuchen. Im Moment genügt es zu bemerken, dass es ein gutes Beispiel für eine zwingende Minisprache ist, die an die Vollständigkeit eines vollwertigen Dolmetschers grenzt (es hat Bedingungen und Rekursionen, aber keine Schleifen; es ist versehentlich Turing-vollständig).

("Versehentlich" im Gegensatz m4zu "absichtlich Turing-vollständig".)

muru
quelle
13

Ja, troff ist Turing-komplett. Es unterstützt eine beliebige Rekursion und bedingte Verzweigung, was ausreichend ist. Es hat auch Register und verschiedene andere Möglichkeiten zum Speichern von Daten, wodurch Sie wieder einen anderen Pfad erhalten.

Die Vollständigkeit von Turing bedeutet nicht, dass hochkomplexe Programme praktisch sind - nur, dass sie auf einer bestimmten Ebene theoretisch irgendwie möglich sind - und ihre Abwesenheit bedeutet auch nicht, dass dies nicht der Fall ist. Weder ist Troff Turing-vollständig noch das Das Fehlen komplexer Programme lässt auf die eine oder andere Weise nicht viel zu.


Die Vollständigkeit ist im Allgemeinen keine Eigenschaft, die für Sie als Benutzer etwas Nützliches bedeutet. Es bedeutet, dass man kann mit ihm eine Turing - Maschine simulieren, nicht , dass Sie wollen würde, und nicht , dass die Ausgabe , dass Sie von ihm bekommen würde , ist etwas wie das, was Sie zu lesen erwarten würde. Die Eingabe oder Ausgabe kann nur eine Zahl sein oder sogar die Häufigkeit, mit der etwas erscheint, und nicht etwas Nützliches. Die Art der Maschine, die Sie am Ende simulieren, und ihre Programme sind anfangs oft kaum nachvollziehbar.

Viele Sprachen und Systeme sind im Übrigen Turing-vollständig, aber für eine tatsächliche Programmierung in dieser Teilmenge (z. B. Conways Game of Life oder CSS) nicht angemessen anwendbar, und einige Sprachen, die für die echte Programmierung nützlich sind , sind nicht Turing-vollständig (z. Agda). Die bestimmenden Merkmale sind wirklich, dass Sie können

  • mach weiter für immer
  • Speichern Sie so viele Daten, wie Sie möchten
  • Wählen Sie, was Sie als Nächstes tun möchten

Oft sind diese Eigenschaften - insbesondere die Nichtbeendigung - tatsächlich unerwünscht, möglicherweise auch für troff. Außerhalb der theoretischen Informatik und des Sprachdesigns ist die Vollständigkeit von Turing praktisch keine besonders interessante Eigenschaft, obwohl sie eingängig ist.

Michael Homer
quelle
Ja natürlich, es ist an sich keine sehr nützliche Sache, aber es ist immer noch interessant - zB ist sogar die Mov-Anweisung vollständig.
Cutculus
4
@theindigamer - Die Anweisung von x86mov ist Turing-complete. (Aufgrund der Adressierungsmodi, mit denen Sie Nachschlagetabellen verwenden können, wird dieselbe Mnemonik zum Laden, Speichern und sofortigen Registrieren verwendet.) Bei vielen anderen ISAs mit einer movAnweisung (z. B. ARM) handelt es sich nur um eine Reg-Reg-Verschiebung und ist nicht vollständig. (Obwohl es in ARM Verschiebungen / Drehungen ausführen kann .) Außerdem benötigen Sie eine jmp, um eine Schleife um Ihren movAnweisungsblock zu erstellen , es sei denn, Sie befinden sich im 16-Bit-Modus, in dem der Anweisungszeiger in einem 64-KByte-Codesegment umlaufen kann Schleife implizit.
Peter Cordes
6
@ SpaceBison Natürlich gibt es :-) github.com/Battelle/movfuscator
Daniel Näslund
2
@ PeterCordes: Ah; In den alten Tagen gab es MOV-Architekturen mit speicherabgebildeten ALUs und IP war nur ein weiteres Register, also war JMP ein weiterer MOV.
Joshua
1
@Joshua: lustige Tatsache: 32-Bit-ARM macht PC als eines der 16 universellen Ganzzahlregister verfügbar. push {r4, lr}/ pop {r4,pc}ist in Funktionen üblich, die ein aufruferhaltenes Register speichern / wiederherstellen und den Stapel ausgerichtet halten müssen: Sie speichern auch das Linkregister und legen es zur Rückkehr in den Programmzähler zurück. (Die 32-Bit-ARM-Anweisungen zum Speichern / Laden mehrerer verwenden ein Bitfeld, um anzugeben, welche Register gespeichert / geladen werden sollen.) Und ja, Sie können den PC als Ziel für einen movoder einen beliebigen Befehl verwenden. Ich wusste jedoch nicht, dass dies in der Vergangenheit üblich war. Aber ich hatte von transportgetriggerten ISAs gehört.
Peter Cordes