模板元編程：基元遞歸？

Question

在this article，筆者斷言：

...程序確實顯示模板實例化機制是可以在編譯時完成重要的計算原始遞歸語言。

我發現這很有趣，因爲我幫助教授計算理論中的一門課，該課深入了原始遞歸函數的理論。然而，我的印象是模板元編程是圖靈完備的，這是一個嚴格的強烈的說法，而不是說它是原始的遞歸......畢竟，創建一個模板元程序並不是很難，它不會停止。

我錯過了什麼嗎？模板元語言是一種嚴格的原始遞歸語言，還是我相信它涵蓋了更廣泛的程序？

Answer 1

我相信你只是讀了太多的文字，而「原始」並不意味着「原始遞歸」，而是它是一種「遞歸語言」（聽起來很古怪，我稱之爲描述爲一種功能語言，但從不介意），這是原始的。

如果將TMP看作是一種功能性語言，它不是一個非常複雜的語言;因此，這是一個原始的。

但是你是對的，TMP肯定是圖靈完備的。

我懷疑很多人聽說過原始遞歸語言，所以這只是一個不幸的選擇。

Answer 2

Unruh的程序只展示了原始遞歸，也就是循環（當發生這種情況時，我確實存在！）。然而，立即認識到完全遞歸得到了支持（因爲實際上的確沒有進行tail rec優化）。