使用constexpr进行计算是否具备图灵完备性？

Question

我们知道C++模板元编程是图灵完备的，但预处理器元编程不是。

C++11为我们提供了一种新形式的元编程：constexpr函数的计算。这种形式的计算是否具有图灵完备性？我认为由于constexpr函数中允许递归和条件运算符（?:），所以它应该是具备的，但我希望有更多专业知识的人来确认。

- HighCommander4

Answer 1

tl;dr: 在C++11中，由于语言规范中的一个bug，constexpr不是图灵完备的，但这个bug已在后续标准草案中得到修复，而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的回答中描述的问题被报告给C++标准化委员会作为核心问题1454。在2012年2月的WG21会议上，我们决定这是一个标准中的缺陷，并选择了解决方案，其中包括能够创建具有指针或引用成员的类类型值，这些值指向临时对象。这允许通过constexpr函数累积和处理无限数量的信息，并足以使constexpr评估具备图灵完备性（假设实现支持递归到无限深度）。

为了证明对于实现了核心问题1454提出的解决方案的编译器，constexpr的图灵完备性，我为clang的测试套件编写了一个图灵机模拟器。

https://github.com/llvm/llvm-project/blob/main/clang/test/SemaCXX/constexpr-turing.cpp

Clang 3.1和g++ 9及以上版本都在其C++11模式中实现了固定规则，并且可以处理该示例。

- Richard Smith

---

有趣！如果我理解正确，区别在于程序只能具有有限数量的静态存储期对象，但它可以具有潜在无限数量的临时对象。您能解释一下为什么吗？ - HighCommander4

每个具有静态存储期的对象都是通过源代码中的声明引入的（这些声明数量是有限的，每个声明只会引入有限数量的可寻址对象），而无限递归可能会引入无限数量的临时对象。这种观点仅适用于C++的抽象机器--每个真实的实现最终都会达到某种形式的资源限制，因此仍然具有一些有限（但通常是未知的）界限。 - Richard Smith

多么抽象啊 :-) - Kerrek SB

@RichardSmith：你不需要处理模板参数包吗？我的意思是，“函数f可以接收的可能输入集合'a...'”对我来说显然是无限的：有'f(1)'，'f(1,1)'，'f(1,1,1)'等等，一直到（可数）无穷大。我并不是说C++11 constexpr必定是图灵完备的，我只是想说，因为你从错误的前提出发，所以你没有真正得到相反的证明。（除非你缺少的前提是参数包的实现定义最大大小。） - Quuxplusone

@Quuxplusone 不，常量表达式求值不能触发模板实例化，因此模板在这里不相关。常量表达式求值仅对程序的非（值）依赖片段进行操作。（交错的模板实例化和常量表达式求值是图灵完备的，但这源于模板实例化本身就是图灵完备的。） - Richard Smith

Answer 2

请看这些例子。我编译了这些例子，它们适用于GCC 4.6： 编译时计算，在编译时解析字符串 - 第一部分，在编译时解析字符串 - 第二部分

- Andrzej

---

+1：哦我的天啊，现在我明白了GoingNative会议小组讨论中constexpr所带来的新疯狂/令人惊叹的可能性。O__O； - Klaim

字符串解析是翻译时计算变得美丽的地方。 - ex0du5

能够读取字符串字面量并不意味着它是图灵完备的（例如，它并未展示如何在无限（非半无限）纸带上进行编写）。 - kennytm

Answer 3

如果我们考虑实际计算机的限制 - 例如有限的内存和MAX_INT的有限值 - 那么，当然，constexpr（以及整个C ++）就不是图灵完备的。

但是如果我们去除这个限制 - 例如，如果我们将int视为完全任意的正整数 - 那么是的，C ++的constexpr部分将是图灵完备的。可以很容易地表示任何部分递归函数。

0，S（n）= n + 1和selectors I_n ^ m（x_1，...，x_n）= x_m和superposition显然可以使用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。

- mihaild

---

对于模拟数学整数的 int 类型，这个答案是正确的。然而，对于只有有限一组不同值的 int 类型，结果并不正确。 - Richard Smith