代码之家 › 专栏 › 技术社区 › rcreswick

构建规范语言表示的一般复杂性是什么?

canonical-form language-theory dsl

0

rcreswick · 技术社区 · 17 年前

一方面,创建语言的规范表示与许多硬图问题(例如:图同构)具有相当的复杂性似乎是合理的,但另一方面,iirc、编译器(如gcc、yhc和ghc)使用中间表示生成各种格式(汇编、javascript等)的输出,因此,这至少在某种形式上是一个已解决的问题。

编辑: 例如,一个 Regular Language (例如:正则表达式的“纯”形式)不能表达与 Turing-complete language 然而 ,如果将图灵完备语言转换为规范形式是P-空间完备的,或者是NP-完备的,那么您不应该浪费时间尝试构建规范形式——或者找到另一种方法,或者将语言复杂性降低到在多项式时间内被标准化。

2 回复 | 直到 17 年前

1

Jouni K. Seppänen 17 年前

所谓“规范表示法”,我想你的意思是:调用程序 P Q 相等的 P 这是一个程序 P' 属于相同的等价类,并且您需要相同等价类的所有成员具有相同的规范表示。

对于图灵完备语言,图灵可计算规范表示将使您能够解决 Halting Problem 如下所示:首先编写一个由无限循环组成的程序,并找到它的规范表示 Q . 然后对于任何输入程序 P ,首先将其机械地转换为程序 ₀ 除了不产生输出,然后找到规范表示之外,它做了同样的事情 P ₀ Q P ₀ . 否则 P ₀ P .

要想获得更多乐趣,请阅读以下内容 Gregory Chaitin's 致力于他所谓的“优雅”计划。

2

0

Paul Nathan 17 年前