我知道 C++ 是不可判定的。但它是递归可枚举的吗？
让我们将有效的 C++ 程序集定义为当前 C++ 标准下任何定义良好的程序。
是否有可能构建一个始终能够在有限时间内识别有效 C++ 程序的编译器？
或者它是可共同递归枚举的吗？
是否有可能构建一个始终能够在有限时间内识别无效 C++ 程序的编译器？
或者两者都不是？
最佳答案
是否可以构建一个始终能够在有限时间内识别有效 C++ 程序的编译器？
是的。如果有足够的时间和资源，C++ 编译器应该能够完成编译任何有效的 C++ 程序。递归可枚举语言需要一个图灵机，当字符串位于该语言中时，它总是终止并提供肯定的答案，而编译器本质上就是这样做的。
是否有可能构建一个始终能够在有限时间内识别无效 C++ 程序的编译器？
没有。 C++ 模板语言是图灵完备的，因此您可以在其中编写无限递归。由于停机问题，无法确定程序是否会完成编译，因此无法确定C++程序是否会成功编译。
我曾经在C++模板中写过一个无限递归，并尝试用gcc编译。事实证明，gcc 有一个可配置的递归深度限制。
关于c++ - C++是递归可枚举语言吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22419853/