c++ - C++ 是一种递归可枚举的语言吗？

Question

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

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

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

还是它是递归可枚举的？

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

或者两者都不是？

Answer 1

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

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

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

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

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