特洛夫图灵完整了吗?

特洛夫图灵完整了吗?

Troff 支持宏定义 using.de和分支 using .if(参见第 5 页和第 6 页)特罗夫用户手册)。在这两个方面,它与 TeX 非常相似。然而,我不知道用 Troff 编写的高度复杂的程序(不像 TeX 的 TikZ)。特洛夫图灵完整了吗?

答案1

是的,troff 是图灵完备的。它支持任意递归和条件分支,这就足够了。它还具有寄存器和各种其他方式来存储数据,这为您提供了另一条路径。

图灵完备性并不意味着高度复杂的程序是实际的- 只是它们在理论上是可能的,不知何故,在某种程度的删除 - 而且它的缺失也不意味着它们不是,所以 troff 不是图灵完备的,也不是复杂程序的缺失并不能以一种方式暗示任何事情或其他相关内容。


一般来说,图灵完备性并不是一个对你(用户)有任何用处的属性。这一切都意味着你用它模拟图灵机,这不是您想要的,也不是您从它得到的输出与您期望阅读的内容一样。输入或输出可能只是一个数字,甚至是某个东西出现的次数,而不是有用的东西,而你最终模拟的机器类型及其程序通常一开始就很难理解。

许多语言和系统都是图灵完备的,但不适用于该子集中的任何实际编程(例如,康威的生命游戏或 CSS),并且某些语言对于真正的编程有用的不是图灵完备的(例如,Agda)。决定性的特征确实是你可以

  • 永远继续下去
  • 记住尽可能多的数据
  • 选择下一步要做什么(如果有的话)

通常,这些属性(尤其是非终止性)实际上是不受欢迎的,可能包括 troff。除了理论计算机科学和语言设计之外,图灵完备性实际上在当时并不是一个非常有趣的属性,尽管它很吸引人。

答案2

ESR的Unix 编程的艺术声称它是:

我们将在第 18 章中更详细地研究 troff;现在,只要注意到它是命令式迷你语言的一个很好的例子就足够了,它几乎是一个成熟的解释器(它有条件和递归,但没有循环;它意外地是图灵完备的)。

(“意外”与 相对m4,据说“故意图灵完备”。)

相关内容