c++ - 模板元编程：原始递归？

Question

在这篇文章中，作者断言：

...该程序确实表明模板实例化机制是一种原始递归语言，可以在编译时执行非平凡的计算。

我发现这很有趣，因为我帮助教授了一门计算理论课程，该课程深入研究了原始递归函数的理论。然而，我的印象是模板元编程是图灵完备的，这是一个比说它是原始递归更严格的陈述......毕竟，创建一个无法停止的模板元程序并不是很困难.

我错过了什么吗？模板元编程是一种严格的原始递归语言，还是我认为它涵盖更广泛的程序是正确的？

Answer 1

我相信您只是对文本阅读过多，并且“原始”并不意味着“原始递归”，而是一种“递归语言”（这听起来很奇怪，我称之为将其描述为功能语言，但没关系），这是原始的。

如果您将 TMP 视为一种函数式语言，它并不是一种非常复杂的语言。因此，它是一个原始的。

但是你是对的，TMP 肯定是图灵完备的。

我怀疑很多人听说过原始递归语言，所以这只是一个不幸的单词选择。

Answer 2

Unruh 的程序只演示了原始递归，即循环（发生这种情况时我实际上在场！）。然而，立即认识到支持完全递归（因为确实该实现没有进行尾部记录优化）。