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

Question

图灵完整性是否会阻止语言具有CFG？我找不到任何这样说的论文。

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

Answer 1

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

如果两个计算系统能够相互模拟，则它们是等价的。如果一个计算系统等价于图灵机，那么它就是图灵等价的。

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

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

文章说 TeX 是图灵完备的语言，也就是说，决定有效的 TeX 字符串的语言需要图灵机的所有能力。任何无法模拟图灵机的系统都无法解析有效 TeX 字符串语言中的决定成员资格。

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