特洛夫圖靈完備嗎?
Troff 支持宏定義 using
.de
和分支 using.if
(請參閱Troff 使用者手冊的第 5 頁和第 6 頁)。在這兩方面,它很像 TeX。但是,我不知道用Troff 編寫的高度複雜的程序(不像TikZ for TeX)。特洛夫圖靈完備嗎?
ESR 的The Art of Unix Programming聲稱它是:
我們將在第 18 章更詳細地研究 troff。就目前而言,足以說明它是命令式微型語言的一個很好的例子,它接近於成為一個成熟的解釋器(它有條件和遞歸,但沒有循環;它意外地是圖靈完備的)。
(“意外”而不是
m4
,據說是“故意圖靈完備”。)
是的,troff 是圖靈完備的。它支持任意遞歸和條件分支,這就足夠了。它還具有寄存器和其他各種儲存數據的方式,這為您提供了另一條路徑。
圖靈完備並不意味著高度複雜的程序是實用的——只是它們在理論上是可能的,不知何故,在某種程度的移除——也不意味著它們不是,所以 troff 既不是圖靈完備的,也不是圖靈完備的。沒有復雜的程序並沒有就此提出任何建議。
通常,圖靈完整性並不是對使用者有用的屬性。這意味著您可以用它來模擬圖靈機,而不是您想要的,也不是您從中獲得的輸出與您期望閱讀的一樣。輸入或輸出可能只是一個數字,甚至是某個東西出現的次數,而不是有用的東西,而且你最終模擬的機器類型和它們的程序通常一開始就很難理解。
許多語言和系統偶然是圖靈完備的,但不適用於該子集中的任何實際程式(例如,康威的生命遊戲或 CSS),並且某些對實際程式有用的語言不是圖靈完備的(例如,阿格達)。真正的定義特徵是你可以
- 永遠繼續下去
- 記住盡可能多的數據
- 選擇下一步做什麼(如果有的話)
通常這些屬性 - 特別是非終止 - 實際上是不可取的,可能包括 troff。在理論電腦科學和語言設計之外,圖靈完備性實際上在當時並不是一個非常有趣的屬性,儘管它很吸引人。