c++ - 基于 constexpr 的计算图灵是否完整？

Question

我们知道 C++ template metaprogramming is Turing complete , 但是 preprocessor metaprogramming is not .

C++11 为我们提供了一种新的元编程形式:constexpr 函数的计算。这种计算形式是图灵完备的吗？我在想，由于 constexpr 函数中允许使用递归和条件运算符 (?:)，所以会这样，但我希望有更多专业知识的人来确认。

Answer 1

tl;dr:C++11 中的 constexpr 不是图灵完备的，因为语言规范中存在错误，但该错误已在标准的后续草案中得到解决，并且 clang 已经实现了修复。

constexpr，如 ISO C++11 国际标准中所指定，不是图灵完备的。草图证明:

• 每个 constexpr 函数 f 在特定参数序列 a... 上的结果(或非终止)是仅由 a...
的值确定
• 可以在常量表达式中构造的每个参数值都必须是文字类型，根据 [basic.types]p10 可以是:
  • 标量类型，
  • 引用，
  • 文字类型的数组，或
  • 类类型
• 上述每种情况都有一组有限的值。
  • 对于标量、非指针类型，这很简单。
  • 在常量表达式中使用的指针或引用，必须由地址或引用常量表达式初始化，因此必须引用具有静态存储时长的对象，在任何程序中该对象的数量都是有限的.
  • 对于数组，bound 必须是一个常量，并且每个成员都必须由一个常量表达式来初始化，结果随之而来。
  • 对于一个类类型，成员的数量是有限的，并且每个成员都必须是字面量类型并由一个常量表达式进行初始化，结果随之而来。
• 因此，f 可以接收的可能输入 a... 的集合是有限的，因此任何有限描述的 constexpr 系统都是有限状态机，因此不是图灵完备的。

但是，自从 C++11 标准发布后，情况发生了变化。

Johannes Schaub 对 std::max() and std::min() not constexpr 的回答中描述的问题已作为核心问题 1454 报告给 C++ 标准化委员会。在 2012 年 2 月的 WG21 session 上，我们认为这是标准中的一个缺陷，并且选择的解决方案包括使用指定的指针或引用成员创建类类型值的能力临时工。这允许 constexpr 函数累积和处理无限量的信息，并且足以使 constexpr 评估图灵完备(假设实现支持递归到无限深度)。

为了演示 constexpr 的图灵完备性，用于实现核心问题 1454 的建议解决方案的编译器，我为 clang 的测试套件编写了一个图灵机模拟器:

http://llvm.org/svn/llvm-project/cfe/trunk/test/SemaCXX/constexpr-turing.cpp

g++和clang的trunk版本都实现了这个核心问题的解决，但是g++的实现目前无法处理这个代码。