2

我知道 C++ 是不可判定的。但它是递归可枚举的吗?

让我们将一组有效的 C++ 程序定义为当前 C++ 标准下任何定义良好的程序。

是否有可能构建一个总能在有限时间内识别有效 C++ 程序的编译器?

还是它是递归可枚举的?

是否有可能构建一个总能在有限时间内识别无效C++ 程序的编译器?

或者两者都不是?

4

1 回答 1

2

是否有可能构建一个总能在有限时间内识别有效 C++ 程序的编译器?

是的。如果有足够的时间和资源,C++ 编译器应该能够完成任何有效的 C++ 程序的编译。递归可枚举语言需要一个图灵机,当字符串在语言中时,它总是终止并提供肯定的答案,而编译器基本上就是这样做的。

是否有可能构建一个总能在有限时间内识别无效 C++ 程序的编译器?

不,C++ 模板语言是图灵完备的,所以你可以在其中编写无限递归。由于停机问题,无法确定程序是否会完成编译,因此无法确定 C++ 程序是否会成功编译。

我曾经在 C++ 模板中写了一个无限递归,并尝试用 gcc 编译。事实证明,gcc 有一个可配置的递归深度限制。

于 2014-03-15T05:38:29.483 回答