我們知道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