parsing - 图灵完备的语言可以有CFG吗?
解决方案
我们通常对这些术语不精确,但要正确回答您的问题,我们必须非常精确地使用术语。
如果两个计算系统能够相互模拟,则它们是等价的。如果一个计算系统等价于图灵机,那么它就是图灵等价的。
如果一个计算系统需要在该系统中计算该系统的所有功能,则该计算就该系统而言是完整的;也就是说,任何导致计算系统无法执行至少与以前相同的计算的更改都将导致它无法执行此计算。如果计算相对于图灵机是完整的,则计算是图灵完备的。
BNF 语法描述了上下文无关的语言,而能够解析此类语言的能力最差的计算系统是下推自动机。该计算系统无法模拟图灵机,因为图灵机可以执行下推自动机无法执行的计算;因此,下推自动机不是图灵等效的。
文章说 TeX 是图灵完备的语言,也就是说,决定有效的 TeX 字符串的语言需要图灵机的所有能力。任何无法模拟图灵机的系统都无法解析有效 TeX 字符串语言中的决定成员资格。
这篇文章并不是说 TeX 是图灵等效的(也许是,也许不是;我不知道)。正如评论中所指出的,计算系统表示的图灵完备性与该计算系统的图灵等效性完全无关。甚至图灵机本身也可以使用常规语言的字符串来表示(实际上,扩展任何语言的解释,以便原本无效的程序编译为不做任何事情而停止的程序,突然所有字符串都是有效的,并且所有的语言字符串当然是常规的)。
推荐阅读
- python - 用于处理字符串的 Pandas lambda 函数语法
- c# - C# tls1.3 异常:无法联系本地安全机构
- java - 使用参数初始化类字段的不同方法
- php - Laravel CSV 导入器未定义的偏移量:1
- javascript - 在同一个新标签 javascript 中打开多个 url,然后停止最后一个
- c++ - 可以获得 Gmutex 锁的线程所有者吗?
- javascript - 未捕获的 TypeError formiobuilder 不是函数。我做错什么了?
- c# - 如何以编程方式使用在 Window.Resources 中定义的 GroupStyle?
- html - 如何在反应中加载带有脚本标签的外部静态 HTML 页面?
- sql - 将行转换为列并计算总和