我们知道C++ template metaprogramming is Turing complete，但是preprocessor metaprogramming is not。基于constexpr的计算图灵完整？
C++ 11为我们提供了一种新的元编程形式：计算constexpr函数。这种计算形式是否完成图灵？我在想，因为递归和条件运算符（？:)在constexpr函数中是允许的，但是我希望有更多专业知识的人来确认。
tl; dr：constexpr由于语言规范中存在缺陷，C++ 11中的图灵并不完整，但该错误已在标准的后续草稿中得到解决，并且clang已经实现了该修复。按照ISO C++ 11国际标准的规定，
constexpr不是图灵完备的。草图证明：
constexpr功能f的结果（或非终止）上的参数，a...的特定顺序，仅受a...[basic.types]p10是任一的：
f接收该组可能的输入a...是有限的，因此，任何有限描述constexpr系统是一个有限状态机，并因此不是图灵完整。但是，自从C++ 11标准发布以来，情况发生了变化。
Johannes Schaub对std::max() and std::min() not constexpr的回答中描述的问题已作为核心问题1454向C++标准化委员会报告。在2012年2月的WG21会议上，我们确定这是标准中的缺陷，并且所选分辨率包括能力使用指定临时对象的指针或引用成员创建类类型的值。这允许无限量的信息被constexpr函数累积和处理，并且足以使constexpr评估图灵完成（假设该实现支持递归到无限深度）。
为了证明constexpr图灵完备性为实现核心问题1454的建议的决议编译器，我写了图灵机模拟器铛的测试套件：
http://llvm.org/svn/llvm-project/cfe/trunk/test/SemaCXX/constexpr-turing.cpp
干线版本g ++和clang都实现了这个核心问题的解决方案，但是g ++的实现目前无法处理这些代码。
看看这些。我编的例子，他们在GCC 4.6工作： Compile-time computations，Parsing strings at compile-time - Part I，Parsing strings at compile-time - Part II
如果我们在现实的计算机帐户的限制 - 如有限内存和MAX_INT的有限值 - 然后，当然，constexpr（也整个C++）不是图灵完整的。但是如果我们将删除这个限制 - 例如，如果我们将int看作一个完全任意的正整数 - 那么是的，C++的constexpr部分将是Turing完整的。很容易表达任何部分递归函数。 （n）= n + 1和选择器I_n^m（x_1，...，x_n）= x_m，明显的叠加可以用constexpr表示。
原始递归可以做它笔直的路：
constexpr int h(int x1, ..., int xn, int y) {
return (xn == 0) ? f(x1, ..., xn) : g(x1, ..., xn, y-1, h(x1, ..., xn, y-1));
}
而对于部分递归我们需要一个简单的一招：
constexpr int h(int x1, ... int xn, int y = 0) {
return (f(x1, ... xn, y) == 0) ? y : h(x1, ..., xn, y+1);
}
所以我们得到任何部分递归函数为constexpr。
有趣！如果我的理解正确，这个区别取决于一个事实，即一个程序只能有有限数量的静态存储持续时间的对象，但它可能有无限数量的临时对象。你能解释为什么吗？ – HighCommander4 2012-03-02 08:34:05
@ HighCommander4静态存储持续时间的每个对象由源代码中的声明引入（其中只有有限数量，并且每个对象只引入有限数量的可单独寻址的对象），而无界递归可引入无限数量的临时工。这个观点仅适用于C++抽象机器 - 每一个真正的实现最终都会遇到某种形式的资源限制，所以仍然有一些有限的（但通常是未知的）限制。 – 2012-03-05 07:57:08
非常抽象:-) – 2013-09-28 23:22:02