我知道C++是不可判定的。但它是否是递归枚举的?
让我们将有效的C++程序定义为当前C++标准下的任何定义良好的程序。
是否有可能构造一个能够在有限时间内始终识别有效C++程序的编译器?
或者是共递归枚举?
是否有可能构造一个能够在有限时间内始终识别无效C++程序的编译器?
还是两者都没有?
发布于 2014-03-15 05:38:29
是否有可能构造一个能够在有限时间内始终识别有效C++程序的编译器?
是。如果有足够的时间和资源,C++编译器应该能够完成任何有效的C++程序的编译。递归枚举语言需要一台图灵机,当字符串在语言中使用时,图灵机总是终止并提供一个肯定的答案,而编译器基本上就是这样做的。
是否有可能构造一个能够在有限时间内始终识别无效C++程序的编译器?
不是的。C++模板语言是图灵完整的,因此您可以在其中编写无限的递归。由于中断问题,无法确定程序是否会完成编译,因此无法确定C++程序是否能够成功编译。
有一次,我用C++模板编写了无限递归,并试图与gcc一起编译。结果表明gcc有一个可配置的递归深度极限。
https://stackoverflow.com/questions/22419853
复制相似问题