图灵完备语言可以有CFG吗



图灵完备性是否排除了一种语言具有CFG?我找不到任何报纸这样说。

我发现:"TeX只能由一个完整的图灵机解析(对可用的有限空间进行模运算(,这就排除了它具有BNF。">

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

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

对于一个计算系统,如果需要在该系统中计算该系统的所有能力,则计算是完整;也就是说,对计算系统的任何改变导致其不能执行至少与以前相同的计算将导致其不能进行该计算。计算是图灵完备,如果它是关于图灵机完备的。

BNF语法描述上下文无关的语言,而能够解析这些语言的能力最低的计算系统是下推自动机。该计算系统不能模拟图灵机,因为图灵机可以执行下推自动机无法执行的计算;因此,下推自动机不是图灵等价的

文章说,TeX是一种图灵全语言,也就是说,决定有效TeX字符串的语言需要图灵机的所有能力。任何不能模拟图灵机的系统都不可能用有效的TeX字符串的语言解析决定成员身份。

这篇文章并不是说TeX是图灵等价物(也许是,也许不是;我不知道(。正如评论中所指出的,计算系统表示的图灵完备性与该计算系统的图灵等价性完全无关。即使是图灵机本身也可以用正则语言的字符串来表示(事实上,扩展对任何语言的解释,使无效的程序编译到不做任何事情就停止的程序,突然间所有字符串都是有效的,所有字符串的语言当然是正则的(。

最新更新