图灵完备语言可以有 CFG 吗？

Question

图灵完整性是否会妨碍语言拥有 CFG？我找不到任何论文这么说。

我发现： “TeX 只能由完整的图灵机解析（以可用的有限空间为模），这使其无法拥有 BNF。”

Answer 1

我们通常对这些术语不精确，但正确回答您的问题需要我们非常精确地使用术语。

如果两个计算系统可以互相模拟，那么它们是等效的。如果一个计算系统等效于图灵机，那么它就是图灵等效的。

如果计算需要在该系统中计算该系统的所有功能，则该计算对于该计算系统而言是完整的；也就是说，对计算系统的任何导致它不能执行至少与以前相同的计算的改变将导致它不能执行该计算。如果计算对于图灵机而言是完整的，则该计算是图灵完整的。

BNF 语法描述了上下文无关语言，而能够解析此类语言的能力最差的计算系统是下推自动机。该计算系统无法模拟图灵机，因为图灵机可以执行下推自动机无法执行的某些计算；因此，下推自动机并不等同于图灵。

文章称，TeX 是一种图灵完备的语言，即决定有效 TeX 字符串的语言需要图灵机的所有能力。任何不能模拟图灵机的系统都不可能解析有效 TeX 字符串语言中的决定成员资格。

这篇文章并没有说 TeX 与图灵等效（也许是，也许不是；我不知道）。正如评论中指出的，计算系统表示的图灵完备性与该计算系统的图灵等价性完全无关。甚至图灵机本身也可以使用常规语言的字符串来表示（事实上，扩展任何语言的解释，以便否则无效的程序编译成不执行任何操作就停止的程序，突然间所有字符串都是有效的，并且所有语言的语言字符串当然是规则的）。