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

В этой статье автор утверждает:

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

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

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


c++ template-meta-programming programming-languages computability
person Dan M. Katz    schedule 22.12.2011    source источник
comment
Спасибо за правки, Коди... В следующий раз постараюсь быть чище :)   -  person Dan M. Katz    schedule 22.12.2011
comment
Будучи примитивно-рекурсивным, метапрограммирование шаблонов C++ также эквивалентно Тьюрингу.   -  person Gabe    schedule 22.12.2011
comment
Поправьте меня, если я ошибаюсь, но я полагаю, что утверждение о том, что язык является примитивно-рекурсивным, означает, что вы можете запрограммировать очень определенный класс функций (а именно те, которые не используют неограниченные циклы). Примитивно-рекурсивные языки гарантируют, что любая программа, написанная на них, остановится... Конечно, язык, эквивалентный Тьюрингу, также может выполнять примитивно-рекурсивную функцию, но это не главное.   -  person Dan M. Katz    schedule 22.12.2011
comment
Я могу ошибаться, но мне неизвестно определение примитивно-рекурсивного языка, поэтому я предположил, что это означает язык, на котором можно писать примитивно-рекурсивные функции. Если это означает язык, на котором могут быть написаны только примитивно-рекурсивные функции, то я действительно ошибаюсь.   -  person Gabe    schedule 22.12.2011

Ответы (2)


arrow_upward
3
arrow_downward

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

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

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

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

person jalf    schedule 22.12.2011
comment
Аааа, понятно... Как-то я даже не подумал об этом :) Большое спасибо! - person Dan M. Katz; 22.12.2011

arrow_upward
1
arrow_downward

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

person Yttrill    schedule 29.12.2011
comment
Ах я вижу. Большое спасибо; это, должно быть, было на что посмотреть! - person Dan M. Katz; 30.12.2011
comment
Да, такое волнение редко встречается на заседаниях комитета ISO :) - person Yttrill; 02.01.2012