更新时间:2022-10-15 13:26:57
tl; dr: constexpr
在C ++ 11中不是Turing完成,由于语言规范中的一个错误,但是该漏洞已在标准的后续草稿中得到解决,并且clang已经实现了修复。
constexpr
如ISO C ++ 11国际标准中规定的,不是图灵完备。草图证明:
constexpr
函数 f 对特定参数序列的结果(或非终止) a ...
仅由 a ...
[basic.types] p10
是: a
其中 f
可以接收是有限的,因此任何有限描述的 constexpr
system是一个有限状态机,因此不是Turing完成。自从C ++ 11标准发布以来,情况已经改变。
约翰内斯·绍布对 std :: max()和std :: min()not constexpr 被报告给C ++标准化委员会作为核心问题1454.在2012年2月WG21会议上,我们决定这是标准中的缺陷,所选择的解决方案包括能够使用指针或指定临时表达式的引用成员创建类类型的值。这允许通过 constexpr
函数来累积和处理无限量的信息,并且足以使 constexpr
评估图灵完成(假设实现支持递归到***深度)。
为了演示实现核心问题1454的解决方案的编译器的 constexpr
的Turing完整性,我为clang的测试套件写了一个图灵机模拟器:
http://llvm.org/svn/llvm-project/cfe/trunk/test/SemaCXX/constexpr-turing.cpp p>
g ++和clang的Trunk版本实现了这个核心问题的解决方案,但g ++的实现目前无法处理此代码。
We know that C++ template metaprogramming is Turing complete, but preprocessor metaprogramming is not.
C++11 gives us a new form of metaprogramming: computation of constexpr functions. Is this form of computation Turing-complete? I am thinking that since recursion and the conditional operator (?:) are allowed in constexpr functions, it would be, but I would like someone with more expertise to confirm.
tl;dr: constexpr
in C++11 was not Turing-complete, due to a bug in the specification of the language, but that bug has been addressed in later drafts of the standard, and clang already implements the fix.
constexpr
, as specified in the ISO C++11 international standard, is not Turing-complete. Sketch proof:
constexpr
function f
's result (or non-termination) on a particular sequence of arguments, a...
, is determined only by the values of a...
[basic.types]p10
is either:
a...
which f
can receive is finite, so any finitely-described constexpr
system is a finite state machine, and thus is not Turing-complete.However, since the publication of the C++11 standard, the situation has changed.
The problem described in Johannes Schaub's answer to std::max() and std::min() not constexpr was reported to the C++ standardization committee as core issue 1454. At the February 2012 WG21 meeting, we decided that this was a defect in the standard, and the chosen resolution included the ability to create values of class types with pointer or reference members that designate temporaries. This allows an unbounded quantity of information to be accumulated and processed by a constexpr
function, and is sufficient to make constexpr
evaluation Turing-complete (assuming that the implementation supports recursion to an unbounded depth).
In order to demonstrate the Turing-completeness of constexpr
for a compiler that implements the proposed resolution of core issue 1454, I wrote a Turing-machine simulator for clang's test suite:
http://llvm.org/svn/llvm-project/cfe/trunk/test/SemaCXX/constexpr-turing.cpp
Trunk versions of both g++ and clang implement the resolution of this core issue, but g++'s implementation currently is unable to process this code.