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

Question

使用语言的规范表示通常很方便（在我的情况下，它们通常是特定于域的语言）;但是，我认为对所涉及的语言的表达有严格的限制，这决定了是否可以为该语言中的任意程序确定和/或创建规范形式。不幸的是，我一直无法找到我（模糊地）回忆起这方面的参考文献。

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

何时可以确定/生成给定语言的规范形式？ （该语言的表达能力如何，以及语言表达如何影响规范形式的效用？）如果可能，请提供参考或证据。

编辑：例如，常规语言（例如：'纯'形式的正则表达式）不能表达许多与图灵完整语言相同的内容可以。换句话说，您不能用常规语言编写Web服务器，但可以使用lambda演算。我的问题是关于理论上的可能性，并且确实有一个与复杂性理论有关的具体答案。如果我有一个需要传输到另一个系统的DSL，那么在传输之前生成该规范的规范形式通常是有益的，因为这将解耦两个不同系统使用的独立表示。 然而，如果是P-Space完成，或NP-Complete将图灵完备语言翻译成规范形式，那么你不应该浪费时间尝试构建规范形式 - 要么找到另一种方法，或者将语言复杂性降低到可以在多项式时间内规范化的东西。

Answer 1

通过“规范表示”我假设您的意思如下：如果他们“做同样的事情”，则调用程序 P 和 Q 等效在相同的输入上。 “做同样的事情”表示程序具有相同的输出，并且两个程序在有限时间后停止或两者都进入无限循环。这种等价关系定义了所有程序集中的等价类。 “规范表示”是指“规范表示”。程序 P 是属于同一等价类的程序 P'，并且您要求同一等价类的所有成员具有相同的规范表示。

对于图灵完备语言，图灵可计算的规范表示将使您能够解决停止问题如下：首先编写一个由无限循环组成的程序，并找到它的规范表示 Q 。然后对于任何输入程序 P ，首先将其机械地转换为程序 P ₀ ，它执行相同的操作，除了它不产生输出，并且然后找到该程序的规范表示 P ₀ '。如果结果是 Q ，则您知道 P ₀ 不会停止，因此 P 也不会停止。否则， P ₀ 停止， P 也停止。

为了获得更多乐趣，请阅读 Gregory Chaitin 关于他所谓的“工作”的一些内容。优雅＆QUOT;程序

Answer 2

在我看来，编译成汇编语言可以归类为以实际方式翻译成规范形式。