基于constexpr的计算图灵完成？
我们知道C ++模板元编程是图灵完备的 ，但是预处理元编程不是 。
C ++ 11为我们提供了一种新的元编程forms：计算constexpr函数。 这种计算forms是否是图灵完成的？ 我在想，因为recursion和条件运算符（？:)在constexpr函数中是允许的，但是我希望有更多专业知识的人来确认。
tl; dr：C ++ 11中的constexpr由于语言规范中的错误而不是图灵完成的，但是该错误已经在标准的后续草稿中得到解决，并且clang已经实现了该修复。
如ISO C ++ 11国际标准所规定的， constexpr不是图灵完备的。 素描certificate：
- 每一个
constexpr函数f的结果（或非终止）在一个特定的参数序列，a...，只能由一个值的决定a... - 可以在常量expression式中构造的每个参数值必须是一个文字types，由
[basic.types]p10可以是：- 一个标量types，
- 一个参考，
- 一个字面types的数组，或者
- 一个类的types
- 上述每种情况都有一组有限的值。
- 对于一个标量的非指针types来说，这是非常平常的。
- 对于在常量expression式中使用的指针或引用，必须通过地址或引用常量expression式进行初始化，所以必须引用具有静态存储持续时间的对象，其中在任何程序中只有有限的数量。
- 对于一个数组来说，bound必须是一个常量，并且每个成员都必须用一个常量expression式进行初始化，结果如下。
- 对于一个类types来说，成员数量是有限的，每个成员必须是字面types，并用一个常量expression式进行初始化，结果如下。
- 因此，
f可以接收的a...组可能的input是有限的，所以任何有限状态的constexpr系统都是一个有限状态机，因此不是图灵完备的。
但是，自从C ++ 11标准发布以来，情况就发生了变化。
Johannes Schaub对std :: max（）和std :: min（）不是constexpr的回答中描述的问题作为核心问题1454被报告给C ++标准化委员会。在2012年2月的WG21会议上，我们认定这是一个缺陷标准和选定的解决scheme包括能够使用指定临时对象的指针或引用成员来创build类types的值。 这允许一个无限量的信息被一个constexpr函数累加和处理，并且足以进行constexpr评估。图灵完成（假设这个实现支持recursion到一个无限深度）。
为了演示实现1454核心问题的解决scheme的编译器的constexpr的图灵完备性，我为叮当testing套件写了一个图灵机模拟器：
http://llvm.org/svn/llvm-project/cfe/trunk/test/SemaCXX/constexpr-turing.cpp
g ++和clang的中继版本实现了这个核心问题的解决scheme，但是g ++的实现目前无法处理这个代码。
看看这些。 我编译了这些例子，他们在GCC 4.6中工作： 编译时计算 ， 编译时 parsingstring – 第一部分 ， 编译时parsingstring – 第二部分
如果考虑到实际计算机的限制 – 比如有限内存和MAX_INT的有限值，那么当然，constexpr（以及整个C ++）不是图灵完备的。
但是，如果我们将删除这个限制 – 例如，如果我们将int看作一个完全任意的正整数 – 那么是的，C ++的constexpr部分将是Turing完成的。 很容易expression任何部分recursion函数。
0，S（n）= n + 1，select符I_n ^ m（x_1，…，x_n）= x_m，明显的叠加可以用constexpr表示。
原始recursion可以直接完成：
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)); }
对于部分recursion，我们需要一个简单的技巧：
constexpr int h(int x1, ... int xn, int y = 0) { return (f(x1, ... xn, y) == 0) ? y : h(x1, ..., xn, y+1); }
所以我们得到任何部分recursion函数作为constexpr。
