Шаблон метапрограммирования: примитивный рекурсивный?

Question

В this article, автор утверждает:

... программа действительно показывают, что механизм шаблонов конкретизации является примитивно рекурсивным языком, который может выполнять нетривиальные вычисления во время компиляции.

Я нашел это довольно интересным, так как я помогаю преподавать класс в Теории вычислений, который вникает в теорию примитивно-рекурсивных функций. Тем не менее, у меня создалось впечатление, что Template Metaprogramming был Turing-complete, что является строго более сильным утверждением, чем сказать, что оно примитивно рекурсивно ... И в конце концов, создать метапрограмму шаблона, которая не может остановить, не очень сложно ,

Я что-то упустил? Является ли шаблон метапрограммированием строго примитивного рекурсивного языка, или я верю, что считаю, что он охватывает более широкий спектр программ?

Answer 1

Я считаю, что вы просто слишком много читали в тексте, а «примитив» не означает «примитивный рекурсивный», а скорее «рекурсивный язык» (который звучит странно, я бы назвал это так: функциональный язык, но неважно), что является примитивным.

Если вы рассматриваете TMP как функциональный язык, это не очень сложный; таким образом, он является примитивным.

Но вы правы, TMP, безусловно, является Тьюрингом.

Я сомневаюсь, что многие люди слышали о примитивных рекурсивных языках, и поэтому это всего лишь неудачный выбор слов.

Answer 2

Программа Unruh продемонстрировала только примитивную рекурсию, то есть цикл (я действительно присутствовал, когда это произошло!). Однако сразу же было признано, что полная рекурсия была поддержана (потому что на самом деле реализация не выполняла оптимизацию хвоста).